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

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

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

الگوریتم های فرا ابتکاری مبتنی بر طبیعت فراوانی وجود دارند که از روند فعالیت ها در طبیعت الهام گرفته می شوند، این الگوریتم ها از جمله الگوریتم هایی هستند که در حل مسائل بهینه سازی بسیار کاربرد دارند. الگوریتم جستجوی هارمونی نیز از سری الگوریتم های فرا ابتکاری (Meta Heuristic algorithms) مبتنی بر طبیعت (الگوریتم های NI) بوده و با استفاده از فرآیند موسیقایی جستجو، برای حالت کامل هماهنگی، مفهوم‌سازی شده است.

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

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

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

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

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

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

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

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

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

***  توجه  ***

قبل از اجرای سورس کد الگوریتم در محیط پایتون حتماً از نصب پکیج های مورد استفاده در این سورس کد در Python خود مطمئن شوید پکیج های استفاده شده در این سورس کد numpy و matplotlib می باشد که اولی پکیج مربوط به استفاده از آرایه ها و ماتریس ها در پایتون و دومی مربوط به عملیات های نموداری و Plot گرفتن می باشد. پیشنهاد ما نصب اسپایدر (Spyder (Python 3.7 می باشد که هم پایتون و پکیج های مختلف و هم IDE های مختلفی را همراه با امکان آپدیتشان نصب می کند.

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

سورس کد حل مسئله فروشنده دوره گرد با الگوریتم جستجوی هارمونی در پایتون عنوان محصولی است که در این پست به آن پرداخته شده است. محصول در پایتون 3.10 برنامه نویسی شده و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است. قبل از اجرای سورس کد در محیط پایتون حتماً از نصب پکیج های مورد استفاده در این سورس کد در Python خود مطمئن شوید. پکیج های استفاده شده در این سورس کد numpy و matplotlib می باشد که اولی پکیج مربوط به استفاده از آرایه ها و ماتریس ها در پایتون و دومی مربوط به عملیات های نموداری و Plot گرفتن می باشد.