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

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

مسئله فروشنده دوره گرد یک مسئله مهم ریاضیاتی است که از بازی همیلتون icosian اقتباس شده است. هدف بازی پیدا کردن یک چرخه همیلتونی در امتداد لبه های یک 12 وجهی است به طوری که از هر راس یک بار بازدید می شود و نقطه پایان آن همان نقطه شروع است. همانطور که قبلاً اشاره شد در مسئله فروشنده دوره گرد تعدادی شهر داریم که فروشنده دوره گرد باید از یک از شهر شروع کند و به هر کدام از این شهر ها فقط یک بار سفر کند و دوباره به شهر اول برگردد و هدف کمینه کردن پیمایش شهر ها (طول کل مسیر پیمایش) است.

از نگاه ریاضی در واقع مسئله TSP را می توان به عنوان یک گراف وزن دار بدون جهت در نظر گرفت، که در آن شهرها رأس ها و مسیر ها یال های گراف هستند و فاصله یک مسیر وزن یال است. در این گراف، به حداقل رساندن شروع و پایان در یک رأس مشخص پس از بازدید دقیق از یک رأس است. مسئله TSP جزو مسائل NP-Hard است یعنی اگر تعداد شهرها از یک حدی زیادتر باشد، تعداد جواب های احتمالی برای حل آن دارای فضا و بعد زیادی است. تعداد جواب های احتمالی برای n شهر در مسئله فروشنده دوره گرد !(n-1)1/2 است یعنی برای 10 شهر باید از بین !(9)1/2 حالت که 181400 است دنبال یک جواب باشیم؛ بنابراین بررسی تمامی این جایگشت ها حتی برای شهر های کمتر هم مشکل خواهد بود به همین خاطر مسئله فروشنده دوره گرد را جزو مسائل NP-Hard حساب می کنند. برای حل این گونه مسائل می توان از الگوریتم های متاهیوریستیک یا فرا ابتکاری استفاده کرد.

الگوریتم بهینه سازی گرگ خاکستری GWO

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

در هر گله یا جمعیت گرگ ها برای شکار کردن ۴ درجه وجود دارد. گرگ های رهبر گروه alpha، گرگ های beta، گرگ های delta و گرگ های omega که یک فضای سلسله مراتبی را در جمعیت به وجود می آورند. هر کدام از گرگ ها با هر سلسله مراتبی، یک جواب بالقوه برای مسئله خواهد بود. در ابتدا برازندگی کلیه جواب ها از کل جمعیت گرگ ها محاسبه می شود و سه جواب برتر به عنوان alpha, beta, delta انتخاب می شود.

در هر تکرار از الگوریتم سه جواب برتر (گرگ های alpha, beta, delta) قابلیت تخمین موقعیت شکار را داشته و این کار را در هر iteration با استفاده از روابط ریاضی انجام می دهند. در هر تکرار بعد از تعیین موقعیت گرگ های alpha, beta, delta، آپدیت موقعیت بقیه جواب ها با تبعیت از آن ها انجام می شود و در پایان تکرارها موقعیت گرگ alpha به عنوان نقطه بهینه یا همان جواب مسئله معرفی می شود.

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

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

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

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

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

#__ 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) + ")"
    

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

#__ Fitness Class   
class Fitness:
    def __init__(self, route):
        self.route = route
        self.distance = 0
        self.fitness= 0.0
    
    def routeDistance(self):
        if self.distance ==0:
            pathDistance = 0
            for i in range(0, len(self.route)):
                fromCity = self.route[i]
                toCity = None
                if i + 1 < len(self.route):
                    toCity = self.route[i + 1]
                else:
                    toCity = self.route[0]
                pathDistance += fromCity.distance(toCity)
                
            self.distance = pathDistance
        return self.distance
    
    def routeFitness(self):
        if self.fitness == 0:
            self.fitness = float(self.routeDistance())
        return self.fitness  

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

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

پیش نمایش

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

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