Skip to content
بازگشت به نتایج جست‌وجو

بهینه‌سازی کلونی مورچگان — بهینه‌سازی ترکیبی مبتنی بر ازدحام

سال
1992 (foundational thesis); 1997 (Ant Colony System formalization)
نوع
Metaheuristic — swarm intelligence

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

بهینه‌سازی کلونی مورچگان (ACO) یک الگوریتم فراابتکاری است که توسط مارکو دورایگو و همکارانش در اوایل دهه ۱۹۹۰ معرفی شد و با شبیه‌سازی رفتار جمعی جستجوی غذا در مورچه‌ها، مسائل بهینه‌سازی ترکیبی را حل می‌کند. مورچه‌های واقعی مسیرها را با رد بوی فرومون علامت‌گذاری می‌کنند و به طور ترجیحی مسیرهای قوی‌تر را دنبال می‌کنند؛ ACO این مکانیزم بازخورد مثبت را به یک رویه جستجو تبدیل می‌کند که راه‌حل‌های با کیفیت بالا برای مسائل ساختاریافته گرافی مانند مسئله فروشنده دوره‌گرد، مسیریابی وسایل نقلیه و زمان‌بندی پیدا می‌کند.

شهود پشت روش

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

تاریخ

چارچوب بهینه‌سازی کلونی مورچگان توسط مارکو دورایگو در پایان‌نامه دکتری خود در سال ۱۹۹۲ معرفی شد، که از مشاهدات نحوه یافتن کوتاه‌ترین مسیرها توسط کلونی‌های مورچه واقعی از طریق ارتباطات فرومون استیگمرژیک الهام گرفته شده بود. اولین الگوریتم ملموس، Ant System (AS)، با Maniezzo و Colorni در سال ۱۹۹۶ منتشر شد. در سال ۱۹۹۷، دورایگو و گامباردلا Ant Colony System (ACS) را منتشر کردند که به‌روزرسانی‌های فرومون محلی و یک قاعده بهره‌برداری تهاجمی‌تر را معرفی کرد و عملکرد را در مسئله فروشنده دوره‌گرد به طور قابل توجهی بهبود بخشید. مونوگراف MIT Press دورایگو و اشتوتزله در سال ۲۰۰۴ چارچوب ACO را یکپارچه کرد و آن را به عنوان یک شاخه اصلی هوش ازدحامی تثبیت کرد. از آن زمان، ACO به دامنه‌های پیوسته (ACOR)، مسائل چندهدفه (MOACO) و گراف‌های پویا گسترش یافته است.

چه زمانی استفاده شود

ACO برای مسائل بهینه‌سازی ترکیبی که می‌توانند به عنوان یک وظیفه یافتن مسیر یا تخصیص بر روی یک گراف بیان شوند، مناسب است — مثال‌های کلاسیک شامل مسئله فروشنده دوره‌گرد، مسیریابی وسایل نقلیه، زمان‌بندی شغل-کارگاه، و مسیریابی شبکه است. این الگوریتم متغیرهای تصمیم‌گیری پیوسته و دسته‌ای را می‌پذیرد، زمانی که مسئله به درستی کدگذاری شده باشد. هیچ فرض نرمالیتی لازم نیست و هیچ محدودیت حداقل اندازه نمونه وجود ندارد؛ ورودی مرتبط یک ساختار گراف خوش‌تعریف و یک بودجه تکرار کافی (معمولاً چند صد تا چند هزار تکرار) است. ACO به ویژه زمانی رقابتی است که اکتشافات دامنه برای هدایت مورچه‌ها در دسترس باشند. اگر کمتر از حدود ۱۰۰ تا ۲۰۰ تکرار قابل تخصیص باشد، Tabu Search یک جایگزین ارجح است.

