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

در این بخش سورس کد حل مسئله فروشنده دوره گرد با الگوریتم جستجوی هارمونی در پایتون قرار داده شده است. الگوریتم جستجوی هارمونی 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 های مختلفی را همراه با امکان آپدیتشان نصب می‌کند.

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

سورس کد حل مسئله فروشنده دوره گرد با الگوریتم جستجوی هارمونی در پایتون عنوان اثری است که در این پست به آن پرداخته شده است. این اثر در پایتون ۳.۱۰ برنامه نویسی شده و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است.