الگوریتم کلونی مورچگان

الگوریتم کلونی مورچگان یا در حقیقت «بهینه‌سازی کلونی مورچگان» (Ant Colony Optimization) همانطور که از نام آن مشخص است، بر پایه رفتار طبیعی کلونی‌های مورچگان و مورچگان کارگر شاغل در آن‌ها بنا نهاده شده است. فرآیند یافتن منابع غذایی در کلونی مورچگان بسیار بهینه است. زمانی که مورچه‌ها عملیات کاوش برای یافتن منابع غذایی را آغاز می‌کنند، به طور طبیعی یک مسیر «منطقی» و «بهینه» از آشیانه خود به منابع غذایی پیدا می‌کنند. به عبارت دیگر، جمعیت مورچگان به نحوی همیشه قادر هستند تا یک مسیر بهینه را برای تامین منابع غذایی مورد نیاز بیابند. شبیه‌سازی چنین رفتار بهینه‌ای، پایه و اساس بهینه سازی کلونی مورچگان را تشکیل می‌دهد. در این مطلب، الگوریتم کلونی مورچگان به طور کامل تشریح شده است. باید توجه داشت که نام دقیق این الگوریتم، بهینه سازی کلونی مورچگان است که توسط اغلب افراد به آن الگوریتم مورچگان یا الگوریتم کلونی مورچگان گفته می‌شود.

دو مورچه را فرض کنید که در حال حرکت از آشیانه به منبع غذایی، از طریق دو مسیر کاملا متفاوت از هم هستند. مورچه‌ها در ضمن حرکت خود به سمت منبع غذایی، ردی از «فرومون» (Pheromone) در محیط منتشر می‌کنند که به‌طور طبیعی و با گذر زمان متلاشی می‌شود. مورچه‌ای که (به‌طور تصادفی) کوتاهترین مسیر به سمت منبع غذایی را انتخاب کرده، سفر برگشتی به سمت آشیانه را زودتر از دیگر مورچه‌ها آغاز می‌کند. در چنین حالتی، این مورچه در مسیر بازگشت به آشیانه، دوباره شروع به منتشر کردن فرومون در محیط می‌کند و از این طریق، رد فرومون به جا گذاشته در کوتاهترین مسیر را تقویت می‌کند.

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

روش بهینه‌سازی کلونی مورچگان، مدلی برای پیاده‌سازی روش‌های بهینه‌سازی ارائه می‌دهد. تاکنون، پیاده‌سازی‌های موفق متفاوتی از این روش بهینه‌سازی ارائه شده است. الگوریتم‌هایی نظیر «سیستم مورچگان» (َAnt System)، «سیستم کلونی مورچگان» (Ant Colony System) و «سیستم مورچگان Min-Max» از جمله مهم‌ترین و موفق‌ترین پیاده‌سازی‌های صورت گرفته از این روش بهینه‌سازی محسوب می‌شوند.

الگوریتم کلونی مورچگان

در این مطب سعی بر آن است تا ویژگی‌ها و مراحل پیاده‌سازی روش الگوریتم کلونی مورچگان شرح داده شود؛ روشی «فرا اکتشافی» (Metaheuristic) که از رفتار بهینه مورچه‌ها الهام گرفته شده است. الگوریتم مورچگان، روشی بسیار قدرتمند برای حل «مسائل بهینه‌سازی ترکیبیاتی» (Combinatorial Optimization Problems) محسوب می‌شود.

الگوریتم‌های مشتق شده از الگوریتم کلونی مورچگان، زیر مجموعه‌ای از روش‌های «هوش ازدحامی» (Swarm Intelligence) هستند. این دسته روش‌ها، حوزه تحقیقاتی و مطالعاتی به شمار می‌آیند که به مطالعه الگوریتم‌های الهام گرفته شده از مفهوم «رفتارهای ازدحامی» (Swarm Behaviors) می‌پردازند. الگوریتم‌های هوش ازدحامی از مجموعه‌ای از موجودیت‌های فردی ساده تشکیل شده‌اند که از طریق «خودسازماندهی» (Self-Organizing) با یکدیگر تعامل و همکاری می‌کنند. منظور از خودسازماندهی، نبود سیستم کنترل مرکزی برای کنترل و ایجاد هماهنگی میان اعضای یک سیستم هوش ازدحامی است.

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

