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

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

مسئله کوله پشتی در الگوریتم ژنتیک: مسئله کوله پشتی که یا Knapsack،  فرض کنید مجموعه‌ای از اشیا داریم، که هر کدام داری وزن و ارزش خاصی هستند. ما یک کوله پشتی داریم که می‌خواهم اشیاء را طوری انتخاب کنیم که وزن اشیا انتخاب شده از ظرفیت گوله پشتی کوچکتر یا مساوی باشد، ولی ارزش آنها بیشینه شود.
توی شکل زیر یک نموه مسئله اومده ما ۵ تا شی داریم که وزن و ارزش اونها توی شکل مشخص شده و اندازه کوله پشتی هم ۱۵ کیلو هستش به نظر شما چه تابع برازشی باید تعریف کنیم.

حالا اگر بخواهیم این مسئله رو با الگوریتم ژنتیک حل کنیم اول باید کروموزوم‌ها رو بسازیم.
فرض کنید اشیاء رو به صورت زیر مرتب کردیم
۱-    شی ۱۲ کیلویی
۲-    شی ۲ کیلویی
۳-    شی ۱ کیلویی (با ارزش ۱ دلار)
۴-    شی ۴ کیلویی
۵-    شی ۱ کیلویی (با ارزش ۲ دلار)
همون طور که گفتیم کروموزوم یعنی یک جواب احتمالی برای مسئله. خوب حالا چند تا کروموزوم بررسی کنیم

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

خوب بریم سراغ تابع برازش مسئله کوله پشتی: این تابع می تونه به صورت زیر باشه

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;
}

خوب تابع بالا یعنی چی:
ورودی تابع: همون طور که گفتیم ورودی تابع برازش کروموزوم است
خروجی تابع: Sum یا همون جمع ارزش اجسام انتخاب شده
بدنه تابع: بر اساس شکل مشخص میکنید اگر شی اول انتخاب شده باشد مقدار sum را ۴ واحد افزایش می دهیم، اگر شی دوم انتخاب شده باشد مقدار sum را ۲ واحد افزایش می دهیم و همین طور تا انتها. و در نهایت مقدار sum را عنوان خروجی بر می گردانیم. در نتیجه خروجی تابع به صورت زیر است

Sum = 2 + 1 + 10 =13;

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

مقدار تابع برای این کروموزوم برابر است با

Sum = 4 + 10 =14;

ایا به نظر شما این تابع برازش مناسب است؟ یا تابع برازش مسئله کوله پشتی به درستی جواب مسئله کوله پشتی را نمایش میدهد؟
تا پست بعدی کمی به این موضوع فکر کنید.