تابع برازش مسئله فروشنده دوره‌گرد – قسمت دوم

توی مطلب قبل تابع برازشی رو برای مسئله فروشنده دوره گرد (Travelling SalesmanProblem – TSP) مطرح کردیم، در ادامه قصد داریم، تابع برازش رو کاملتر کنیم. پیش از ادامه، نیاز است که این مطلب تابع برازش مسئله فروشنده دوره گرد در الگوریتم ژنتیک رو مرور کنید.

نقشه شهرهای که داشتیم به صورت زیر بود

تابعی که هم که بهش رسیده بودیم این بود.

Function FitnessFunctionTSP(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;
}

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

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

قبل ادامه یک سوال رو جواب بدیم

اگر یکی از شروط فوق رعایت نشده بود باید چکار کنیم؟

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

Function FitnessFunctionTSP(Chromosome)
{
Sum = 0;
If (!conations(Chromosome, all Cities))
Return -1;
If(Length (Chromosome) != Count(Cities))
Return -1;
If(Start_City != End_City)
Return -1;
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;
}

خوب شروط بالا چی میگن:
شرط اول میگه اگر کروموزم شامل همه شهرها نبود مقدار غیر جاز یعنی -۱ رو برگردون
شرط دوم میگه اگر طول کروموزم مخالف تعداد شهرها بود مقدار غیر مجاز یعنی -۱ رو برگردون
یک نکته مهم: دو شرط بالا با هم یعنی ما از هر شهر فقط و فقط یک بار عبور کنیم، یکم فکر کنید ببینید شما هم به همین نتیجه من می رسید

شرط سوم میگه : اگر شهر ابتدا و انتها یکی نبود مقدار غیر مجاز یعنی -۱ رو برگردون

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

این کروموزم سه تا شرط بالا رو داره یعنی شامل تمام شهرها هستش، هر شهری فقط و فقط یک بار تکرار شده و شهر ابتدا و انتها هم یکی است. نکته مهم اینکه مسیری از شهر E به شهر C وجود نداره … این موضوع رو هم باید در تابع برازش مسئله فروشنده دوره‌گرد جای بدیم

Function FitnessFunctionTSP(Chromosome)
{
Sum = 0;
If (!conations(Chromosome, all Cities))
   Return -1;
If(Length (Chromosome) != Count(Cities))
    Return -1;
If(Start_City != End_City)
Return -1;
If( !Connect(City i , City i +1))
Return -1;
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;
}

توی شرط چهارم هم گفتیم اگر بین دو شهر پشت سرهم مسیری وجود نداشت مقدار غیر مجاز یعنی -۱ رو برگردون.

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

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