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

در این بخش سورس کد حل مسئله فروشنده دوره گرد با الگوریتم جستجوی هارمونی در متلب قرار داده شده است. الگوریتم جستجوی هارمونی Harmony Search یا HS، یکی از الگوریتم های متاهیوریستیک مبتنی بر طبیعت است که با استفاده از فرآیند موسیقایی جستجو، برای حالت کامل هماهنگی، مفهوم‌سازی شده است. از این الگوریتم می توان برای حل مسئله فروشنده دوره گرد Traveling Salesman Problem یا همان TSP استفاده کرد.

الگوریتم جستجوی هارمونی Harmony Search

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

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

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

مسئله فروشنده دوره گرد Traveling Salesman Problem یک مسئله مهم ریاضیاتی است. در مسئله فروشنده دوره گرد تعدادی شهر داریم که فروشنده دوره گرد باید از یک از شهر شروع کند و به هر کدام از این شهر ها فقط یک بار سفر کند و دوباره به شهر اول برگردد و هدف کمینه کردن پیمایش شهر ها (طول کل مسیر پیمایش) است.

از نگاه ریاضی در واقع مسئله TSP را می توان به عنوان یک گراف وزن دار بدون جهت در نظر گرفت، که در آن شهرها رأس ها و مسیر ها یال های گراف هستند و فاصله یک مسیر وزن یال است. در این گراف، به حداقل رساندن شروع و پایان در یک رأس مشخص پس از بازدید دقیق از یک رأس است. مسئله TSP جزو مسائل NP-Hard است یعنی اگر تعداد شهرها از یک حدی زیادتر باشد، تعداد جواب های احتمالی برای حل آن دارای فضا و بعد زیادی است. تعداد جواب های احتمالی برای n شهر در مسئله فروشنده دوره گرد !(n-1)1/2 است یعنی برای 10 شهر باید از بین !(9)1/2 حالت که 181400 است دنبال یک جواب باشیم؛ بنابراین بررسی تمامی این جایگشت ها حتی برای شهر های کمتر هم مشکل خواهد بود به همین خاطر مسئله فروشنده دوره گرد را جزو مسائل NP-Hard حساب می کنند. برای حل این گونه مسائل می توان از الگوریتم های متاهیوریستیک یا فرا ابتکاری استفاده کرد.

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

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

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

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

تصاویر خروجی حل مسئله

ویدئوی نحوه اجرا

درباره سورس کد

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

مباحث مرتبط با الگوریتم جستجوی هارمونی

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