Matlab

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

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

وضعیت : موجود

برند :Matlab

تعداد بازدید: 21
0 0

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

 

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

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

 

ساده ترین راه حل این مسئله، تعیین جایگشت های شهرها و بررسی هزینه های آن است که مرتبه این روش !n خواهد بود که به همین دلیل به آن یک مسئله NP Hard میگویند. راه حل برنامه نویسی پویا برای حل این مسئله دارای مرتبه n2.2n است. 

البته فروشنده دوره گرد میتواند با فروش اجناس خود در Ebay، با مرتبه (1)O مسئله خود را حل کند :)

 

راه حل های دیگری نیز وجود دارد که میتوان به روش های مکاشفه ای مانند الگوریتم ژنتیک اشاره کرد. الگوریتم ژنتیک سعی دارد تا ترتیبی از شهرها را پیدا کند که کمترین هزینه را داشته باشد. 

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

 

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

 

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

1. با استفاده از اجرای آنلاین که در هر مرحله، مسیر بهینه طی شده توسط فروشنده دوره گرد نشان داده میشود که متعاقبا به دلیل نمایش گرافیکی جواب، زمان بیشتری برای رسیدن به جواب لازم است.

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

 

ویدیوی زیر نحوه اجرای این پیاده سازی را نشان میدهد.

ویدیو نحوه اجرای کد و نمایش خروجی

 

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

 

در صورت هر گونه سوال نسبت به کالای مورد نظر، با ایمیل msd.abasian@gmail.com  یا شماره 09132324263 و یا آیدی تلگرام masoudabasian مکاتبه نمایید.

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

با تشکر از حسن اعتماد شما

مسعود عباسیان

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

20،000 تومان افزودن به سبد خرید

محل نوشتن دیدگاه شما


تعداد نظرات : 0