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

مقدمه

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

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

تعداد جواب‌های احتمالی برای n شهر در مسئله فروشنده دوره گرد !(n-1)1/2 است یعنی برای ۱۰ شهر باید از بین !(۹)۱/۲ حالت که ۱۸۱۴۰۰ است دنبال یک جواب باشیم؛ بنابراین بررسی تمامی این جایگشت‌ها حتی برای شهرهای کم‌تر هم مشکل خواهد بود به همین خاطر مسئله فروشنده دوره گرد را جزو مسائل NP-Hard حساب می‌کنند. برای حل این گونه مسائل می‌توان از الگوریتم های متاهیوریستیک یا فرا ابتکاری استفاده کرد.

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

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

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

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

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

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

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

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

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

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

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

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