- تاریخچه‌ای کوتاه درباره الگوریتم بهینه‌سازی کلونی مورچگان (ACO)
این روش که از رفتار مورچه‌ها در یافتن مسیر بین محل لانه و غذا الهام گرفته شده؛ اولین بار در ۱۹۹۲ توسط مارکو دوریگو Marco Dorigo و همکارانش، به عنوان يک راه حل چند عامله (Multi Agent) براي مسائلی که مشکل بهينه سازي دارند، مثل فروشنده دوره گرد (TSP :Traveling Sales Person)، ارائه شد.
موضوع Optimization که در سال ۱۹۹۲ توسط مارکو دوریگو و در رساله دکتری وی مطرح شد، یکی از بارزترین نمونه ها برای روش‌های هوش جمعی است. این الگوریتم از روی رفتار جمعی مورچه ها الهام گرفته شده است. مورچه ها با همکاری یکدیگر، کوتاه ترین مسیر را میان لانه و منابع غذایی پیدا می کنند تا بتوانند در کمترین زمان مواد غذایی را به لانه منتقل کنند. هر کدام از مورچه ها، به تنهایی قادر به انجام چنین کاری نیستند
آشیانه شان به سمت محل غذا در بیرون آشیانه شان، الهام گرفته شده است. دو مورچه را فرض کنید که در حال حرکت از آشیانه به منبع غذایی، از طریق دو مسیر کاملا متفاوت از هم هستند. مورچه‌ها در ضمن حرکت خود به سمت منبع غذایی، «ردی از فرومون» (Pheromone Trail) در محیط منتشر می‌کنند که به‌طور طبیعی و با گذر زمان متلاشی و تبخیر می‌شود. مورچه‌ای که (به‌طور تصادفی) کوتاهترین مسیر به سمت منبع غذایی را انتخاب کرده، سفر برگشتی به سمت آشیانه را زودتر از دیگر مورچه‌ها آغاز می‌کند. در چنین حالتی، این مورچه در مسیر بازگشت به آشیانه، دوباره شروع به منتشر کردن فرومون در محیط می‌کند و از این طریق، رد فرومون به جا گذاشته در کوتاهترین مسیر را تقویت می‌کند. همانطور که در شکل 1 مشاهده می‌شود، ابتدا در قسمت 1 مورچه‌ها اولین بار برای عبور از مسیر رسیدن به غذا را در دوراهی‌ها، به طور کاملا تصادفی انتخاب می‌کنند. ممکن است در مسیر رفت یا برگشت حتی از مسیر طولانی تر عبور کنند. در بخش 2 ملاحظه می‌کنید که نسبت حرکت در دو مسیر طولانی و کوتاه از نقطه T به Nتقریبا مشابه است اما در قسمت 3 با توجه به فرومون بیشتر ترشح شده در مسیر کوتاه، اغلب مورچه ها از مسیر کوتاه تر به سمت غذا حرکت می کنند و مسیر را باز می‌گردند. البته باید توجه داشت که این موضوع به صورت احتمالی است و همانطور که در قسمت 3شکل 1 هم ملاحظه می‌شود، هنوز مورچه هایی هستند که از مسیر طولانی تر حرکت می کنند.
- الگوریتم ACO چگونه کار می‌کند؟
روش کلی رفتار مورچه‌ها قبلا طبق شکل 1 بیان شد. حال با نگاهی الگوریتمی این حرکت را مورد مطالعه قرار می‌دهیم. نمای کلی فلوچارت الگوریتم به این شکل است:
همانطور که در شکل 2 ملاحظه می‌فرمایید، آزمایشات انجام شده نشان می دهد که مورچه ها در مرحله اول وقتی به دو راهی می رسند مسیر خود را کاملا تصادفی انتخاب می کنند. یعنی اگر دو مورچه داشته باشیم ممکن است هر دو از مسیر کوتاه یا هر دو از مسیر طولانی یا یکی از مسیر کوتاه یکی از مسیر طولانی حرکت کند. این موضوع کاملا تصادفی است.
در مرحله دوم تا چهارم، ملاحظه می کنیم که به مرور با ادامه حرکت رفت (L) و برگشت (R) مورچه ها احتمال انتخاب مسیر کوتاه تر بیشتر خواهد شد. به دلیل این که فرومون بیشتری در مسیر کوتاه تر قرار دارد لذا مورچه هایی که از آشیانه به سمت غذا حرکت می کنند، آن مسیر را انتخاب خواهند کرد. البته باید به این نکته توجه داشت که کماکان این موضوع احتمالی است و مورچه هایی هم هستند که مسیر طولانی تر را انتخاب خواهند کرد.
چگونه مسیر کوتاه انتخاب می شود؟ این را در شکل 3 به صورت خلاصه و بین دو مورچه بررسی خواهیم کرد:
برای ساده شده مسئله، فرض کنیم یک مورچه از مسیر A حرکت کرده و یک مورچه از مسیر B، لذا چون مسیر A به طول 10 متر بود و اگر یک واحد فرومون در مسیر ریخته شود، هر متر آن 0.1 فرومون خواهد داشت. در مسیر B که 100 متر است نیز اگر یک واحد فرومون ریخته شود، هر متر آن 0.01 فرومون خواهد داشت. حال اگر مورچه بعدی بخواهد مسیر انتخاب کند، به طور کاملا تصادفی این کار را خواهد کرد، مثلا مسیر B را انتخاب کند، بنابر این میزان فرمون مسیر B برابر 0.02 خواهد شد. به همین شکل و به صور کاملا تصادفی مسیر A و B انتخاب خواهند شد. با هر بار انتخاب هر مسیر نیز، مقدار فرومون آن مسیر تقویت خواهد شد. البته فرومون مسیر بعد از مدتی تبخیر خواهد شد (تضعیف احتمال انتخاب مسیر) که این موضوع نیز در انتخاب مسیر مورچه ها تاثیر خواهد داشت. وجود پارامتر تبخیر فرومون، برای جلوگیری از «همگرایی سریع و نابالغِ» (Rapid and Premature Convergence) الگوریتم کلونی مورچگان ضروری است. پارامتر تبخیر، نوعی مکانیزم «فراموشی» (Forgetting) در فرآیند بهینه‌سازی فراهم می‌کند و سبب تاکید بیشتر بر جستجو و کاوش مناطق جدید، در فضای جستجوی الگوریتم‌های پیاده‌سازی شده می‌شود. شکل 4 بیانگر سه مرحله ابتدایی این الگوریتم با نگاهی ساده خواهد بود:
توجه کنیم که نباید فرض کرد که بعد از مدتی بدون استثناء همه مورچه ها از مسیر کوتاه حرکت خواهند کرد بلکه تصادفی بودن انتخاب آن‌ها تا انتهای اجرای الگوریتم وجود خواهد داشت. همچنین تمرکز و تنوع در این نوع الگوریتم‌ها در نظر گرفته خواهد شد.
-سخن آخر
در این بخش به اجمال به برخی مزایا و معایب و کاربردهای الگوریتم ACO می‌پردازیم:
* مزایای روش الگوریتم کلونی مورچگان:
· همکاری گروهی میان مورچه‌ها برای تولید جواب‌های بهینه، طبیعت مبتنی‌بر «توازی» (Parallelism) و «همبستگی» (Solidarity) این روش فرا اکتشافی را نشان می‌دهد.
· بازخورد مثبت ایجاد شده از طریق انتشار فرومون در محیط، سبب همگرایی سریع به جواب‌های خوب برای مسأله بهینه‌سازی می‌شود.
· برای استفاده در کاربردهای پویا (کاربردهایی که نیاز به انطباق سریع با تغییرات محیطی ضروری است) مناسب است.
· همگرایی به جواب بهینه، تضمین شده است.
* معایب روش الگوریتم کلونی مورچگان:
· تجزیه و تحلیل نظری این روش بسیار سخت است.
· این روش، بر پایه دنباله‌ای از تصمیمات تصادفی ولی وابسته به هم بنا نهاده شده است.
· زمان لازم برای همگرایی به جواب بهینه نامشخص است.
* کاربردهای ACO:
از کاربردهای ACO می‌توان به بهینه کردن هر مسئله‌ای که نیاز به یافتن کوتاهترین مسیر دارد، اشاره نمود:
· مسائل بهینه‌سازی استراتژی برنامه‌ریزی کارها (Job-Scheduling Problems).
· بهینه‌سازی مسیریابی وسایل نقلیه.
· «پردازش تصویر» (Image Processing).
· مسائل بهینه‌سازی اندازه دستگاه‌ها در طراحی فیزیکی دستگاه‌های نانوالکترونیکی.
· بهینه‌سازی شکل آنتن‌ها (به عنوان نمونه در برچسب‌های RF-ID).
· مسیر یابی داخل شهری و بین شهری.
· مسیر یابی بین پست‌های شبکه‌های توزیع برق ولتاژ بالا.
· مسیر یابی شبکه‌های کامپیوتری.
· استفاده از وب.
· استفاده ازACO دربهینه سازی شبکه‌های توزیع آب
· لبه یابی تصاویر
موفق باشید
