بررسی روند اجرایی الگوریتم ژنتیک در مساله کوله پشتی صفر و یک

یکی از مسائل مهم در زمینه مسائل تصمیم گیری و مهم تر از آن بهینه سازی، مساله کوله پشتی است. مخصوصا در مواردی که مساله زمان و سرمایه گذاری در یک زمینه جزو فاکتورهای بحرانی است و از درجه اهمیت بالایی برخوردار می باشد، حل دقیق و بهینه مساله کوله پشتی، راهگشا خواهد بود. از طرف دیگر در تخصیص منابع با محدودیت مالی، و مواردی از قبیل ترکیبات،نظریه پیچیدگی محاسباتی، رمز نگاری و ریاضیات کاربردی نیز با این مساله روبرو هستیم. الگوریتم های مختلفی برای حل مساله کوله پشتی ارائه شده است، اما مرتبه زمانی بیشتر آنها، نمایی است. اخیرا روش دیگری به نام الگوریتم ژنتیک برای این مساله ارائه شده که پیچیدگی محاسباتی آن برای مساله کوله پشتی به صورت چند جمله ای می باشد. الگوریتم ژنتیک جزو الگوریتم های تکرار شونده به شمار می رود، و در هر محله از میان راه حل هایی که تمام ترکیبات ممکن را دارد، بهتری راه حل را انتخاب می کند. در این مقاله سعی شده روند اجرایی الگوریتم ژنتیک برای مساله کوله پشتی مورد بررسی قرار بگیرد و در نهایت نتایج شبیه سازی در دو نمودار با هم مقایسه و بهینه نهایی ارائه می شود.

کلیدواژه ها:

الگوریتم ژنتیک ، بهینه سازی ، کوله پشتی ، fitness