حل مسئله ی فروشنده دوره گرد با استفاده از الگوریتم ژنتیک ،پروژه درس مقدمه ای بر هوش محاسباتی بود که در اینجا قرار می دهم.
روی سوال مسئله را در ادامه قرار می دهیم و در انتها فایل matlab حاوی سورس برنامه رو با نتیجه ی آن رو قرار خواهم داد.
1- 26 نقطه تصادفی در فاصله ( 0و0 ) و ( 100 و 100 ) به عنوان شهرها در مسئله فروشنده دورگرد اختیار نمائید .
2- یکی از نقاط را به عنوان مبدأ انتخاب کرده و از آن می¬خواهیم به سایر شهرها هر کدام یکبار و فقط یکبار رفته و به مبدأ برگردیم . کوتاهترین مسیر مطلوبست .
3- برای پیدا کردن ترتیب بهینه شهرها که مسیر طی شده در کل کمینه باشد ، از الگوریتم ژنتیک استفاده می¬کنیم . هر شهر را با یکی از حروف لاتین کد میکنیم .
4- بهترین مسیر بدست آمده در الگوریتم پس از تکرار اول ، تکرار صدم ، تکرار پانزدهم و نیز در پایان الگوریتم را روی صفحه رسم ( plot ) و روند تکامل و بهینه¬سازی را مشاهده نمائید .
توجه : برای اینکه عملگرهای ژنتیکی تقاطع و جهش در اینجا به ترتیب غیرمعتبر شهرها ( مسیر غیرمعتبر ) منجر نشود ، می¬توانید از عملگرهای زیر استفاده کنید :
جهش : جابه¬جایی تصادفی دو شهر در ترتیب فعلی
تقاطع : معکوس کردن بخشی از زنجیره پس از بریدن تصادفی دو نقطه¬ای از زنجیره .
نتیجه :
منبع : www.bioemm.com
روی سوال مسئله را در ادامه قرار می دهیم و در انتها فایل matlab حاوی سورس برنامه رو با نتیجه ی آن رو قرار خواهم داد.
1- 26 نقطه تصادفی در فاصله ( 0و0 ) و ( 100 و 100 ) به عنوان شهرها در مسئله فروشنده دورگرد اختیار نمائید .
2- یکی از نقاط را به عنوان مبدأ انتخاب کرده و از آن می¬خواهیم به سایر شهرها هر کدام یکبار و فقط یکبار رفته و به مبدأ برگردیم . کوتاهترین مسیر مطلوبست .
3- برای پیدا کردن ترتیب بهینه شهرها که مسیر طی شده در کل کمینه باشد ، از الگوریتم ژنتیک استفاده می¬کنیم . هر شهر را با یکی از حروف لاتین کد میکنیم .
4- بهترین مسیر بدست آمده در الگوریتم پس از تکرار اول ، تکرار صدم ، تکرار پانزدهم و نیز در پایان الگوریتم را روی صفحه رسم ( plot ) و روند تکامل و بهینه¬سازی را مشاهده نمائید .
توجه : برای اینکه عملگرهای ژنتیکی تقاطع و جهش در اینجا به ترتیب غیرمعتبر شهرها ( مسیر غیرمعتبر ) منجر نشود ، می¬توانید از عملگرهای زیر استفاده کنید :
جهش : جابه¬جایی تصادفی دو شهر در ترتیب فعلی
تقاطع : معکوس کردن بخشی از زنجیره پس از بریدن تصادفی دو نقطه¬ای از زنجیره .
نتیجه :
منبع : www.bioemm.com
