ساختار الگوریتم کلونی مورچگان (ACO)


ساختار الگوریتم کلونی مورچگان (ACO)

الگوریتم کلونی مورچگان در رتبه دوم پر اهمیت‌ترین الگوریتم‌ها، در دسته الگوریتم‌های تکاملی قرار می‌گیرد. رفتار بیولوژیکی مورچه برای پیدا کردن غذا نقطه شروع شبیه سازی مصنوعی ما است. با رادوو همراه باشید با بخش آموزش الگوریتم‌های تکاملی.


الگوریتم‌های تکاملی یک جهش در زمینه هوش مصنوعی به حساب می‌آید. الگوریتم ژنتیک، اولین الگوریتم تکاملی ارائه شده بود. ژنتیک در کنار قدیمی‌ترین بودن همچنان به عنوان پیشتاز تکامل نیز به حساب می‌آید.

الگوریتم کلونی مورچگان یا (ACO) در رتبه دوم از نظر مصرف قرار دارد. بهتر است ساختار آن را با تشریح مدل بیولوژیکی آغاز کنیم.

مورچه‌ها به مانند پرندگان، زنبور عسل و .. برای پیدا کردن غذا به صورت گروهی حرکت می‌کنند. اصطلاحا به این نوع رفتار هوش جمعی گفته می‌شود. هوش جمعی به این منظور است که تمام تصمیمات مسیریابی و جمع آوری آذوقه از یک مورچه به مورچه دیگر انتقال پیدا می‌کند. تعداد مورچه‌ها در یک کلونی می‌تواند به 30 میلیون برسد!! و هدف تک تک اعضای آن به بقای کلونی باز ‌می‌گردد. غیر از پیدا کردن غذا، تقسیم کار، ساماندهی گورستان و مراقبت از فرزندان نیز در بین کلونی مورچگان مبحثی رایج است.

 

رفتار جستجو گرانه مورچه‌ها

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

حال با توضیحات بالا یک سوال مهم پیش می‌آید: فرض کنید یک مورچه که به عنوان اولین مورچه است، در مسیری حرکت کرده و بقیه مورچه‌ها نیز به دنبال او راه افتاده‌اند. اگر در مسیر حرکت آن غذا پیدا نشود، آن زمان تصمیم چیست؟ طبق این فرضیه هیچ وقت مسیرهای جدید اکتشاف نمی‌شوند و حرکت به یک حلقه بدون پایان تبدیل می‌شود.!

شاید جالب باشد بدانید که بعضی از مورچه‌ها در واقع جوانان اکتشاف‌گری هستند که توجهی به میزان فرومون نمی‌کنند و اهمیتی برای‌شان ندارد که دیگران از چه مسیری رفتند. البته شاید این اتفاق ناشی از هوش کم‌شان باشد.


می‌خواهم با یک مثال ساده کاملا کل حرف‌هایم را برای‌تان روشن کنم.

فرض کنید در ماه محرم هستیم، شما برای نذری گرفتن با اتومبیل‌تان شروع به حرکت در سطح شهر می‌کنید، (همان اولین حرکت تصادفی مورچه).

نقطه‌ای در شهر را پیدا می‌کنید که در حال پخش کردن شربت و کیک هستند، تلفن همراه خود را در می‌آورید و شروع به زنگ زدن به دوستان‌تان می‌کنید. برای اینکه آن‌ها را به محل نذری شربت و کیک دعوت کنید به آن‌ها آدرس دقیق می‌دهید که مثلا از اتوبان X خروجی خیابان Y  بیا و به محل می‌رسی. (این مرحله به مانند پخش کردن فرومون است).

حال یکی از دوستان شما به کرو