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

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

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

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

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

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

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

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

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

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

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

مسئله فروشنده دوره گرد یا TSP قابل حل با الگوریتم‌های فرا ابتکاری می‌باشد که یکی از آن‌ها الگوریتم تبرید شبیه سازی شده می‌باشد. این سورس کد دارای ۱ فایل اصلی 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) + ")"

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

***  توجه  ***

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

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

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