حل مسائل گسسته توسط الگوریتم های تکاملی – مسیریابی خودرو

حل مسائل گسسته توسط الگوریتم های تکاملی - مسیریابی خودرو

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

سوال یکی از مخاطبین به این صورت بود:

“باسلام

لطف کنید برای شبکه هم توضیحاتی بیان کنید چون پایان نامه بنده راجع به شبکه می باشد، و روی مقاله ایی که در رابطه با این موضوع می باشد دارم کار میکنم و اگر امکانش وجود داشته باشد، تابع هدف و قیود آن را همراه با کد های آن ارائه دهید.”

این سوال را با مدرس در میان گذاشتیم؛ ایشان پاسخ را ارائه نموده اند:

با سلام؛

مسأله مسیریابی خودرو یا VRP یکی از مسائل جایگشتی و ترکیبی است و می بایست پاسخ آن، به صورت جایگشتی کد شود. به این منظور، می توان از روش های مختلفی استفاده کرد و الزاما نیازی به الگوریتم گسسته نیست.

از نظر ریاضی، VRP بسیار شبیه به مسأله فروشنده دوره گرد یا TSP است و عملا می توان با تغییرات کوچک در ساختار برنامه ای که TSP را حل می کند، آن را برای حل VRP نیز استفاده نمود.

در خصوص روش های مختلف کدینگ پاسخ برای مسأله TSP، با استفاده از انواع الگوریتم های پیوسته و گسسته، این فیلم را به شما توصیه می کنیم. این آموزش به صورت رایگان در فرادرس ارائه شده است و می توانید آن را دانلود کنید:

دانلود رایگان آموزش انواع روش های کدینگ مسأله فروشنده دوره گرد

اما اگر می خواهید از PSO برای حل مسائل گسسته یا عدد صحیح استفاده نمایید (هر چند در مورد VRP و TSP الزاما نیازی به این کار نیست)، می توانید از راهکاری که در یک آموزش رایگان دیگر ارائه شده است، استفاده نمایید. برای دانلود مشاهده آموزش حل مسائل گسسته با استفاده از الگوریتم ازدحام ذرات یا PSO، لینک زیر را مشاهده نمایید:

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

در فیلم آموزشی دیگری، با استفاده از الگوریتم PSO، مسأله فروشنده دوره گرد یا TSP حل شده است. همان طور که پیش از این نیز گفته شد، می توان با تغییرات جزئی در این برنامه، آن را برای حل مسأله VRP استفاده نمود. چرا که از نظر ریاضی، VRP توسعه ای از مسأله TSP است و به راحتی می توان راه حل عمومی یک مسأله VRP را، به صورت یک جایگشت نشان داد؛ یعنی همان ساختاری که برای توصیف راه حل TSP قابل استفاده است. برای مشاهده آموزش حل مسأله فروشنده دوره گرد با استفاده از PSO، لینک زیر را مشاهده نمایید:

آموزش حل مسأله فروشنده دوره گرد با الگوریتم PSO

به عنوان یک مثال دیگر از کاربرد یک الگوریتم پیوسته برای حل مسائل جایگشتی (که شامل گستره وسیعی از مسائل معروف می شود)، می توان به آموزش حل مسائل جایشگتی با استفاده از الگوریتم رقابت استعماری (ICA) اشاره نمود، که آن هم الگوریتمی پیوسته و مشابه با PSO است. آموزش زیر را در نظر بگیرید:

آموزش حل مسائل جایگشتی با الگوریتم رقابت استعماری

در این آموزش، حل چهار مسأله جایگشتی معروف به صورت گام به گام با الگوریتم رقابت استعماری آموزش داده شده است. فهرست این چهار مسأله در ادامه آمده است:

مسأله فروشنده دوره گرد یا Traveling Salesman Problem (به اختصار TSP) که به جرأت می توان گفت که معروف ترین مسأله بهینه سازی جایگشتی است؛

مسأله تخصیص درجه دو یا Quadratic Assignment Problem (به اختصار QAP) که دارای کاربردهای وسیعی در علوم مهندسی است؛

مسأله n وزیر (ملکه) یا n-Queens Problem (به اختصار nQP) که یک مسأله کلاسیک در بهینه سازی و تحقیق در عملیات است؛

مسأله زمان بندی پایه یا Basic Scheduling Problem که مادر تمام مسائل زمان بندی است و قطعا شیوه حل آن، می تواند الگوی مناسبی برای حل سایر انواع مسائل زمان بندی باشد.

در نهایت، فهرست آموزش ها را، با معرفی آموزش حل مسأله VRP با استفاده از الگوریتم شبیه سازی تبرید (SA) کامل می کنیم. مستقل از این که شما می خواهید از چه الگوریتمی برای حل مسأله VRP استفاده کنید، پیاده سازی مدل مسأله، تابع هدف و قیدهای آن، می تواند کاری دشوار باشد که در این آموزش، به صورت بسیار کاملی، برای مسأله VRP پایه، VRP با فرض محدودیت ظرفیت برای خودروها و همین طور VRP با پنجره زمانی (یا TWVRP) انجام شده است. در نهایت، پس از پیاده سازی مدل، با استفاده از الگوریتم SA این مسأله حل شده است و نتایج بهینه سازی نیز، به صورت آنلاین به همراه اجرای الگوریتم، نمایش داده می شوند.

همان طور که گفته شد، پیاده سازی مدل (قوانین حاکم بر مسأله) و تابع هدف، موضوعی است که وابستگی به نوع الگوریتم مورد استفاده شده ندارد و در اکثر مواقع، سئوالات و مشکلات دانشجویان نیز، به همین مورد بر می گردد. در آموزشی که لینک آن در ادامه آمده است، این سئوالات به صورت کامل برطرف می شوند و مثال هایی روشن، علمی و واقعی از نحوه پیاده سازی VRP، ارائه شده اند:

آموزش حل مسأله VRP

با مشاهده این آموزش ها، به احتمال زیاد شما خواهید توانست که مسأله VRP را نه تنها با الگوریتم PSO، بلکه با هر الگوریتم دیگری که به آن مسلط هستید، پیاده سازی کنید. این همان هدفی است که ما در آموزش های فرادرس مد نظر داشته ایم و امیدواریم که به این هدف رسیده باشیم.

 

مطالب پیشنهادی‎




0 پاسخ

ارسال یک پاسخ

در گفتگو ها شرکت کنید.

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *