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

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

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

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

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

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

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

از نگاه ریاضی در واقع مسئله TSP را می‌توان به عنوان یک گراف وزن دار بدون جهت در نظر گرفت، که در آن شهرها رأس‌ها و مسیرها یال‌های گراف هستند و فاصله یک مسیر وزن یال است. در این گراف، به حداقل رساندن شروع و پایان در یک رأس مشخص پس از بازدید دقیق از یک رأس است. مسئله TSP جزو مسائل NP-Hard است یعنی اگر تعداد شهرها از یک حدی زیادتر باشد، تعداد جواب‌های احتمالی برای حل آن دارای فضا و بعد زیادی است.

تعداد جواب‌های احتمالی برای n شهر در مسئله فروشنده دوره گرد !(n-1)1/2 است یعنی برای ۱۰ شهر باید از بین !(۹)۱/۲ حالت که ۱۸۱۴۰۰ است دنبال یک جواب باشیم؛ بنابراین بررسی تمامی این جایگشت‌ها حتی برای شهرهای کمتر هم مشکل خواهد بود به همین خاطر مسئله فروشنده دوره گرد را جزو مسائل NP-Hard حساب می‌کنند. برای حل این گونه مسائل می‌توان از الگوریتم‌های متاهیوریستیک یا فرا ابتکاری استفاده کرد.

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

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

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

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

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

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

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