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

در این بخش حل مسئله فروشنده دوره گرد با الگوریتم SA در پایتون قرار داده شده است. مسئله فروشنده دوره گرد از جمله مسائل ریاضیات می باشد که قابل حل به روش‌های مختلفی است. اما از جمله مهم ترین روش هایی که می توان با استفاده از آن مسائل بهینه سازی نظیر مسئله فروشنده دوره گرد یا Travelling salesman problem که به اختصار TSP نامیده می شود را حل نمود، الگوریتم های فرا ابتکاری یا متاهیورستیک است. الگوریتم شبیه سازی تبرید یا SA یکی از الگوریتم های متاهیورستیک است که با استفاده از آن می توان مسئله فروشنده دوره گرد را حل نمود. در ادامه درمورد حل مسئله فروشنده دوره گرد با الگوریتم SA در پایتون بیشتر صحبت خواهیم کرد.

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

مسئله فروشنده دوره گرد یکی از مسائل مهم در زمینه بهینه سازی و علوم کامپیوتر محسوب می شود که این مسئله را با روش های مختلفی می توان پیاده سازی و حل نمود. تاریخچه پیدایش این مسئله مشخص نیست اما به طور کلی این مسئله برای اولین بار در کتاب های ریاضیات پیدا شده است.

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

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

الگوریتم تبرید شبیه سازی شده یا Simulated annealing

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

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

این روش به طور مستقل توسط اسکات کرک پاتریک، سی دانیل ژلات و ماریو پی وکی در سال 1983 و توسط ولادو سرنو در سال 1985 توصیف شد. SA احتمالاً پرکاربردترین روش فرااکتشافی در مسئله بهینه سازی ترکیبی است. این انگیزه با تشابه بین بازپخت فیزیکی فلزات و روند جستجو برای راه حل بهینه در مسئله بهینه سازی ترکیبی بدست آمده است. هدف اصلی روش SA فرار از بهینه های محلی و به تأخیر انداختن همگرایی است.

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

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

مسئله فروشنده دوره گرد یا TSP قابل حل با الگوریتم های فرا ابتکاری می باشد که یکی از آن ها الگوریتم تبرید شبیه سازی شده می باشد. این سورس کد دارای 1 فایل اصلی SA.py می باشد که در برگیرنده کدهای اصلی و فراخوانی ها می باشد. در یک پوشه به نام data نیز مقادیر و هزینه های شهرها در داخل فایل های txt قرار گرفته اند که در خط زیر می توانید نام داده مدنظر خود را وارد کنید.

with open('./data/chn14.txt') as f:

برای مثال در این مورد فایل chn14.txt مدنظر قرار داده شده است. جهت مشاهده خروجی برنامه به ادامه توضیحات محصول مراجعه نمایید. بخشی از سورس کد در زیر آورده شده است.

import random as rd
import numpy as np
import matplotlib.pyplot as plt 

#__ City Class
class City:
    def __init__(self,num, x, y):
        self.num=num
        self.x = x
        self.y = y
    def distance(self, city):
        xDis = abs(self.x - city.x)
        yDis = abs(self.y - city.y)
        distance = np.sqrt((xDis ** 2) + (yDis ** 2))
        return distance
    def __repr__(self):
        return "(" + str(self.x) + "," + str(self.y) + ")"

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

ویدئوی معرفی

***  توجه  ***

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

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

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

مباحث مرتبط با الگوریتم SA

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

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