آموزش الگوریتم مورچگان از صفر تا صد

الگوریتم بهینه‌ سازی کلونی مورچه‌ ها ACO -Ant Colony Optimization


یکی از موفق ترین مثال های الگوریتم مورچه ها (ant colony)، الگوریتم بهینه‌ سازی کلونی مورچه‌ ها (Ant Colony Optimization) است که به اختصار ACO نامیده می شود. با توجه به اینکه ACO نسبت به سایر سایر الگوریتم های مورچه ها بیشتر مورد توجه قرار گرفته است، تمرکز ما نیز بیشتر بر روی این الگوریتم است.
الگوریتم ACO از رفتار مربوط به پیدا کردن غذا (foraging) مورچه های الهام گرفته شده است. الگوریتم ACO برای مسئله های بهینه سازی گسسته (discrete) استفاده می شود.
همانطور که در مطلب قبلی بیان کردیم:

این کلونی‌ها و تجمعات دارای یک ساختار اجتماعی فوق العاده هستند.
هر حشره معمولاً یک تنها یک یا چند وظیفه محدود رو انجام می‌ده
انجام کارهای بزرگ و پیچیده توسط این حشرات با کنار هم قرار گرفتن تک تک آنها قابل انجام است. کارهای که هر یک از حشرات به تنهایی نمی‌توانند انجام دهند. در واقع کار گروهی باعث موفقیت آنها در انجام فعالیت‌های بزرگ و پیچیده می‌شود.
همچنین بیان کردیم که ” همانطور که گفتیم رمز موفقیت مورچه‌ها از کار گروهی آنها ناشی می‌شه. مورچه‌ها از طریق stigmergy فعالیت‌های گروهی خودشون رو انجام می‌دن. Stigmergy به این معنا است که مورچه‌ها با یکدیگر به صورت غیر مستقیم ارتباط برقرار میکنن”
در رفتار مربوط به پیدا کردن غذا (foraging)، هر گاه مورچه ها احتمال وجود یک غذا را در یک منطقه بدهند، از یک ماده شیمایی که در بدن شون تولید میکنند برای نشانه گذاری محیط استفاده میکنند تا به سایر مورچه ها بگن که در این منطقه احتمال وجود غذا هست. هر چه این احتمال بیشتر باشد محیط با مقدار بیشتری از ماده شیمیایی نشانه گذاری میکنند. نام این ماده شیمیایی فرمون (pheromones) است.
نکته جالب این است که اکثر مورچه ها کور هستند و چشم ندارد، به همین خاطر برای برقراری ارتباط با یکدیگر از ترشح مواد شیمیایی در محیط اطراف خود استفاده میکنند
دنباله فرمون یا trail pheromone یک از مهم‌ترین انواع فرمون است که گونه های از مورچه ها مانند Lasius niger و Iridomyrmex humilis برای مشخص کردن مسیر غذا تا لانه استفاده میکنند. سایر مورچه ها از این مسیرهای مشخص شده برای رسیدن به غذا استفاده میکنند.

الگوریتم ACO از همین رفتار “به جا گذاشتن فرمون از مسیر لانه تا غذا توسط مورچه‌ها و دنبال کردن مسیر توسط سایر مورچه ها برای رسیدن به غذا” الهام گرفته شده است. شاید این رفتار به ظاهر بسیار ساده باشد اما میتوان مسائل پیچیده ای را با آن حل نمود. در مطالب بعدی چندین نمونه مسئله ساده و پیچیده که با الگوریتم بهینه‌ سازی کلونی مورچه‌ ها قابل حل است را بررسی خواهیم کرد.

منبع (اطلاعات بیشتر)

http://mrmining.ir/2016/11/11/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85-%D8%A8%D9%87%DB%8C%D9%86%D9%87%E2%80%8C-%D8%B3%D8%A7%D8%B2%DB%8C-%DA%A9%D9%84%D9%88%D9%86%DB%8C-%D9%85%D9%88%D8%B1%DA%86%D9%87%E2%80%8C-%D9%87%D8%A7-ac/