الگوریتم کلونی مورچگان

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

حشره‌شناس فرانسوی، پیر پائول گراس (Pierre-Paul Grassé) اولین محققی بود که رفتار اجتماعی حشرات را مورد بررسی قرار داد. ایشان در بازه سال‌های اولیه دهه 40 میلادی تا اواخر دهه 50 میلادی، به مطالعه و تحقیق در مورد رفتار «موریانه‌ها» (Termites) پرداخت. در جریان این مطالعات، او به این موضوع پی برد که این گونه حشره‌ای می‌تواند به سیگنال‌های «محرک‌» (Stimuli) محیطی واکنش نشان دهد. چنین محرک‌هایی، به نوبه خود، نوعی واکنش برنامه‌نویسی شده ژنتیکی در این موجودات را فعال می‌کند.

این دانشمند، پی برد که تاثیرات این واکنش‌های ژنتیکی (از سوی موریانه) نه تنها می‌تواند به عنوان محرکی جدید برای خود موریانه عمل کند (ایجاد واکنش‌های متعاقب دیگر در پاسخ به محرک‌های محیطی)، بلکه دیگر موریانه‌های موجود در کلونی را نیز تحت تاثیر قرار می‌دهد و واکنش‌های خاصی را در آن‌‌ها برمی‌انگیزد. ایشان از اصطلاح «نشانه‌ورزی» (Stigmergy) برای توصیف این نوع ارتباط غیر مستقیم میان موریانه‌ها استفاده کرد. در این ارتباط کد شده ژنتیکی، گونه‌های کارگری حشرات از طریق عملکرد حاصل از تعامل با محیط تحریک می‌شوند و واکنش‌های ژنتیکی خاصی از خود نشان می‌دهند.

این دسته از ارتباطات ژنتیکی و غیر مستقیم میان حشرات، از دو جهت با دیگر وسایل ارتباطی متفاوت است:

  • طبیعتِ فیزیکی و غیر نمادین اطلاعات مبادله شده میان حشرات: این اطلاعات، مترادف با تغییرات حالات محیطی-فیزیکی است که در اثر تعامل حشره با محیط صورت می‌پذیرد.
  • طبیعتِ (ذات) محلی اطلاعات مبادله شده: این دسته از اطلاعات تنها توسط حشراتی قابل دسترسی است که از محیط حاوی این اطلاعات بازدید کرده باشند یا در همسایگی بلافاصل این محیط قرار گرفته باشند. به عبارت دیگر، چنین اطلاعاتی توسط تمامی حشرات موجود در کلونی قابل دریافت نیست و یک فاکتور جغرافیایی در تبادل اطلاعات میان حشرات مؤثر است.

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

الگوریتم کلونی مورچگان

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

الگوریتم کلونی مورچگان

 

این آزمایش نتایج بسیار شگفت انگیزی برای محققان به ارمغان آورد. آن‌ها کشف کردند که مورچه‌ها از رفتار بهینه ازدحامی مبتنی بر «بازخورد مثبت» (Positive Feedback) برای یافتن کوتاه‌ترین مسیر از کلونی به منابع غذایی استفاده می‌کنند. به چنین مکانیزمی، «خودکاتالیز» یا «اتوکاتالیز» (Autocatalysis) نیز گفته می‌شود. در ادامه، توضیح داده خواهد شد که مطالعات انجام شده روی جمعیت مورچه‌ها، چگونه منجر به توسعه الگوریتم‌های بهینه‌سازی می‌شود. به‌عبارت دیگر، یک الگوریتم بهینه‌سازی الهام گرفته شده از رفتار بهینه مورچگان، باید چه ویژگی‌هایی داشته باشد.

محققان، در پی مشاهده نتایج آزمایش «پل باینری» (Binary Bridge Experiment)، در صدد آن برآمدند تا مدلی ریاضی را برای توصیف رفتار بهینه مورچگان توسعه دهند. با فرض اینکه پس از گذشتن t واحد زمانی از زمان آغاز آزمایش، m1 مورچه از پل اول و m2 مورچه از پل دوم استفاده کرده باشند، احتمال (p1) اینکه مورچهm+1 پل اول را انتخاب کند برابر است با:

 

 

 

 

