حل مسئله فروشنده دوره گرد(TSP) با الگوریتم کلونی مورچه(ACO)
در این پست یک مساله واقعی مبتنی بر مساله فروشنده دوره گرد را با الگوریتم کلونی مورچگان حل می نماییم. برای حل آن از نرم افزار متلب(Matlab) استفاده کرده ایم.
تعریف مسئله
فرض کنید می خواهیم برنامه یک سفر را بچینیم. فاصله شهرها با یکدیگر(به کیلومتر) و جاذبه گردشگری هر شهر (امتیازی بین ۱ تا ۱۰) را در اختیار داریم. همچنین، ۳۰۰ لیتر بنزین داریم و خودرویی در اختیار است که برای هر ۱۰۰ کیلومتر مسافت، ۴ لیتر بنزین مصرف میکند. می خواهیم از شهر x حرکت کنیم و با بازید از پر جاذبه ترین شهرها، مجددا به شهر x برگردیم. به عبارت دیگر، در هر قسمت از مسیر، با توجه به میزان بنزین باقی مانده، باید مقدار بنزین مورد نیاز تا رسیدن به شهر مبدا را در نظر بگیریم و در راه نمانیم. دیتاست مورد نیاز یعنی ماتریس فاصله ها و جاذبه های گردشگری شهرها در پروژه موجود است و استفاده خواهیم کرد.
برای حل این مسئله از هر الگوریتم ابتکاری می توان استفاده نمود ما برای حل آن، از الگوریتم کلونی مورچه که برای این مسئله مناسب تر است استفاده کرده ایم.
الگوریتم کلونی مورچه(Ant colony optimization algorithms)
بهینهسازی کلونی مورچهها (ACO) یک تکنیک جستجوی تصادفی تکراری است که از رفتار کلونی مورچه های واقعی برای جستجوی غذا الهام گرفته شده است. مورچه ها در حین راه رفتن بین کلونی خود و منبع غذایی، فرمون ها را در امتداد مسیرهایی که حرکت می کنند، به جا می گذارند. سطح فرمون در مسیرها با عبور تعداد مورچه ها افزایش می یابد و با تبخیر فرمون کاهش می یابد. با گذشت زمان، مسیرهای کوتاه تر، شدت فرمون بیشتری را جمع می کنند. سپس مورچه ها می توانند از فرمون ها برای شناسایی مسیرهای کوتاه تر به منبع غذا استفاده کنند. در نتیجه یک بازخورد مثبت و مکانیسم اتوکاتالیستی مبتنی بر فرمون شکل میگیرد.
برای اولین بار دوریگو از این مکانیزم برای حل مسئله فروشنده دوره گرد استفاده نمود و یک الگوریتم بهینه سازی بنام ACO ارائه داد. شما می توانید از لینک زیر مقاله پایه یک مقاله متناسب با همین مسئله را که ما نیز از آن ایده گرفتیم ببینید:
An ant colony optimization algorithm for the Multiple Traveling Salesmen Problem
کد متلب این پروژه به اضافه فایل های لازم و داکیومنت آن را از لینک زیر می توانید دانلود نمایید:
ACO Matlab Codes for TSP
قیمت: ۲۰۰۰۰۰ تومان
همچنین فیلم توضیحات پروژه و نحوه اجرای آن در متلب را در ادامه می توانید مشاهده کنید: