الگوریتم‌های تکاملی یک جهش در زمینه هوش مصنوعی به حساب می‌آید. الگوریتم ژنتیک، اولین الگوریتم تکاملی ارائه شده بود. ژنتیک در کنار قدیمی‌ترین بودن همچنان به عنوان پیشتاز تکامل نیز به حساب می‌آید.
الگوریتم کلونی مورچگان یا (ACO) در رتبه دوم از نظر مصرف قرار دارد. بهتر است ساختار آن را با تشریح مدل بیولوژیکی آغاز کنیم.
مورچه‌ها به مانند پرندگان، زنبور عسل و .. برای پیدا کردن غذا به صورت گروهی حرکت می‌کنند. اصطلاحا به این نوع رفتار هوش جمعی گفته می‌شود. هوش جمعی به این منظور است که تمام تصمیمات مسیریابی و جمع آوری آذوقه از یک مورچه به مورچه دیگر انتقال پیدا می‌کند. تعداد مورچه‌ها در یک کلونی می‌تواند به 30 میلیون برسد!! و هدف تک تک اعضای آن به بقای کلونی باز می‌گردد. غیر از پیدا کردن غذا، تقسیم کار، ساماندهی گورستان و مراقبت از فرزندان نیز در بین کلونی مورچگان مبحثی رایج است.
رفتار جستجو گرانه مورچه‌ها
جالب است بدانید که مورچه‌ها موجوداتی کور، بی‌حافظه و بسیار کم هوش هستند. ولی با این حال همیشه بهینه‌ترین و کوتاه‌ترین مسیر از لانه تا محل غذا را پیدا می‌کنند. ارتباط این مورچه‌ها با یکدیگر از طریق ماده شیمیایی فرومون است. زمانی که مورچه از یک مسیر حرکت می‌کند بر روی زمین فرومون ترشح می‌کند و این باعث می‌شود که مورچه‌های بعدی به دنبال او حرکت کنند. فرومون ها دارای غلظت هستند که طی واحد زمان تبخیر می‌شوند، پس هر چه غلظت فرومون بیشتر باشد مورچه می‌فهمد که این مسیر جدیدتر است. به نحوی می‌توان این غلظت را به عنوان یک فیدبک در نظر گرفت که هر چه غلیظ‌تر باشد امتیاز بالاتری دارد.
حال با توضیحات بالا یک سوال مهم پیش می‌آید: فرض کنید یک مورچه که به عنوان اولین مورچه است، در مسیری حرکت کرده و بقیه مورچه‌ها نیز به دنبال او راه افتاده‌اند. اگر در مسیر حرکت آن غذا پیدا نشود، آن زمان تصمیم چیست؟ طبق این فرضیه هیچ وقت مسیرهای جدید اکتشاف نمی‌شوند و حرکت به یک حلقه بدون پایان تبدیل می‌شود.!
شاید جالب باشد بدانید که بعضی از مورچه‌ها در واقع جوانان اکتشاف‌گری هستند که توجهی به میزان فرومون نمی‌کنند و اهمیتی برای‌شان ندارد که دیگران از چه مسیری رفتند. البته شاید این اتفاق ناشی از هوش کم‌شان باشد.
می‌خواهم با یک مثال ساده کاملا کل حرف‌هایم را برای‌تان روشن کنم.
فرض کنید در ماه محرم هستیم، شما برای نذری گرفتن با اتومبیل‌تان شروع به حرکت در سطح شهر می‌کنید، (همان اولین حرکت تصادفی مورچه).
نقطه‌ای در شهر را پیدا می‌کنید که در حال پخش کردن شربت و کیک هستند، تلفن همراه خود را در می‌آورید و شروع به زنگ زدن به دوستان‌تان می‌کنید. برای اینکه آن‌ها را به محل نذری شربت و کیک دعوت کنید به آن‌ها آدرس دقیق می‌دهید که مثلا از اتوبان X خروجی خیابان Y بیا و به محل می‌رسی. (این مرحله به مانند پخش کردن فرومون است).
حال یکی از دوستان شما به کروکی و مسیری که به آن معرفی کردید گوش نمی‌دهد و به انتخاب خود از مسیر دیگری حرکت می‌کند. در راه محلی را پیدا می‌کند که در حال پخش کردن غذا هستند. سریعا تلفن خود را در می‌آورد و با شما و دوستان‌تان تماس می‌گیرد که به محل او بی‌آیید. این به آن معنا است که میزان اهمیت فرومون شخص دوم از فرومون شما بیشتر می‌شود و همگی به سمت فردی که به جای شربت غذا پیدا کرده است کشیده می‌شوند.
الگوريتم های بهینه سازی کلونی مورچگان
تفاوت مورچه‌های واقعی و مورچه‌های مصنوعی
- حالت درونی: حافظه‌ای از فعاليت های قبلی مورچه‌ها (در صورتی که در مورچه‌های واقعی این نوع حافظه وجود ندارد).
- فرومون مصنوعی: تابعي از کيفيت پاسخ پيدا شده.
- موانع مصنوعی: تغییر دادن جزئیات مسئله برای بررسی الگوریتم و رسیدن به جواب‌های متنوع.
- حیات در محیط گسسته: مورچه‌های واقعی نمی‌توانند جدا از کلونی به حیات خود ادامه دهند.
مدل تصادفی:
احتمال اینکه مورچه بعدی مسیر A را انتخاب کند:
nA(t) و nB(t) تعداد مورچه هایی که در زمان t در مسیر A و B قرار دارند.
c: درجه جذب برای یک مسیر ناشناخته هر چه c بزرگتر باشد به معنی مقدار فرومون بیشتر برای عدم انتخاب مسیر تصادفی است.
a: بایاس به سمت فرومون به جا مانده در روند تصمیم گیری.
ساختار کلی الگوریتم کلونی مورچگان را باهم بررسی کردیم. در طی چند سال گذشته بهینه‌سازی‌های زیادی بر روی این الگوریتم انجام شد، که از انواع آن‌ها می‌توان به الگوریتم‌های زیر اشاره کرد:
SACO: Simple Ant Colony Optimization
ACOA: Ant Colony Optimization Algorithms
AS: Ant System
Elitist AS: Elitist Ant System
ACS: Ant Colony System
Max-Min AS
و ...
امیدوارم از آموزش اولین بخش رایانش تکاملی لذت برده باشید، با رادوو و ادامه الگوریتم‌های تکاملی همراه باشید.