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

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

مسئله فروشنده دوره گرد Traveling Salesman Problem یا همان TSP یکی از مسائل مهم در مباحث مربوط به ریاضیات، علوم کامپیوتر، مسیریابی و غیره است. در مسئله فروشنده دوره گرد ما با تعدادی شهر مواجه هستیم و یک فروشنده دوره گرد که می خواهد محصولات خود را در هر یک از این شهرها به فروش برساند. هدف پیدا کردن کمترین مسافت طی شده توسط فروشنده دوره گرد است بشرطی که دقیقاً به هر کدام از شهرها یکبار سر بزند. شاید در نگاه اول حل مسئله خیلی آسان باشد ولی مشکل زمانی آغاز می شود که تعداد شهرها زیاد شوند.

در تعداد شهرهای بیشتر، تعداد جایگشت ها بیشتر خواهد شد؛ بنابراین فضا یا بعد مسئله به اندازه ای زیاد خواهد بود که محاسبات از دست انسان برای برآورد کم ترین مسافت یا هزینه خارج خواهد شد. در اینجاست که با استفاده از الگوریتم های مختلف بهینه سازی، فرا ابتکاری و تکاملی بایستی مسئله را حل کرد. مسئله فروشنده دوره گرد را می توان با الگوریتم ژنتیک حل کرد. قبلاً این کار را در متلب انجام داده ایم و آموزش نحوه پیاده سازی TSP با الگوریتم ژنتیک در متلب را توضیح داده ایم و می خواهیم این بار این کار را در پایتون انجام دهیم.

الگوریتم ژنتیک GA

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

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

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

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

برای کدنویسی پیاده سازی حل مسئله فروشنده دوره گرد با الگوریتم ژنتیک در پایتون از IDE محبوب Spyder استفاده شده است. این IDE پس از نصب Anaconda در اختیار شما قرار می گیرد و بسته ها و پکیج های مهم و کاربدری پایتون را در خود دارد. همان طور که در ابتدای مطالب هم عنوان شد این پکیج شامل سورس کد حل مسئله، گزارش کار 12 صفحه ای از روند کدنویسی و یک فیلم آموزشی 40 دقیقه ای می باشد. به طور کلی در فیلم آموزشی به موارد زیر اشاره کرده ایم:

• بیان کلی تئوری و مسئله TSP و الگوریتم ژنتیک GA
• پیاده سازی TSP و ایجاد شهرها در پایتون
• نحوه پیاده سازی Fitness یا تابع شایستگی بر اساس فاصله شهرها
• ایجاد مسیر یا Tour در مسئله
• ایجاد جمعیت اولیه
• تعیین فضای ترکیب Crossover
• تولید اولین نژاد جمعیت
• انجام عملیات تولید مثل
• پیاده‌سازی عملیات جهش Mutation
• تکرار الگوریتم برای ایجاد نسل بعدی
• رسم شهرها و نحوه پیمایش آن ها
• رسم نمودار همگرایی

پیش‌نمایش

درباره پکیج حل TSP با الگوریتم ژنتیک در پایتون

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