در این بخش سورس کد حل مسئله فروشنده دوره گرد با الگوریتم گرگ خاکستری در پایتون Python قرار داده شده است. مسئله فروشنده دورهگرد Traveling Salesman Problem که به اختصار TSP نامیده می شود یکی از مسائل بسیار مهم و پرکاربرد در علوم کامپیوتر است.
در مسئله TSP تعدادی شهر داریم که فروشنده دوره گرد بایستی از یکی از شهرها شروع کند و به هر کدام از این شهرها فقط یک بار سفر کند و دوباره به شهر اول برگردد و هدف پیمایش شهر ها با کمترین هزینه است. برای حل مسئله فروشنده دوره گرد می توان از الگوریتم های متاهیوریستیک استفاده کرد. در این بخش مسئله فروشنده دوره گرد با استفاده از الگوریتم متاهیوریستیک گرگ خاکستری Gray Wolf Optimizer یا GWO در پایتون حل شده و سورس کد آن موجود می باشد.
تیم برنامه نویسی پی استور یکی از اولین گروههای تشکیل شده در مجموعه آموزشی پی استور میباشد. این تیم از اساتید مجرب و فارغ التحصیلان رشتههای فنی و مهندسی تشکیل شده که در زمینههای مختلف برنامهنویسی و تهیه سورس کد فعال هستند.
مسئله فروشنده دوره گرد 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 گرفتن می باشد.
مباحث مرتبط
اطلاعات تکمیلی محصول
نام محصول: | سورس کد حل مسئله فروشنده دوره گرد با الگوریتم گرگ خاکستری در پایتون |
---|---|
نوع محصول: | سورس کد |
حجم فایل: | 5 کیلو بایت |
فرمت فایل: | zip. |
قابل اجرا در: | Python 3.10 |
مباحث پیشنهادی دیگر
تاریخ انتشار: | 13 آذر ماه 1401 |
---|---|
حجم فایل: | 5 کیلو بایت |
فرمت فایل | zip. |
هماهنگی با: | Python 3.10 |
تضمین کیفیت: | دارای گارانتی 7 روزه بازگشت وجه |
سفارش تدریس: | اطلاعات تکمیلی |
تاکنون 204 نفر این محصول را تهیه کرده اند و 1 نظر برای آن ثبت شده است.
نظرات و دیدگاه ها
قوانین ثبت دیدگاه
- لطفاً دیدگاه های خود را فارسی تایپ کنید.
- دیدگاه های نامرتبط به مطلب تایید نخواهد شد.
- از درج دیدگاه های تکراری پرهیز نمایید.
- سوالات تخصصی خودتان را از طریق تیکت پشتیبانی مطرح کنید.
قیمت 59,000 تومان
تاریخ انتشار: | 13 آذر ماه 1401 |
---|---|
حجم فایل: | 5 کیلو بایت |
فرمت فایل | zip. |
هماهنگی با: | Python 3.10 |
تضمین کیفیت: | دارای گارانتی 7 روزه بازگشت وجه |
سفارش تدریس: | اطلاعات تکمیلی |
1 بازخورد (مشاهده نظرات)
قیمت: 59,000 تومان
مدیریت و پشتیبانی
نظرات و پیشنهادات خود را با ما در میان بگذارید.