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

توی مطالب قبل در مورد انواع نمایش کروموزوم ها صحبت کردیم توی این مطلب قصد داریم در مورد نمایش باینری مسئله کوله پشتی در الگوریتم ژنتیک صحبت کنیم.

نمایش باینری: همون طور که گفتیم هر کروموزم از یک سری ژن تشکیل شده. توی نمایش حالت باینری کروموزم میشه سری ژن که مقدرا اونا 0 یا 1 است. اگر مسئله هنوز برای شما گنگ هستش نگران نباشید. با چند مثال قصد درایم این مورد رو بررسی میکنیم.

کوله پشتی در الگوریتم ژنتیک: مسئله کوله پشتی که یا Knapsack: فرض کنید مجموعه‌ای از اشیا داریم، که هر کدام داری وزن و ارزش خاصی هستند. ما یک کوله پشتی داریم که می‌خواهم اشیاء را طوری انتخاب کنیم که وزن اشیا انتخاب شده از ظرفیت گوله پشتی کوچکتر یا مساوی باشد، ولی ارزش آنها بیشینه شود.
توی شکل زیر یک نموه مسئله اومده ما 5 تا شی داریم که وزن و ارزش اونها توی شکل مشخص شده و اندازه کوله پشتی هم 15 کیلو هستش به نظر شما چه ترکیبی رو باید از اشیاء برداریم که از حجم کوله پشتی بیشتر نشه و ارزشش هم بیشینه باشه؟ (حل مسئله باشه بعداً)مسئله کوله پشتی و الگوریتم ژنتیک
حالا اگر بخواهیم این مسئله رو با الگوریتم ژنتیک حل کنیم اول باید کروموزوم ها رو بسازیم.
فرض کنید اشیاء رو به صورت زیر مرتب کردیم
1-    شی 12 کیلویی
2-    شی 2 کیلویی
3-    شی 1 کیلویی (با ارزش 1 دلار)
4-    شی 4 کیلویی
5-    شی 1 کیلویی (با ارزش 2 دلار)
همون طور که گفتیم کروموزوم یعنی یک جواب احتمالی برای مسئله. خوب حالا چند تا کروموزوم بررسی کنیم
 کروموزوم 1 مسئله کوله پشتی در الگوریتم ژنتیک:
مسئله کوله پشتی و الگوریتم ژنتیک
کروموزوم بالا یعنی چی: یعنی ما شی دوم و سوم و چهارم رو انتخاب کردیم و بقیه رو انتخاب نکردیم (در این صورت وزن اشیا میشه 2 + 1 +4 = 7 که مجموع وزن اونا حجم کوله پشتی کمتر است و ارزششون میشه 1+10+2 = 13 دلار)کروموزوم 2 مسئله کوله پشتی در الگوریتم ژنتیک:
مسئله کوله پشتی و الگوریتم ژنتیک
کروموزوم بالا یعنی چی: یعنی ما شی اول و چهارم رو انتخاب کردیم بقیه رو انتخاب نکردیم (در این صورت وزن اشیا میشه 12+4 = 14 که بیشتر از حجم کوله پشتی است پس جواب مناسبی نیست)ما می تونیم کلی کروموزوم داشته باشیم. اینکه چطوری به جواب برسیم رو بعداً توضیح میدیم. توی این مطلب فقط می‌خواستیم نمایش کروموزوم مسئله کوله پشتی با حالت باینری رو بررسی کنیم.

کانال تلگرامی MrMining.ir

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *