در ادامه تشریح الگوریتم‌های بهینه سازی ، الگوریتم کلونی مورچگان را شرح خواهیم داد. این الگوریتم که برگردان Ant Colony Optimization یا به اختصار ACO است یکی از ده ها الگوریتم مختلف بهینه سازی است که در سالهای اخیر در رشته های گوناگون برای بهینه سازی به کار رفته اند. الگوریتم کلونی مورچگان در ابتدا بوسیله آقایان Dorigo, Maniezzo و Colorni بعنوان استعاره‌ای برای حل مسائل ترکیبی دشوار در سال ۱۹۹۱ ارائه گردید.
اساس الگوریتم کلونی مورچگان یا Ant colony optimization (ACO)
الگوریتم کلونی مورچگان یا ACO روشی است بر پایه‌ی قابلیت مورچه‌ها در پیدا کردن کوتاه‌ترین مسیر از لانه به یک منبع غذایی. یک مورچه مسیرهای گوناگونی را طی می‌کند تا سرانجام به مقصد که همان منبع غذاست برسد. مورچه‌ها در هنگام دنبال کردن یک مسیر، یک ترکیب ارگانیک (Organic) که فرومون (Pheromone) نامیده می‌شود از خود بجای می‌گذارند. مورچه‌های دیگر با دنبال کردن بوی این ماده، مسیر را دنبال می‌کنند. با انتشار فرومون مورچه‌ها مسیری را که پیموده‌اند علامت گذاری می‌کنند. در طول زمان و درحالیکه تعداد عبور مورچه‌ها افزایش می‌یابد ، تمرکز فرومون در محیط براساس اینکه مورچه‌ها به تدریج کوتاه‌ترین مسیر را بین سایر مسیرها پیدا می‌کنند، تغییر خواهد کرد.
بررسی دقیق‌تر الگوریتم کلونی مورچگان ACO با آزمایش پل دوتایی
مشهورترین آزمایش پایش کاوش مورچه‌ها ، “آزمایش پل دوتایی” یا Double Bridge Experiment است. این آزمایش توسط Deneubourg و همکارانش انجام شد. آنها از یک پل دوتایی برای اتصال لانه‌ی مورچه‌ها و منبع غذایی استفاده کردند. سپس انتشار فرومون از مورچه‌ها و تاثیر آن بر کاوش غذا در آنها را مورد بررسی قرار دادند. دو مسیر را در نظر بگیرید. یکی بلند و دیگری کوتاه که لانه را به منبع غذا متصل می‌کنند. در ابتدا مورچه‌ها هر دو مسیر را انتخاب می‌کنند. اما بعد از مدتی تمامی مورچه‌ها مسیر کوتاه‌تر را انتخاب خواهند کرد. در این آزمایش در مرحله نخست، هیچ کدام از مسیرها دارای فرومون نبودند. بنابراین مورچه‌ها هیچ مرجعی برای انتخاب نداشتند. پس هیچ تعصبی نسبت به هیچ مسیری نیز وجود نداشت. در نتیجه مورچه‌ها تنها به طور تصادفی مسیر را انتخاب کردند. بنابراین احتمال انتخاب هریک از دو مسیر مقداری برابر بود. هرچند مورچه‌ها با انتخاب مسیر کوتاه‌تر زودتر به مقصد می‌رسند و در نتیجه زودتر باز خواهند گشت. دفعه‌ی بعدی ، آنها فرومون را روی مسیر کوتاه‌تر پخش می‌کنند. این بدین معناست که در طی گذشت زمانی اندک، در مسیر کوتاه‌تر مقدار فرومون بیشتری خواهد بود. با گذشت زمان، مقدار تجمعی فرومون در مسیر کوتاه‌تر نسبت به مسیر بلندتر بیشتر و بیشتر می‌گردد. و مورچه‌ها مسیر کوتاه‌تر را انتخاب خواهند کرد.
با الهام از این آزمایش ما می توانیم شاخصه‌های مورچه‌های واقعی را مدلسازی کنیم. که الگوریتم کلونی مورچگان فعلی براساس این رفتار گروهی مورچه‌ها برای حل مسائل گوناگون ساخته شده است.
سه گام اصلی در الگوریتم کلونی مورچگان
بر اساس مقاله که Bianchi و همکارانش در سال ۲۰۰۸ ارائه دادند، الگوریتم کلونی مورچگان ACO دارای سه گام اصلی است که سازنده‌ی ساختار اصلی حلقه بهینه سازی این الگوریتم هستند:
- تولید راه حل مورچه‌ها
- تبخیر فرومون
- اقدامات نهایی
تولید راه حل مورچه‌ها
این پروسه‌ای است که مورچه‌ها مسیرهایی را به شکل تصادفی و افزایشی تولید می‌کنند. که این مسیرها ، همان پاسخ‌های بهینه سازی در یک زمینه‌ی بزرگتر هستند.
تبخیر فرومون
در این پروسه میزان فرومون برای پاسخ‌های مشخصی با استفاده از اطلاعات “محلی” کاهش می‌یابد. بنابراین به این مرحله بروزرسانی محلی نیز گفته می‌شود. این مرحله یک مرحله حیاتی است. چراکه تضمین می‌کند الگوریتم کلونی مورچگان زودتر از موعد به یک پاسخ منتهی نخواهد شد.
اقدامات نهایی
این مرحله به تصمیمات گرفته شده براساس اطلاعات “کلی” مربوط به مسئله بهینه سازی باز می‌گردد. به تفاوت بین محلی در مرحله دوم و کلی در مرحله سوم دقت کنید. مشابه با مرحله دوم، مرحله سوم نیز به بروزرسانی کلی نیز معروف است.
سه مرحله فوق تا زمانی که مسئله بهینه سازی به یک جواب مشخص همگرا شود ادامه می‌یابد. در غیر این صورت با شرایط خاصی که از پیش تعیین شده است تکرار پایان می‌گیرد.
مدلسازی الگوریتم کلونی مورچگان ACO
هر کمان \( \Large (i,j) \) از یک گراف \( \Large G=(N,A) \) دارای یک متغیر مرتبط است که آن را با نماد \( \Large T_{ij} \) نمایش می‌دهیم. این نماد دنباله فرومون یا Pheromone Trail نام دارد. شدت فرومون شاخصه‌ای است از کاربردی بودن آن کمان برای ساختن پاسخ‌های (Solution) بهتر. در هر گره (Node) مورچه‌ها تصمیمات تصادفی‌ای برای رفتن به گره بعدی می‌گیرند. در ابتدا یک مقدار ثابت از فرومون \( \Large (i.e. , T_{ij} = 1 , \forall (i,j) \in A ) \) به تمامی کمان ها اختصاص می‌یابد. احتمال اینکه مورچه k اُم در گره i ، گره j را با استفاده از دنباله‌ی فرومون \( \Large T_{ij} \) از طریق رابطه زیر محاسبه می‌گردد:
\( \LARGE p_{ij}(k) = \begin{cases} & \huge \frac{\tau_{ij}^\alpha}{ \sum_{l \in N_l^k} \tau_{ij}^\alpha } & \text{if } j \in N^k_i \\ & 0 & \text{if } j \notin N^k_i \end{cases} \)
در این فرمول \( \Large N_i^k \) همسایگی مورچه k می‌باشد در حالیکه بر روی گره i اُم ایستاده است. همسایگی گره i اُم شامل تمام گره‌هایی است که مستقیماً به آن متصل هستند. به جز گره قبلی. این مسئله حرکت یکطرفه مورچه‌ها را تضمین می کند. بعنوان یک استثناء برای گره مقصد، جاییکه \( \Large N_i^k \) تهی است، گره پیشین i نیز شامل می‌شود. با استفاده از این سیاست تصمیم گیری ، مورچه‌ها از نقطه شروع تا مقصد به صورت تصادفی حرکت می‌کنند.
میزان فرومون در هربار تکرار از طریق رابطه زیر بروزرسانی می‌گردد:
\( \Large \tau_{ij} (k+1) = \rho \tau_{ij}(k) + \Delta \tau_{ij} (k) \)
در فرمول بالا \( \Large 0 < \rho < 1 \) است. همچنین \( \Large 1 – \rho \) نشاندهنده‌ی نرخ تبخیر فرومون است. \( \Large \Delta \tau_{ij} \) مربوط به عملکرد هر مورچه می‌باشد.
در کجا از الگوریتم کلونی مورچگان استفاده کنیم؟
الگوریتم بهینه سازی کلونی مورچگان در بسیاری از مسائل بهینه سازی ترکیبی مورد استفاده قرار گرفته است. محدوده این کاربردها بسیار متنوع و متغیر است. مانند مسائل مسیردهی به خودروها. برای این الگوریتم میتوان روشهای مشتق بسیاری را نام برد که برای مسائل پویا (Dynamic Problems) با متغیرهای واقعی، مسائل آماری، بهینه سازی چندهدفه و پیاده سازی موازی (Parallel Implementation) ، مسائلی خاص در زمینه پردازش تصویر و همچنین یادگیری ماشین و هوش مصنوعی استفاده می‌شوند. همچنین برای تولید راه حل‌های نزدیک به حالت بهینه (Near Optimal Solutions) در مسئله “فروشنده دوره گرد” از این الگوریتم استفاده می‌شود.
یک مزیت بزرگ این روش نسبت به الگوریتم ژنتیک و شبیه سازی تبرید، این است که با تغییر گراف، الگوریتم کلونی مورچگان قابلیت تغییر در لحظه را دارید. و همین نکته باعث جذابیت این الگوریتم در مسیردهی شبکه ای و حمل و نقل عمومی شده است.
مسئله فروشنده دوره گرد
اولین الگوریتم کلونی مورچگان ، الگوریتم مورچه‌ای نیز نامیده می‌شد. و هدف آن حل مسئله فروشنده دوره گرد بود. هدف مسئله فروشنده دوره گرد، پیدا کردن کوتاه‌ترین مسیر سفر برای ارتباط یک سلسله شهر است. مسئله به نسبت ساده است و اساس آن مجموعه‌ای از مورچه‌ها است که هرکدام یک مسیر ممکن را در طول این سفر انتخاب می‌کنند. در هر مرحله، مورچه انتخاب می‌کند که براساس قوانین زیر از یک شهر به شهر دیگر برود:
- از هر شهر دقیقاً باید یک بار عبور کرد.
- شهری که دور است، شانس کمتری برای دیده شدن دارد (بینایی)
- هرچقدر که مقدار فرومون به‌جا مانده در یک مسیر بیشتر باشد، احتمال اینکه آن مسیر برگزیده شود بیشتر است.
- بعد از پایان سفر، در صورتیکه سفر کوتاه باشد، مورچه فرومون بیشتری در مسیرهایی که عبور کرده پخش می‌کند.
- بعد از هر بار تکرار، ردپای فرومون‌های پخش شده از بین می‌رود.