حل مساله ی کوله پشتی 0-1 با استفاده از الگوریتم ژنتیک

1- مساله ی کوله پشتی چیست؟

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

سابقه ی کار بر روی این مساله به سال 1897 می رسد. این مساله در دنیای واقعی کاربردهای فراوانی دارد. این مساله به صورت های مختلفی بیان شده است در روش حل به صورت 0-1 فرض بر این است که هر کدام از کالاهای کاندید برای قرار گرفتن در کوله پشتی می توانند دارای دو حال باشند: یا برداشته می شوند و یا برداشته نمی شوند. این در حالی است که در روش حل دیگری به نام "کسری" مجاز هستیم تا در صورت دارا بودن شرایط، کسری از یک کالا را برای قرار گرفتن در کوله پشتی انتخاب کرده و کسر دیگری را برنداریم. به این دلیل که در روش حل 0-1 نمی توانیم قسمتی از کالا را برداریم، برای پیاده سازی این روش استفاده از الگوریتم حریصانه ممکن نیست و بایستی از الگوریتم های بهینه سازی استفاده کرد. الگوریتم ژنتیک یکی از این نوع الگوریتم ها است.

2- الگوریتم ژنتیک چیست؟

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

3- الگوریتم ژنتیک چگونه کار می کند؟

الگوریتم ژنتیک در مواردی که نیاز به رسیدن به جوابی با کیفیت بالا در زمان مناسب داریم به کار برده میشوند ایدهی کار ساده است، در هر مرحله تمام جواب های ممکن بررسی و جوابی که نزدیکتر به جواب اصلی باشد برای مرحله بعد انتخاب می شود.

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

دقیقا مطابق با مراحلی که در تصویر وجود دارد توایعی تعریف می شوند و هر نسل از کروموزوم های تولید شده از این مراحل می گذرند. هر کروموزوم به حالت خاصی از جواب اطلاق می شود.

ابتدا به طور تصادفی جمعیت اولیه ایجاد می شود، در مرحله ی دوم تابعی با عنوان Fitness مقدار برازندگی هر کدام از کروموزوم های ایجاد شده به شکل تصادفی را می سنجد و بهترین کروموزوم را انتخاب می کند. در مرحله ی بعد تعداد بیشتری از بهترین کروموزوم ها نیز انتخاب می شوند و تابع Crossover بر روی هر جفت کروموزوم انتخاب شده اجرا می شود، این تابع در واقع همان عمل لقاح جانوران در طبیعت را شبیه سازی می کند و خروجی آن تولید کروموزوم های جدید یا نسل دوم خواهد بود. سپس این نسل جدید وارد تابع Mutation می شوند. Mutation یا جهش یکی از ارکان اصلی در نظریه تکامل است، در واقع موتور محرک نسل ها و عامل اصلی تکامل را می توان عمل جهش معرفی کرد در اینجا نیز کروموزوم های جدید وارد این تابع شده و با احتمالی متغیر برخی از ژن ها جهش می یابند تا در نهایت جمعیت جدید ایجاد شود. جمعیت جدید بارها و بارها همین مراحل را تکرار می کنند تا در نهایت به جواب بهینه نزدیک شوند.

4- توضیحات مربوط به کد نوشته شده

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

درباره کروموزوم در بخش های قبل صحبت کردیم، کروموزوم به صورت اجمالی به یک حال از جواب اطلاق می شود، در تصویر ذیل یک کروموزوم را مشاهده می کنید:

همانطور که در تصویر مشخص است یک کروموزوم در واقع رشته ای از صفر و یک ها است. دلیل این امر به ماهیت مساله ی ما بر میگردد که باید هر کدام از کالاها انتخاب شوند یا خیر و حالت میانی وجود ندارد.

در مساله ی ما هر کروموزوم رشته ای 10 رقمی است و هر رقم یا اصطلاحا ژن نشاندهنده ی این موضوع است که در این کروموزوم خاص کالای مرتبط با آن رقم یا ژن در کوله پشتی انتخاب خواهد شد یا خیر.

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

با توجه به توضیحات ارائه شده کروموزوم 0001101001 به معنای این است که به ترتیب از چپ به راست آیتم های چهارم، پنجم، هفتم و دهم طبق این کروموزوم باید در کوله پشتی قرار بگیرند. در صورتی که ارزش معادل این کالاها را محاسبه کنیم به عدد 155 می رسیم که این عدد بالاترین ارزشی است که می توانیم طبق تعریف مساله ی کوله پشتی 0-1 در این کوله پشتی فرضی با این مشخصات جای دهیم. بنابراین می توانیم بگوییم این کروموزوم جواب نهایی ماست که باید الگوریتم به آن برسد.

تعاریف متغیرها به صورت زیر انجام شده است: 

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

در واقع ستون آخر را برای محاسبه و نوشتن Fitness یا ارزش معادل هر کروموزوم ایجاد کرده ایم. با کلیک روی دکمه ی Start ابتدا تابع make_first_generation() فراخوانی می شود. این تابع مرحله ی اول از الگوریتم های ژنتیک یعنی ایجاد جمعین تصادفی اولیه را بر عهده دارد.

ادامه توضیحات و ادامه کدها و همچنین سورس پروژه را بعد از خرید می توانید دانلود نمایید.