الگوریتم کلونی مورچه
« کلونی مورچه »
مقدمه
کلونی مورچه ها و به طور کلی جوامع حشرات اجتماعی ،سیستم های گسترده ای هستند که علی رغم سادگی ، ساختار اجتماعی کاملاٌ سازمان یافته ای را عرضه می کنند . از طریق این سازماندهی کلونی مورچگان می تواند وظایف پیچیده ای را انجام دهد که در برخی موارد فراتر از توانایی های یک مورچه است .
الهام از طبیعت
- حوزه الگوریتم های مورچه مدل هایی را مطالعه می کند که از مطالعات رفتارهای واقعی مورچه ها ناشی می شود و از این مدل ها به عنوان منبع انگیزشی برای طراحی الگوریتم های جدید به منظور حل مسائل بهینه سازی و مسائل کنترل توزیع شده (Distributed control) استفاده می کند
- آذوقه جویی، تقسیم کار و مشارکت در حمل و نقل ، مثال هایی از این موارد هستند
- یکی از موفق ترین مثال های الگوریتم های مورچه به بهینه سازی از طریق کلونی مورچه یا ACO شهرت دارد
- ACO که برای حل مسائل بهینه سازی گسسته کاربرد دارد، از رفتار جمع آوری آذوقه مورچه ها الهام گرفته شده است
رفتار کاوشگرایانه مورچه ها و بهینه سازی
قوه بینایی بسیاری از گونه های مورچه بسیار ابتدایی و محدود است و حتی برخی از انواع آن ها کاملاً نابینا هستند اما کوتاه ترین مسیر رفت و برگشت از خانه تا غذا را پیدا می کنند
در حقیقت نتیجه تحقیقات اخیر در مورد رفتار مورچه ها این بود که بیشترین ارتباط بین مورچه ها و یا میان هریک از آن ها و محیط اطرافشان ، با استفاده از مواد شیمیایی تولید شده توسط مورچه ها به نام فرمون (Pheromone) صورت می گیرد
واژه استیگمرجی توسط گراس برای تشریح نوعی ارتباط غیر مستقیم از طریق تغییراتی که روی محیط اطراف گذاشته می شود استفاده می گردد، معرفی شد. وی این رفتار را از روی موریانه های کارگر مشاهده کرد
تاریخچه
الگوریتم مورچگان اولین بار در سال ۱۹۹۱ توسط مارکو دوریگو (Dorigo) برای حل مسائل بهینه سازی مشکلی مانند مسأله فروشنده دوره گرد Traveling) (Sales Person ارائه شد .
رفتار باقی گذاردن و تعقیب رد پا (Trail Pheromone) که مورچه از مواد شیمیایی به جا مانده از سایر مورچه ها تأثیر می گیرد، منشأ پیدایش ACO شد .
آزمایشات پل دو راهه
یکی از آزمایشات درخشانی که توسط دنوبورگ و همکارانش طراحی و اجرا شد ، اتصال لانه گونه ای از مورچه های آرژانتینی به نام آی .هیومیلی توسط یک پل دوراهه به منبع آذوقه بود
آن ها آزمایشات خود را با طول پل های مساوی و نامساوی انجام دادند
پل های مساوی
نتایج آزمایش پل های مساوی(آزمایش اول)
نتیجه این بود که تمام مورچه ها به سمت یک شاخه همگرا می شوند
این مسئله بدین علت رخ می دهد که در ابتدای آزمایش در هیچ یک از پل ها فرومونی وجود ندارد بنابراین مورچه ها با احتمال تقریباً برابر هر دو پل را انتخاب می کنند
اما به دلیل نوسانات تصادفی ، تعداد بیشتری مورچه ها یکی از شاخه ها را بیشتر از دیگری برمی گزینند
پل های نامساوی
نتایج آزمایش پل های نا مساوی(آزمایش دوم)
در بیشتر آزمایشات مورچه ها پس از گذشت مدتی شاخه کوتاه تر را انتخاب کردند
با توجه به مقدار فرمون بیشتری که در شاخه کوتاه تر وجود دارد شاخه کوتاه تر را برمی گزینند
بنابراین فرمون به دلیل فرایند اتوکاتالیزور( بازخورد مثبت) روی شاخه کوتاه تر که توسط همه مورچه ها انتخاب می شود سریع تر انباشته می گردد
عبور مورچه‌هاي بيشتر از مسيرهاي كوتاه‌تر آزمايش پل با مسيرهاي با طول متفاوت
کشف مسیر
به طور جالب توجهی مشاهده می شود که حتی زمانی که طول شاخه بلند تر دو برابر شاخه کوتاه تر است ، تمام مورچه ها از مسیر کوتاه تر استفاده نمی کنند. بلکه درصد کمی ( مثلاً ۱۰%) از مورچه ها ممکن است از شاخه بلند تر بگذرند. این عمل مورچه ها کشف مسیر نامیده می شود
نکته
جالب است بدانیم که وقتی مسیر جدید و کوتاه تری بین لانه و آذوقه پس از مدتی در اختیار کلونی مورچه قرر داده شود با گذشت زمان باز هم مورچه ها شاخه کوتاه تر را انتخاب می کنند چون تبخیر کند فرمون به کلونی مورچه ها اجازه می دهد تا مسیر نیمه بهینه ای که به سمت ان همگرا شده اند را فراموش و مسیر جدید و کوتاه تر را کشف کنند