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

الگوریتم ژنتیک

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

الگوریتم ژنتیک روشی قدرتمند بوده و بر روی دسته وسیعی از مسائل به‌خوبی عمل می کند.

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

در این الگوریتم ها، جستجو بر روی مجموعه هایی از راه حل ها به‌صورت موازی انجام می شود، درحالی‌که در روش های سنتی جستجو به‌صورت ترتیبی است.

نحوه کار الگوریتم

در آغاز الگوریتم، تعدادی از افراد به‌عنوان جمعیت اولیه و معمولاً به‌صورت تصادفی ساخته‌شده و معیاری از کیفیت به نام تابع هدف یا برازندگی برای تک  تک آن ها ارزیابی می شود. اگر شرط رسیدن به جواب برقرار نباشد (به جواب بهینه نرسیده باشیم)، نسل بعدی با انتخاب والدین بر اساس میزان برازندگی آن ها تولید می شود. در هر نسل، بهترین های آن نسل انتخاب می شوند و پس از زادوولد، مجموعه جدیدی از فرزندان را تولید می کنند.

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

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

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

تعریف‌ها

الف) ژن: مقدار کد شده هر متغیر را ژن گویند.

ب)کروموزوم: به رشته یا دنباله ای از ژن ها که به‌عنوان شکل کد شده یک جواب ممکن (مناسب یا نامناسب) از مسئله موردنظر به کار می رود کروموزوم گویند.

ج) جمعیت: در هر مرحله تکرار از الگوریتم ژنتیکی تعدادی مشخص از کروموزوم ها مورد ارزیابی قرار می گیرد. به مجموعه این کروموزوم ها جمعیت می گویند.

د) عدد برازندگی: مناسب بودن یا نبودن را با معیاری که باهدف(مورد بهینه‌سازی) رابطه دارد می‌سنجند.

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

و) عملگر جهش: این عملگر روی یک دنباله منفرد عمل می کند به‌این‌ترتیب که با احتمال کوچکی به نام احتمال جهش هر ژن از کروموزوم ها را تغییر می دهد.

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

ح) جایگذاری: پس‌ازآنکه فرزندان جدید، با استفاده از جمعیت قدیمی ساخته شدند و میزان شایستگی آن‌ها نیز تعیین گردید، می بایست یک نسل جدید از میان فرزندان و والدین موجود انتخاب شوند.
ط) عملگر انتخاب: برای ایجاد افراد نسل جدید، از عملگر انتخاب استفاده می‌شود. اولین قدم در این راه تعیین شایستگی تک‌تک افراد جمعیت هست.

ی) مرحله تولید: به هر بار تولید یک جمعیت جدید یک مرحله تولید گویند.

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

مسئله فروشنده دورگرد TSP

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

به طور کلی هدف پیدا کردن کم هزینه ترین تور برای ملاقات همه شهرها و بازگشت به شهر آغازین حرکت است. مساله فروشنده دوره گرد در شکل ساده و اختصاری با نام TSP شناخته می شود. شکل  زیر یک نمونه جواب از مساله فروشنده دوره گرد که در سال ۱۵۹۱ برای ۱۵ شهر از کشور آمریکا مطرح شد را نشان می دهد که با روش شاخه وحد حل شد.

تصاویر محصول

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

سورس کد حل مسئله فروشنده دوره گرد با الگوریتم ژنتیک در Matlab 2017b نوشته و اجرا شده است این سورس کد توسط تیم پشتیبانی پی استور تست و اجرا شده است. کیفیت محصول حل مسئله فروشنده دوره گرد با الگوریتم ژنتیک توسط پی استور تضمین می شود و محصول دارای نشان تضمین کیفیت پی استور می باشد. برای دانلود محصول آن را خریداری فرمایید به محض خرید لینک دانلود در دسترس خواهد بود.