در این رابطه، پارامترهای k و h ، پارامترهای مورد نیاز برای «برازش» (Fitting) مدل روی داده‌های آزمایش است. همچنین، احتمال اینکه همان مورچه m + 1 پل دوم را انتخاب کند، از طریق رابطه (p 2 ( m + 1 ) = 1 − p 1 ( m + 1 به دست می‌آید. «شبیه‌سازی مونته کارلو» (Monte Carlo Simulation) انجام شده روی داده‌های آزمایش نشان می‌دهد که مدل توسعه داده شده با مقادیر پارامترهای k ≈ 20 و h ≈ 2 ، برازش بسیار خوب و مناسبی از داده‌های آزمایش تولید می‌کند. از این مدل ساده می‌توان برای طراحی «مورچه‌های مصنوعی» (Artificial Ants) استفاده کرد که مسائل بهینه‌سازی را به شیوه مشابه حل می‌کنند.

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

بنابراین، مورچه‌های مصنوعی به دو روش قادر خواهند بود خود را با ویژگی‌های شاخص مدل ارتباطی ذکر شده (نشانه‌ورزی) سازگار کنند:

ایجاد تناظر میان متغیرهای توصیف کننده حالات محیطی و مقادیر مختلف برای متغیرهای مسأله.
فراهم کردن دسترسی (فقط) محلی به این متغیرها برای عوامل (مورچه‌های مصنوعی).
یکی دیگر از ویژگی‌های رفتاری مهم جمعیت مورچه‌ها که می‌تواند توسط مورچه‌های مصنوعی (عامل‌های روش بهینه‌سازی) مورد بهره‌وری قرار بگیرد، جفت‌شدگی (رابطه متقابل) میان مکانیزم خودکاتالیز و «ارزیابی ضمنی» (Implicit Evaluation) جواب‌ها است. منظور از ارزیابی ضمنی در رفتار بهینه مورچه‌ها این است که مسیر‌های کوتاه‌تر، زودتر از مسیرهای بلندتر توسط مورچه‌ها پیموده می‌شوند؛ در نتیجه، رد فرمون منتشر شده در این مسیر، سریع‌تر توسط مورچه‌های دیگر تقویت می‌شود. مسیر کوتاه‌تر برای مورچه‌های مصنوعی، معادل برازندگی بیشتر یا هزینه کمتر است. بنابراین، جفت‌شدگی میان مکانیزم خودکاتالیز و ارزیابی ضمنی، در صورتی که برای تولید عملگرهای تکاملی مناسب استفاده شود، مکانیزم فوق‌العاده قدرتمندی برای تضمین عملکرد بهینه در الگوریتم‌های بهینه‌سازی مبتنی بر جمعیت خواهد بود.

الگوریتم کلونی مورچگان

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

 

  • جمعیت کلونی‌های واقعی و کلونی‌های مصنوعی مورچگان، از نمونه‌هایی تشکیل شده‌اند که برای رسیدن به یک هدف خاص با هم همکاری می‌کنند. یک کلونی، جمعیتی متشکل از عامل‌های ساده، مستقل و «ناهمگام» (Asynchronous) است که با یکدیگر برای یافتن جواب‌های بهینه یک مسأله بهینه‌سازی، همکاری و تعامل می‌کنند.
  • در کلونی مورچگان واقعی، مسأله، پیدا کردن منابع غذایی است. در کلونی مورچه‌های مصنوعی، مسأله، پیدا کردن جواب‌های بهینه برای مسأله بهینه‌سازی داده شده است.
  • یک مورچه (چه واقعی و چه مصنوعی)، به تنهایی قادر به پیدا کردن جواب خواهد بود؛ ولی فقط همکاری میان نمونه‌ها از طریق مکانیزم «نشانه‌ورزی» (Stigmergy)، رسیدن به جواب بهینه را تضمین می‌کند.
  • وجود مکانیزمی معادل تبخیر فیزیکی اثر فرومون در روش‌های بهینه‌سازی مورچگان (همانند کلونی واقعی مورچگان)، به مورچه‌های مصنوعی این امکان می‌دهد که مسیرهای از پیش پیموده شده را فراموش کرده و بیشتر بر روی جهت‌های جستجوی جدید و امیدوارکننده تمرکز کنند.
  • در کلونی مصنوعی مورچگان (همانند کلونی واقعی)، مورچه‌های مصنوعی، جواب‌های کاندید را با حرکت ترتیبی از یک حالت خاص مسأله به حالتی دیگر (تغییر مقادیر متغیرهای مسأله) تولید می‌کنند.
  • مورچه‌های واقعی، بر اساس غلظت فرومون در محیط و نیز یک سیاست تصمیم‌گیری تصادفی، مسیر حرکت خود را مشخص می‌کنند. مورچه‌های مصنوعی نیز مرحله به مرحله و از طریق تغییر مقادیر متغیرهای مسأله و نیز تصمیم‌گیری‌های تصادفی، اقدام به تولید جواب‌های کاندید برای مسأله مورد نظر می‌کنند.
  • در کلونی واقعی، مورچه‌ها یا ماده‌ای به نام فرومون در محیط منتشر می‌کنند و یا به آن واکنش نشان می‌دهند؛ در کلونی مصنوعی، مورچه‌های مصنوعی، مقادیر عددی متناظر با حالت‌های مختلف مسأله (متغیرهای مسأله) را تغییر می‌دهند. به مقادیر عددی، «فرومون‌های مصنوعی» (Artificial Pheromones) و به دنباله‌ای از این مقادیر عددی، «رد مصنوعی فرومون» (َArtifical Pheromone Trail) گفته می‌شود.
  • برخلاف مورچه‌های واقعی، مورچه‌های مصنوعی در یک جهان گسسته فعالیت می‌کنند. آن‌ها، پی در پی و در یک فضای متناهی متشکل از حالات (متغیرهای) مسأله در حال حرکت و تولید جواب‌های کاندید هستند.
  • فرآیند به‌روز رسانی مقادیر فرومون‌ها (نظیر انتشار و تبخیر فرومون) در کلونی مصنوعی مورچگان، دقیقا همانند کلونی واقعی مورچه‌ها انجام نمی‌شود. برخی مواقع، به‌روز رسانی فرومون، فقط توسط تعدادی از مورچه‌های مصنوعی و معمولا تنها پس از تولید یک جواب برای مسأله بهینه‌سازی انجام می‌شود.
  • برخی از پیاده‌سازی‌های انجام شده از الگوریتم کلونی مورچگان، مکانیزم‌های اضافی را شامل می‌شوند که در جهان واقعی وجود ندارند (نظیر مکانیزم جستجوی محلی، مکانیزم عقب‌نشینی و سایر موارد).

الگوریتم کلونی مورچگان

الگوریتم کلونی مورچگان، به عنوان یک روش فرا اکتشافی برای حل «مسائل بهینه‌سازی ترکیبیاتی» (Combinatorial Optimization Problems) طراحی شده و تاکنون، در موارد بسیاری، برای حل این دسته از مسائل استفاده شده است.

با فرض داشتن یک مسأله بهینه‌سازی ترکیبیاتی، اولین قدم در بهینه‌سازی با استفاده از الگوریتم کلونی مورچگان، تعریف یک مدل مناسب است. از این مدل، برای تعریف یکی از مهم‌ترین واحدهای الگوریتم کلونی مورچگان یا همان «مدل فرومون» (Pheromone Model) استفاده می‌شود. مدل لازم برای یک مسأله بهینه‌سازی ترکیبیاتی، به شکل زیر تعریف می‌شود:

(A model P = ( S , Ω , f

یک مدل فرومون برای یک مسأله بهینه‌سازی ترکیبیاتی شامل موارد زیر خواهد بود:

  • یک فضای جستجو به نام  S ، که روی مجموعه‌ای متناهی از متغیرهای گسسته تصمیم و مجموعه‌ای از قیدهای تعریف شده روی متغیرهای مسأله به نام  Ω تعریف می‌شود.

یک تابع هدف f : S → R + 0 که قرار است کمینه شود. به این نکته باید توجه کرد که کمینه‌سازی یک تابع هدف مثل f ، دقیقا برابر با بیشینه‌سازی تابع هدف − f خواهد بود. در نتیجه، هر مسأله بهینه‌سازی ترکیبی، در قالب یک مسأله کمینه‌سازی قابل بازنویسی خواهد بود. فضای جستجو به این شکل تعریف می‌شود: مجموعه‌ای از متغیرهای تصمیم گسسته (متغیرهای مسأله) X i ، i = 1 , … , n ، با مقادیر v j i ∈ D i = { v 1 i , … . . , v ∣ ( D i ) ∣i } داده شده است. مقداردهی متغیرهای مسأله (اختصاص دادن مقدار v j i به متغیر X i )، توسط نماد X i ← v j i نمایش داده می‌شود. یک جواب کاندید s ∈ S ، به یک مقداردهی کامل به متغیرهای مسأله گفته می‌شود که در آن، هر متغیر تصمیم مقادیری دارد که تمام قیدهای تعریف شده در مجموعه Ω برای یک مسأله بهینه‌سازی ترکیبیاتی داده شده را ارضا می‌کند.

اگر مجموعه  Ω تهی باشد، به  P مسأله بهینه‌سازی ترکیبی «نامقید» (Unconstrained) گفته می‌شود؛ در غیر این صورت، به آن مسأله بهینه‌سازی «مقید» (Constrained) گفته می‌شود. یک جواب کاندید  s ∗ ∈ S ، یک «جواب بهینه سراسری» (Global Optimum Solution) برای مسأله بهینه‌سازی ترکیبیاتی داده شده است، اگر و تنها اگر شرط  f ( s ∗ ) ≤ f ( s ) ∀ s ∈ S را ارضا کند. مجموعه تمامی جواب‌های بهینه سراسری توسط نماد  S ∗ ⊆ S نمایش داده می‌شوند. حل یک مسأله بهینه‌سازی ترکیبیاتی، مستلزم پیدا کردن حداقل یک جواب بهینه  s ∗ ∈ S ∗ است.

از مدل تعریف شده بالا، برای توسعه مدل فرومون در الگوریتم کلونی مورچگان استفاده می‌شود. متغیر تصمیم مقداردهی اولیه شده  X i = v j i (به عبارت دیگر، یک مقدار مانند  v j i از دامنه  D i به متغیر  X i اختصاص داده می‌شود)، یک «مؤلفه جواب کاندید» (Candidate Solution Component) نامیده می‌شود و به وسیله نماد  c i , j نمایش داده می‌شود. مجموعه تمامی مؤلفه‌های جواب کاندید ممکن، توسط  C نمایش داده می‌شوند. سپس، هر پارامتر «رد فرومون» (Pheromone Trail)،  T i j ، متناظر با یکی از مؤلفه‌های جواب کاندید  c i , j در نظر گرفته می‌شود. مجموعه تمامی پارامترهای رد فرومون، توسط  T نمایش داده می‌شوند. مقدار یک پارامتر رد فرومون  T i j توسط نماد  τ i j نمایش داده شده و «مقدار فرومون» (Pheromone Value) نامیده می‌شود.

مقادیر فرومون، در طی فرآیند جستجو، توسط الگوریتم کلونی مورچگان استفاده و به روز رسانی می‌شوند. همچنین، این پارامترها امکان مدل‌سازی توزیع احتمالی مؤلفه‌های مختلف جواب را به الگوریتم مورچگان می‌دهند. مقادیر فرومون و جواب کاندید (مقادیر متغیرهای مسأله)، عملا دو مفهوم کاملا به هم وابسته هستند. در طول فرآیند تکاملی، مقادیر فرومون برای جواب‌های کاندیدی که به جواب بهینه سراسری نزدیک‌تر باشند، افزایش می‌یابند و برعکس. در نتیجه، رد فرومون جواب‌های خوب، قوی‌تر می‌شود و جهت جستجو برای یافتن جواب بهینه برای مورچه‌های مصنوعی دیگر مشخص می‌شود.

در الگوریتم کلونی مورچگان، مورچه‌های مصنوعی، یک جواب کاندید برای مسأله بهینه‌سازی ترکیبیاتی داده شده را از طریق پیمایش گرافی به نام «گراف ساختاری» (Construction Graph) تولید می‌کنند. این گراف، توسط  G C ( V , E ) نمایش داده می‌شود. یک گراف ساختاری کاملا متصل، از مجموعه‌ای از «رأس‌ها» (Vertices) و مجموعه‌ای از «یال‌ها» (Edges) تشکیل شده است. مجموعه مؤلفه‌های جواب کاندید  C ممکن است متناظر با مجموعه رأس‌ها  V در گراف  G C یا مجموعه یال‌ها  E در گراف  G C باشند.

مورچه‌ها، برای تولید جواب کاندید، در راستای یال‌های گراف، از یک رأس به رأس دیگر حرکت می‌کنند و از این طریق، به طور تدریجی یک «جواب کاندید جزئی» (Partial Candidate Solution) را تولید می‌کنند. علاوه بر این، مورچه‌ها در هنگام حرکت در محیط، روی یال‌ها یا رأس‌هایی که در گراف ساختاری پیمایش می‌کنند، مقدار مشخصی فرومون منتشر می‌کنند. مقدار فرومون منتشر شده در محیط  △ τ ، به کیفیت جواب کاندید تولید شده بستگی دارد. مورچه‌های بعدی، از اطلاعات فرومون منتشر شده به عنوان راهنما برای پیدا کردن مناطق بهتر در فضای جستجو و حرکت به سمت آن‌ها استفاده می‌کنند. از یک سو، این مناطق، به احتمال زیاد حاوی جواب بهینه سراسری هستند و از سوی دیگر، در صورت حرکت مورچه‌‎های مصنوعی به سمت این مناطق، با سرعت بیشتری می‌توانند به جواب بهینه سراسری همگرا شوند.

شبه کد الگوریتم کلونی مورچگان در ادامه آمده است.

پارامترهای الگوریتم کلونی مورچگان تنظیم شده و ردهای فرومون مقداردهی اولیه می‌شوند.
تا زمانی که شرط توقف ارضا نشده باشد:
مرحله اول یا مرحله «تولید جواب‌های کاندید» (Construct Ant Solution) را شروع کن.
مرحله دوم یا مرحله «جستجوی محلی جواب‌ها» (Local Search) را شروع کن. در این مرحله، از جواب‌های بهینه محلی استفاده می‌شود تا مشخص شود کدام یک از فرومون‌ها باید به روز رسانی شوند. این مرحله اختیاری است و در برخی از پیاده‌سازی‌های انجام شده از الگوریتم کلونی مورچگان وجود ندارد.
مرحله سوم یا مرحله «به روز رسانی فرومون» (Pheromone Update) را انجام بده.
در صورتی که شرط توقف ارضا شده باشد، اجرای الگوریتم را متوقف کن؛ در غیر این صورت، مراحل را مجددا انجام بده.
الگوریتم کلونی مورچگان از دو بخش تشکیل شده است. در بخش اول، مقادیر پارامترهای مسأله تنظیم و متغیرهای جمعیت اولیه مقداردهی می‌شوند. بخش دو شامل یک حلقه تکرار است که سه مرحله الگوریتم کلونی مورچگان را اجرا می‌کند. در هر حلقه از الگوریتم کلونی مورچگان، جواب‌های کاندید توسط تمامی مورچه‌های مصنوعی ساخته می‌شوند. جواب‌های تولید شده، از طریق یک الگوریتم جستجوی محلی بهبود می‌یابند. در مرحله آخر، فرومون‌ها به روز رسانی می‌شوند.

الگوریتم کلونی مورچگان

  • همکاری گروهی میان مورچه‌ها برای تولید جواب‌های بهینه، طبیعت مبتنی‌بر «توازی» (Parallelism) و «همبستگی» (Solidarity) این روش فرا اکتشافی را نشان می‌دهد.
  • بازخورد مثبت ایجاد شده از طریق انتشار فرومون در محیط، سبب همگرایی سریع به جواب‌های خوب برای مسأله بهینه‌سازی می‌شود.
  • برای استفاده در کاربردهای پویا (کاربردهایی که نیاز به انطباق سریع با تغییرات محیطی ضروری است) مناسب است.
  • همگرایی به جواب بهینه، تضمین شده است.
  • تجزیه و تحلیل نظری این روش بسیار سخت است.
  • این روش، بر پایه دنباله‌ای از تصمیمات تصادفی ولی وابسته به هم بنا نهاده شده است.
  • زمان لازم برای همگرایی به جواب بهینه نامشخص است