محدودیت‌ها و ملاحظات

  • به بودجه تکرار کافی نیاز دارد؛ با تکرارهای بسیار کم، مسیرهای فرومون قابل اعتماد نیستند و کیفیت راه‌حل کاهش می‌یابد.
  • سه پارامتر کلیدی — α، β، و ρ — باید تنظیم شوند؛ مقادیر نامناسب می‌توانند باعث همگرایی زودهنگام یا سکون شوند.
  • همگرایی در گراف‌های بسیار بزرگ می‌تواند کند باشد زیرا سیگنال فرومون در بین یال‌های زیادی رقیق می‌شود.
  • به طور طبیعی برای مسائل بهینه‌سازی پیوسته بدون کدگذاری گراف مناسب نیست.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • فضاهای جستجوی ترکیبی بزرگ و گسسته را که برای روش‌های دقیق غیرقابل حل هستند، مدیریت می‌کند.
  • جستجوی مبتنی بر جمعیت امکان موازی‌سازی ضمنی را فراهم می‌کند — چندین راه‌حل کاندیدا به طور همزمان کاوش می‌شوند.
  • دانش دامنه (اکتشافی η) می‌تواند مستقیماً در قاعده انتقال تزریق شود تا همگرایی تسریع شود.
  • مکانیزم فرومون بازخورد مثبت به طور طبیعی جستجو را در طول زمان بر روی مناطق امیدوارکننده متمرکز می‌کند.
  • در برابر بازسازی مجدد مسئله مقاوم است: اضافه کردن یا حذف گره‌ها/یال‌های گراف نیازی به بازتعریف الگوریتم ندارد.

کاربردها

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

چگونه کار می‌کند

چگونه کار می‌کند

1

مسئله بهینه‌سازی به صورت یک گراف کدگذاری می‌شود: گره‌ها نقاط تصمیم‌گیری (مانند شهرها، وظایف، عملیات) را نشان می‌دهند و یال‌ها دو وزن دارند — سطح فرومون τ که هر تکرار به‌روزرسانی می‌شود و یک مقدار اکتشافی η که از دانش دامنه (مانند معکوس فاصله) مشتق شده است. این گراف محیط مشترکی است که از طریق آن همه مورچه‌ها به طور غیرمستقیم ارتباط برقرار می‌کنند.

2

هر مورچه مصنوعی با پیمایش گراف، یک راه‌حل کامل می‌سازد. در هر گره، یال بعدی را بر اساس یک قاعده انتقال که سطح فرومون (به توان α) و جذابیت اکتشافی (به توان β) را متعادل می‌کند، به صورت احتمالی انتخاب می‌کند. α بالاتر، بهره‌برداری از مسیرهای خوب شناخته شده را ترجیح می‌دهد؛ β بالاتر، اتکا به دانش خاص مسئله را افزایش می‌دهد. نتیجه جمعیتی از راه‌حل‌های کاندیدا است که در هر تکرار به صورت موازی تولید می‌شوند.

3

پس از اینکه همه مورچه‌ها تورهای خود را کامل کردند، سطوح فرومون در دو مرحله تنظیم می‌شوند. ابتدا، تبخیر، فرومون هر یال را با ضریبی (۱ - ρ) کاهش می‌دهد، که از تجمع نامحدود جلوگیری کرده و از قفل شدن زودهنگام جستجو جلوگیری می‌کند. دوم، مورچه‌ها بر روی یال‌هایی که استفاده کرده‌اند فرومون می‌ریزند؛ راه‌حل‌های بهتر بیشتر می‌ریزند و مسیرهای کوتاه‌تر یا با کیفیت‌تر را تقویت می‌کنند. نوع Ant Colony System (ACS) علاوه بر این، یک به‌روزرسانی فرومون محلی در طول ساخت برای تنوع بخشیدن به جستجو اعمال می‌کند.

4

این رویه تکرار می‌شود تا زمانی که یک معیار توقف برآورده شود — معمولاً حداکثر تعداد تکرار یا یک آستانه سکون (عدم بهبود در طی تعداد مشخصی تکرار). بهترین راه‌حل یافت شده در تمام تکرارها برگردانده می‌شود. اگر بودجه تکرار خیلی کم باشد، کلونی ممکن است مسیرهای فرومون قابل اعتمادی تشکیل ندهد و نتیجه به یک جستجوی تقریباً تصادفی تبدیل شود؛ در این صورت، استفاده از Tabu Search توصیه می‌شود.

دام‌های رایج

  • اجرای تکرارهای بسیار کم (یک قاعده سرانگشتی رایج، حداقل چند صد تکرار است) — کلونی هرگز مسیرهای فرومون پایدار تشکیل نمی‌دهد و راه‌حل‌های تقریباً تصادفی تولید می‌کند؛ در صورت تنگ بودن بودجه، به Tabu Search تغییر دهید.
  • تنظیم نرخ تبخیر ρ خیلی پایین — فرومون قدیمی انباشته می‌شود، کلونی زودتر بر روی یک مسیر زیربهینه تثبیت می‌شود و تنوع فرو می‌ریزد؛ ρ را افزایش دهید یا از مکانیزم بازنشانی فرومون استفاده کنید.
  • نادیده گرفتن اطلاعات اکتشافی (β = 0) — الگوریتم صرفاً مبتنی بر فرومون می‌شود که در ابتدا که مسیرها ناآگاهانه هستند، کند و غیرقابل اعتماد است.
  • اعمال ACO بر روی مسائل پیوسته بدون کدگذاری گراف مناسب — قاعده انتقال احتمال به یک گراف گسسته متکی است؛ نگاشت مستقیم متغیرهای حقیقی بدون گسسته‌سازی یا نوع ACO مناسب (مانند ACOR) منجر به نتایج ضعیف می‌شود.
  • عدم پیگیری بهترین راه‌حل سراسری در تمام تکرارها — به‌روزرسانی‌های فرومون که فقط بر اساس بهترین مورچه تکرار فعلی انجام می‌شوند، بهترین راه‌حل کلی یافت شده را از دست می‌دهند.

پرسش‌های متداول

ACO چگونه با الگوریتم‌های ژنتیک متفاوت است؟

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

چه مقادیری را باید برای α، β و ρ استفاده کنم؟

بنچمارک‌های متعارف بر روی TSP نشان می‌دهند که α ≈ ۱، β ≈ ۲–۵، و ρ ≈ ۰.۰۲–۰.۱ به عنوان نقاط شروع معقول هستند (Dorigo & Stützle, 2004). β بالاتر، تأثیر اکتشافی را افزایش می‌دهد (زمانی که دانش دامنه قابل اعتماد است مفید است)؛ ρ بالاتر، تبخیر و تنوع را افزایش می‌دهد اما ممکن است همگرایی را کند کند. این پارامترها به مسئله وابسته هستند و باید به طور سیستماتیک تنظیم شوند، برای مثال با یک جستجوی شبکه‌ای کوچک یا بهینه‌سازی بیزی.

آیا ACO می‌تواند مسائل بهینه‌سازی پیوسته را حل کند؟

ACO استاندارد برای فضاهای جستجوی گسسته و ساختاریافته گرافی طراحی شده است. مسائل پیوسته را می‌توان با ACOR (بهینه‌سازی کلونی مورچگان برای دامنه‌های پیوسته) که ماتریس فرومون را با یک بایگانی راه‌حل و یک تابع چگالی احتمال جایگزین می‌کند، حل کرد. برای مسائل کاملاً پیوسته بدون کدگذاری گراف طبیعی، جایگزین‌هایی مانند بهینه‌سازی ازدحام ذرات یا تکامل تفاضلی ممکن است ساده‌تر باشند.

معمولاً به چند مورچه و تکرار نیاز است؟

پاسخ جهانی وجود ندارد، اما یک نقطه شروع عملی این است که تعداد مورچه‌ها را برابر با تعداد گره‌های گراف قرار دهید و برای چند صد تکرار اجرا کنید. تشخیص سکون — توقف زمانی که بهترین راه‌حل برای تعداد ثابتی از تکرارها بهبود نیافته است — می‌تواند محاسبات را ذخیره کند. اگر یک بودجه سخت کمتر از حدود ۱۰۰ تا ۲۰۰ تکرار اعمال شود، بعید است ACO نتایج قابل اعتمادی تولید کند؛ Tabu Search انتخاب بهتری در این رژیم است.

روش‌های مرتبط

منابع

  1. Dorigo, M. & Gambardella, L.M. (1997). Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66.

    باز کردن مرجع DOI
    کپی شد.
  2. Dorigo, M. & Stützle, T. (2004). Ant Colony Optimization. MIT Press.

    شابک: 9780262042192
    کپی شد.