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

توضیحات

در این قسمت تیم کدگیت سورس مسئله کوله پشتی با الگوریتم ژنتیک را تهیه کرده است. مسئله کوله پشتی یکی از مسائل Np-hard است که برای رسیدن به جواب زمان زیادی را باید صرف کرد. اینگونه مسائل را می توان با الگوریتم‌های تکاملی مانند الگوریتم ژنتیک حل کرد. اگرچه به پاسخ بهینه ممکن است نرسید اما در زمان کم به پاسخی مناسب خواهید رسید. ادامه با ما همراه باشید تا سورس تهیه شده از حل مسئله کئله پشتی  را با کمک الگوریتم ژنتیک معرفی کنیم. همچنین پیشنهاد می‌کنیم از دیگر محصولات ما نیز دیدن فرمایید:

• فیلم الگوریتم ژنتیک در پایتون
• سورس تشخیص لبخند در پایتون
• ویدئو الگوریتم هافمن در پایتون
• سورس تابع سیگموئید در پایتون
• سورس بازی پازل کشویی در پایتون

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

فرض کنید ما کوله پشتی داریم که می خواهیم وسایلی در آن قرار دهیم. کوله پشتی میزان ثابتی وزن را در خود جای می‌دهد و ما از وزن و وسایل اطلاعات کاملی داریم. میزان وزنی که در کوله پشتی جا می‌گیرد را Capacity قرار می‌دهیم. وسایلی که می توانیم در آن قرار دهیم دارای وزن wi و ارزشی معادل vi دارند. به عنوان مثال ارزش وسیله اول ما برابر با v1 و وزن آن معادل با w1 است. ارزش وسیله دوم ما برابر با v2 و وزن آن معادل با w2 است. حال با دانستن پارامترهای مسئله، می خواهیم طوری وسائل را در کوله پشتی قرار دهیم که بالاترین ارزش را داشته و وزن آن نیز از مقدار ظرفیت کوله پشتی بیشتر نشود. این مسئله کوله پشتی است.

فرضیات مسئله

برای حل این مسئله از الگوریتم ژنتیک کمک گرفتیم. هر ایتم که در کوله پشتی قرار می گیرد عدد 1 و هر ایتم که در کولپشتی قرار نمی‌گیرد عدد 0 می‌دهیم. حال فرضیات مسئله را در نظر می‌گیریم:

    w = [4, 3, 2, 1]

    v = [5, 4, 3, 2]

    CAPACITY = 6

 نحوه اجرا مسئله کوله پشتی

بعد از تهیه سورس مسئله کوله پشتی با الگوریتم ژنتیک، فایلی با فرمت Zip در اختیار شما قرار خواهد گرفت. این فایل را از حالت zip خارج کرده تا فایل پروژه را ببینید. فایل اصلی پروژه GeneticAlgorithmKnapsack نام دارد. با اجرای این فایل مسئله کوله پشتی در 100 iteration اجرا خواهد شد. پس از اجرا خروجی زیر را مشاهده خواهید کرد:

Generation #86 - fittest is: 0111 with fitness value 9

Generation #87 - fittest is: 0111 with fitness value 9

Generation #88 - fittest is: 0111 with fitness value 9

Generation #89 - fittest is: 0111 with fitness value 9

Generation #90 - fittest is: 0111 with fitness value 9

Generation #91 - fittest is: 0111 with fitness value 9

Generation #92 - fittest is: 0111 with fitness value 9

Generation #93 - fittest is: 0111 with fitness value 9

Generation #94 - fittest is: 0111 with fitness value 9

Generation #95 - fittest is: 0111 with fitness value 9

Generation #96 - fittest is: 0111 with fitness value 9

Generation #97 - fittest is: 0111 with fitness value 9

Generation #98 - fittest is: 0111 with fitness value 9

Generation #99 - fittest is: 0111 with fitness value 9

Generation #100 - fittest is: 0111 with fitness value 9

Solution found...

0111

در پایان خروجی اعداد 0111 مشاهده می کنید که به معنی این است که سه ایتم پایانی در الگوریتم بهترین نتیجه را می‌دهند. ایتم اول در خروجی مسئله حذف گردیده است.