حل مسئله فروشنده دوره رد (tsp) با استفاده از الگوریتم ژنتیک

در حل TSP با الگوریتم ژنتیک سه قسمت اساسی Encoding ,  Mutation , Crossover است.

 روشهای  Encoding

1.استفاده از ماتریس مجاورت گراف است . اگر در مکان i , j عدد 1 وجود داشت یعنی یک یال از ذاس i به j وجود دارد و اگر 0 بود یعنی یالی یا مسیری نیست  به طور مثال 

در ماتریس روبرو از راس 1 به راس 3 میرویم و از راس 3 به راس 2 میرویم و از راس 2 به راس 1 میرویم در واقع این دور را ایجاد می کنیم:

1--->3--->2--->1

که برای راس یک می توان از 001 و برای راس دوم از 100 و برای راس سوم از 001 نیز استفاده کرد به جای استفاده از ماتریس.

2. استفاده از جایگشت است که در حل مسائل TSP بیشتر از این روش استفاده می شود که برای مثال بالا به این شکل مطرح می شود شماره هر راس را کنار هم قرار می دهیم    1321

جمعیت اولیه

با توجه به Encoding که انتخاب می کنیم تعدادی جمعیت اولیه را که می خواهیم از آن استفاده کنیم را ایجاد می کنیم.

تابع برازش یا Fitness برای آنها را نیز محاسبه می کنیم که برای TSP استاندارد طول دور حاصل از پیمایش در راستای کروموزوم های مورد نظر می باشد.

روشهای Crossover در TSP

یکی از نسائل مهم در TSP که به روش جایگشت encoding میشود مسئله Crossover می باشد زیرا بعد از عمل Crossover   فرزندان نیز باید خاصیت جایگشت بودن خود را حفظ کنند.

همانطور که ملا حظه می کنید بعضی اعداد دوبار تکرار شده و خاصیت جایگشتی اعداد 0 تا 7 را ندارد که به چند روش می توان این مشکل را حل کرد که در زیر به شرح چند روش آن خواهیم پرداخت:

1 - روش PMX

یک نقطه را به دلخواه در کروموزوم والد انتخاب می کنیم.

سپس قسمت های تکراری را در کروموزوم مقابل پیدا می کنیم و جای آنها را تعویض می کنیم.

و این کار را چند بار تکرار می کنیم تا فرزندان با ویژگیهای مختلف داشته باشیم.

2 - روش OX  (ordered Crossover)

در این روش نیمی از کروموزوم ها را ارپز والد اول انتخاب می کنیم و در همان جای خود در فرزند قرار می دهیم و بقیه کروموزمو ها فرزند را با توجه با والد دوم به ترتیب پر می کنیم مانند شکل زیر:

روش CX (cycle crossover)

برای توضیح این روش ابتدا از شکل شروع می کنیم فکر کنم این طور بهتر می توان توضیح داد:

از والد اول شروع می کنیم واولین عنصر را انتخاب می کنیم (عدد 1 ) حالا به اولین عنصر از والد دوم میرویم ( عدد 9) آنها را به هم وصل می کنیم در ادامه دنبال عدد 9 در والد اول میرگردیم  و آنها را به هم وصل می کنیم و دوباره به سمت عنصر والد دوم در همان مکان میرویم (عدد 4) و این کار را انچنان ادامه می دهیم تا به عنصر اولی که انتخاب کردیم یعنی 1 برسیم و دوباره عنصر بعد را که چرخه نیست میرویم (عدد2) و ینکار را ادامه میدهیم تا دوباره به آن برسیم و در دور بعد تنها یک عنصر باقیمانده (عدد6 ) و در پایان جای عناصر هر والد را با توجه به جهت های بدست آمده جابه جا می کنیم حالا دو فرزند جدید داریم.

روش MOX

ادامه دارد  ...