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

ما قبلاً در مورد کروموزوم و شیوه‌های نمایش کروموزوم صحبت کردیم (مطلب ۱ ، مطلب ۲ ، مطلب ۳ ، مطلب ۴). توی این مطلب قصد داریم در مورد نمایش جایگشتی کروموزوم مسئله فروشنده دوره گرد در الگوریتم ژنتیک صحبت کنیم. مسئله فرونشده دوره گرد یا Traveling Salesman Problem به اختصار TSP نامیده میشود

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

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

توی شکل زیر یک نموه مسئله اومده ما ۵ تا شهر داریم و فاصله بین اونها هم مشخص شده. به نظر شما چه ترتیبی رو باید از شهرها بلید طی کنیم تا کمترین فاصله رو پیموده باشیم؟ (حل مسئله باشه بعداً)

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

کروموزوم ۱  مسئله فروشنده دوره گرد در الگوریتم ژنتیک:
کروموزوم بالا یعنی چی: یعنی ما از شهر A شروع کنیم، بعد میریم شهر B و بعد D و بعد C و بعد در نهایت دوباره برگردیم شهر A. در این صورت مسافت طی شده میشه
۳۰+۳۵+۲۵+۵۰=۱۴۰
کروموزوم ۲ مسئله فروشنده دوره گرد در الگوریتم ژنتیک:

کروموزوم بالا یعنی چی: یعنی ما از شهر A شروع کنیم، بعد میریم شهر B و بعد C و بعد D و بعد در نهایت دوباره برگردیم شهر A. در این صورت مسافت طی شده میشه
۳۰+۳۰+۲۵+۴۰=۱۲۵

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

کروموزوم بالا یعنی چی: یعنی ما از شهر A شروع کنیم، بعد میریم شهر C و بعد B و بعد D و بعد در نهایت دوباره برگردیم شهر A. در این صورت مسافت طی شده میشه
۵۰+۳۰+۳۵+۴۰=۱۵۵

ما می تونیم کلی کروموزوم داشته باشیم. اینکه چطوری به جواب برسیم رو بعداً توضیح میدیم. توی این مطلب فقط می‌خواستیم نمایش کروموزوم فروشنده دوره گرد با حالت جایگشتی رو بررسی کنیم.