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

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

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

نمونه مسئله کوله پشتی به صورت زیر بود (حداکثر وزن کوله پشتی هم ۱۵ است)

شی ۱۲ کیلویی
شی ۲ کیلویی
شی ۱ کیلویی (با ارزش ۱ دلار)
شی ۴ کیلویی
شی ۱ کیلویی (با ارزش ۲ دلار)

تابع برازش مسئله کوله‌پشتی که معرفی کرده بودیم به این صورت بود:

Function FitnessFunctionKnapsack(Choromosom)
{
Sum = 0;
If(Obj1 is selected) Sum = Sum + 4;
If(Obj2 is selected) Sum = Sum + 2;
If(Obj3 is selected) Sum = Sum + 1;
If(Obj4 is selected) Sum = Sum + 10;
If(Obj4 is selected) Sum = Sum + 2;
Return Sum;
}

این تابع دو تا مشکل هنوز داره

مشکل اول : وزن شی های انتخاب شده رو در نظر نمی گیره.
دوتا کروموزوم زیر رو در نظر بگیرید

کروموزوم ۱

کروموزوم ۲

طبق فرمون بالا ارزش کروموزوم اول میشه ۱۳ و دومی میشه ۱۴٫ طبق این تابع کروموزوم دوم بهتر است اما نکته مهم این است که وزن شی های انتخاب شده برابر ۱۶ است و ۱۵ بیشتر است در نتیجه این کروموزوم با اینکه از کروموزوم اول بهتر است اما جواب مسئله نیست.

برای حل این مشل کد بالا را به صورت زیر تغییر می دهیم:

Function FitnessFunctionKnapsack(Choromosom)
{
Sum = 0;
Weight  = ۰;
If(Obj1 is selected) Sum = Sum + 4 and Weight   = Weight   + ۱۲;
If(Obj2 is selected) Sum = Sum + 2 and Weight   = Weight   + ۲;
If(Obj3 is selected) Sum = Sum + 1 and Weight   = Weight   + ۱;
If(Obj4 is selected) Sum = Sum + 10 and Weight   = Weight   + ۴;
If(Obj4 is selected) Sum = Sum + 2 and Weight   = Weight   + ۱;

IF(and Weight   <= 15)
      Return Sum;
ELSE
      ???
}

توی تابع فوق مشکل مربوط به مجاز بودن وزن اشیاء حل شده، همانطور که مشخصه بر اساس اینکه کدوم شی انتخاب شده وزن شی هم به مجموعه وزن ها (Weight)  اضافه شده.
یک مشکل دیگه که به وجود میاد اینکه خوب اگر وزن اشیاء انتخاب بیشتر از ۱۵ بود باید چکار کنیم؟ (به جای؟؟؟ باید چه چیزی بنویسم)

روش های زیادی برای حل این مشکل وجود داره ولی باید دقت داشت که روش منطقی و قابل قبول ارائه بدهیم.
یک نکته قبل ارائه حل رو باید بهش دقت داشت: بدترین کروموزومی، کروموزومی است که هیچ یک از اشیاء انتخاب نشه، به عبارت دیگه مجموعه ارزش اشیاء انتخابی برابر صفر میشه. خوب این نکته به چه دردی میخوره؟ پس اگر ما در صورت فراتر رفتن وزن اشیاء انتخاب شده از وزن مجاز کوله پشتی، عددی منفی (مثلا ۱-) رو برگردونیم اون وقت این جواب از همه جواب های مجاز کمتر خواهد بود. این به چه دردی می خوره؟
این مقدار برای این مسئله یک جواب غیر قابل قبول است. یعنی ما نمی تونیم مجموعه ای از اشیاء رو انتخاب کنیم که مجموع ارزش اونها بشه ۱-، پس هر وقت این مقدار برگردونده شده یعنی اون کروموزوم (جواب) غیر قابل قبول است و می توان اونو دور ریخت. در نتیجه تابع نهایی میشه شکل زیر

Function FitnessFunctionKnapsack(Choromosom)
{
Sum = 0;
Weight  = ۰;
If(Obj1 is selected) Sum = Sum + 4 and Weight   = Weight   + ۱۲;
If(Obj2 is selected) Sum = Sum + 2 and Weight   = Weight   + ۲;
If(Obj3 is selected) Sum = Sum + 1 and Weight   = Weight   + ۱;
If(Obj4 is selected) Sum = Sum + 10 and Weight   = Weight   + ۴;
If(Obj4 is selected) Sum = Sum + 2 and Weight   = Weight   + ۱;

IF(and Weight   <= 15)
     Return Sum;
ELSE
-۱;
}

(دقت داشته باشید کد بالا بهینه و مبتنی بر هیچ زبان برنامه نویسی خاصی نیست). فقط یک نمای کلی از کد نهایی تابع برازش مسئله کوله‌پشتی است، می توان این کد را به هر زبانی بازنویسی کرد.

پرونده تابع برازش مسئله کوله‌پشتی اینجا بسته شد، منتظر سایر تابع برازش در قالب مثال باشید.