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

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

فروشنده دوره گرد: صورت مسئله اینکه ما تعدادی شهر داریم که فاصله بین شهرهای  مقدار مشخصی است. در مسئله فروشنده دوره گرد قصد داریم مسیری را پیدا کنیم که دو ویژگی زیر رو داشته باشه
۱- همه شهرها  رو دقیقاً یک بار طی کنیم و به نقطه شروع برگردیم
۲- کم هزینه‌ترین مسیر باشه

مثال زیر رو در نظر بگیرید.

توی شکل بالا هر حرف نماینده یک شهر است و فاصله بین شهرها با اعداد مشخص شده است است. مثلا فاصله بین دو شهر A و  B برابر ۲۴  است.

همون طور که گفتیم کروموزوم یعنی یک جواب احتمالی برای مسئله. خوب حالا چند تا کروموزوم بررسی کنیم
کروموزوم ۱ مسئله فروشنده دوره گرد:

خوب بریم سراغ تابع برازش مسئله فروشنده دوره گرد: این تابع می تونه به صورت زیر باشه. دقت داشته باشید بر اساس کروموزم فوق فروشنده از شهر ۱ (A) به شهر ۲ (B) می رود و بعد از شهر ۲ (B) به شهر ۳ (C) می رود و … تا آخر

Function FitnessFunctionKnapsack(Choromosom)
{
Sum = 0;
Sum = Sum + Distance City1(A)-City2(B);
Sum = Sum + Distance City2(B)-City3(C);
Sum = Sum + Distance City3(C)-City4(D);
Sum = Sum + Distance City4(D)-City5(E);
Sum = Sum + Distance City5(e)-City1(A);
Return Sum;
}

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

Sum = 24 + 9 + 8 + 28 + 10 = 79;

کروموزوم ۲ فروشنده دوره گرد :

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

Sum = 10 + 30 + 9 + 8  + ۲۵ =۸۲;

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