ایمیل خود را وارد و بر روی بچرخون کلیک کنید. (کد تخفیف دریافتی را هنگام ثبت سفارش وارد کنید)
قوانین بازی:
مسئله فروشنده دورهگرد Traveling Salesman Problem که به اختصار TSP یکی از مسائل بسیار مهم و پرکاربرد در علوم کامپیوتر است. در این بخش سورس کد حل مسئله فروشنده دوره گرد با الگوریتم گرگ خاکستری در پایتون Python قرار داده شده است.
برنامهنویس:
هزینه سفارش:
۲۹۶,۰۰۰ تومان قیمت اصلی: ۲۹۶,۰۰۰ تومان بود.۱۱۸,۴۰۰ تومانقیمت فعلی: ۱۱۸,۴۰۰ تومان.
تخصصی و منحصر به فرد بودن این اثر، تضمین کننده بهای محصول نسبت به آثار مشابه است.
مسئله فروشنده دوره گرد یک مسئله مهم ریاضیاتی است که از بازی همیلتون icosian اقتباس شده است. هدف بازی پیدا کردن یک چرخه همیلتونی در امتداد لبههای یک ۱۲ وجهی است به طوری که از هر راس یک بار بازدید میشود و نقطه پایان آن همان نقطه شروع است. همانطور که قبلاً اشاره شد در مسئله فروشنده دوره گرد تعدادی شهر داریم که فروشنده دوره گرد باید از یک از شهر شروع کند و به هر کدام از این شهرها فقط یک بار سفر کند و دوباره به شهر اول برگردد و هدف کمینه کردن پیمایش شهرها (طول کل مسیر پیمایش) است.
از نگاه ریاضی در واقع مسئله TSP را میتوان به عنوان یک گراف وزن دار بدون جهت در نظر گرفت، که در آن شهرها رأسها و مسیرها یالهای گراف هستند و فاصله یک مسیر وزن یال است. در این گراف، به حداقل رساندن شروع و پایان در یک رأس مشخص پس از بازدید دقیق از یک رأس است. مسئله TSP جزو مسائل NP-Hard است یعنی اگر تعداد شهرها از یک حدی زیادتر باشد، تعداد جوابهای احتمالی برای حل آن دارای فضا و بعد زیادی است.
تعداد جوابهای احتمالی برای n شهر در مسئله فروشنده دوره گرد !(n-1)1/2 است یعنی برای ۱۰ شهر باید از بین !(۹)۱/۲ حالت که ۱۸۱۴۰۰ است دنبال یک جواب باشیم؛ بنابراین بررسی تمامی این جایگشتها حتی برای شهرهای کمتر هم مشکل خواهد بود به همین خاطر مسئله فروشنده دوره گرد را جزو مسائل NP-Hard حساب میکنند. برای حل این گونه مسائل میتوان از الگوریتم های متاهیوریستیک یا فرا ابتکاری استفاده کرد.
الگوریتم گرگ خاکستری 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 گرفتن میباشد.
نام اثر: | سورس کد حل مسئله فروشنده دوره گرد با الگوریتم گرگ خاکستری در پایتون |
نوع اثر: | سورس کد |
برنامهنویس: | تیم برنامهنویسی پیاستور |
زبان برنامه نویسی: | پایتون |
ویژگی: | قابل دانلود و ویرایش |
تیم برنامه نویسی پی استور یکی از اولین گروههای تشکیل شده در مجموعه آموزشی پی استور میباشد. این تیم از اساتید مجرب و فارغ التحصیلان رشتههای فنی و مهندسی تشکیل شده که در زمینههای مختلف برنامهنویسی و تهیه سورس کد فعال هستند.
هزینه سفارش:
۲۹۶,۰۰۰ تومان قیمت اصلی: ۲۹۶,۰۰۰ تومان بود.۱۱۸,۴۰۰ تومانقیمت فعلی: ۱۱۸,۴۰۰ تومان.
نظرات
مدیریت و پشتیبانی
نظرات و پیشنهادات خود را با ما در میان بگذارید.