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

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

معرفی‌شده توسط
Dorigo, M. and colleagues; agent-based framing developed in swarm intelligence community
سال
1992-2004
نوع
Metaheuristic optimization — agent-based swarm simulation
خانواده
Simulation / optimization

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

اندازه قلم

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

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

شهود پشت روش

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

تاریخ

بهینه‌سازی کلونی مورچه توسط مارکو دورگو در پایان‌نامه دکتری سال ۱۹۹۲ او معرفی شد و در سال ۲۰۰۴ با اشتوتزله رسمی شد. دیدگاه مبتنی بر عامل از چارچوب گسترده‌تر هوش ازدحامی (Bonabeau, Dorigo, Theraulaz 1999) پدیدار شد که مورچه‌ها را به عنوان عامل‌های خودمختار با هماهنگی استیگمرژیک معرفی کرد. جفت کردن ACO با محیط‌های شبیه‌سازی مبتنی بر عامل در تحقیقات لجستیک، زنجیره تأمین و سیستم‌های چند عاملی در طول دهه‌های ۲۰۰۰ و ۲۰۱۰ برجسته شد.

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

هنگامی که با مسائل بهینه‌سازی ترکیبی (مسیریابی، زمان‌بندی، تخصیص، طراحی شبکه) مواجه هستید که فضای جستجو برای روش‌های دقیق بسیار بزرگ است و جستجوی تصادفی مبتنی بر جمعیت توجیه‌پذیر است، از AB-ACO استفاده کنید. این روش زمانی برتری دارد که مسئله را بتوان به عنوان پیمایش گراف در نظر گرفت و زمانی که هماهنگی توزیع‌شده و نوظهور بر کنترل متمرکز ترجیح داده می‌شود. این روش به ویژه برای مسائل پویا یا تعبیه‌شده در شبیه‌سازی که در آن ارزیابی برازندگی شامل اجرای یک شبیه‌سازی مبتنی بر عامل است، مناسب است. از آن برای چشم‌اندازهای بهینه‌سازی پیوسته هموار (روش‌های گرادیانی غالب هستند)، برای مسائل بسیار کوچک (حل‌کننده‌های دقیق کافی هستند)، یا زمانی که بودجه تنظیم پارامتر فرومون در دسترس نیست، اجتناب کنید — پارامترهای alpha/beta/rho با تنظیم نادرست می‌توانند منجر به همگرایی زودهنگام شوند.

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

  • عملکرد به انتخاب alpha، beta و rho حساس است؛ اغلب به تنظیم دقیق گسترده پارامتر یا بهینه‌سازی فرعی نیاز است.
  • سرعت همگرایی به طور کلی کندتر از روش‌های تک راه‌حل (مانند جستجوی ممنوعه) در مسائل ایستا با ساختار واضح است.
  • رکود فرومون — که در آن همه عامل‌ها یک مسیر زیربهینه را دنبال می‌کنند — می‌تواند در صورتی رخ دهد که تبخیر خیلی کند باشد یا جمعیت خیلی کوچک باشد.
  • تضمین‌های همگرایی نظری فقط تحت شرایط محدودکننده وجود دارند؛ اعتبارسنجی تجربی معمولاً مورد نیاز است.
  • سربار حافظه و ارتباطات نگهداری یک ماتریس فرومون جهانی با تعداد اجزای راه‌حل افزایش می‌یابد.

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

نقاط قوت

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

کاربردها

  • مسیریابی وسایل نقلیه و برنامه‌ریزی لجستیک که در آن عامل‌های مورچه برنامه‌های تحویل کارآمد را کشف می‌کنند.
  • پروتکل‌های مسیریابی شبکه در مخابرات که در آن مورچه‌ها مسیرها را بررسی کرده و فرومون مسیریابی را نهشت می‌کنند.
  • بهینه‌سازی زنجیره تأمین با ادغام AB-ACO با مدل‌های شبیه‌سازی رویداد گسسته یا مبتنی بر عامل.
  • زمان‌بندی تولید انعطاف‌پذیر و زمان‌بندی خط تولید که در آن عامل‌ها ماشین‌ها یا وظایف را نشان می‌دهند.
  • مشکلات تاشدگی پروتئین و هم‌ترازی توالی بیوانفورماتیک که به عنوان پیمایش گراف در نظر گرفته می‌شوند.
  • برنامه‌ریزی مسیر تخلیه در شبیه‌سازی‌های شهری مبتنی بر عامل با مدل‌سازی ازدحام پویا.

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

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

1

مسئله بهینه‌سازی را به عنوان یک گراف ساختاری تعریف کنید که در آن گره‌ها اجزای راه‌حل را نشان می‌دهند و یال‌ها سطوح فرومون و مقادیر مطلوبیت اکتشافی را حمل می‌کنند. تعداد عامل‌ها m، نرخ تبخیر rho، پارامترهای تأثیر alpha (فرومون) و beta (اکتشافی)، و معیار توقف را مشخص کنید.

2

m عامل مورچه را در گره‌های شروع تصادفی یا اکتشافی قرار دهید. تمام ردپاهای فرومون tau_ij را به یک مقدار یکنواخت کوچک tau_0 مقداردهی اولیه کنید تا از سوگیری زودهنگام جلوگیری شود. هر عامل لیست ممنوعه یا راه‌حل در حال ساخت خود را حفظ می‌کند.

3

هر عامل در طول گراف تکرار می‌کند و جزء بعدی j را از همسایگی ممکن N_i^k خود با احتمال p_ij متناسب با tau_ij^alpha * eta_ij^beta انتخاب می‌کند. اکتشافی eta_ij راهنمایی خاص مسئله (به عنوان مثال، فاصله معکوس) را رمزگذاری می‌کند. این قانون تصادفی، اکتشاف را با بهره‌برداری از گرادیان‌های فرومون آموخته‌شده متعادل می‌کند.

فرمول
p_{ij}^k = \frac{[\tau_{ij}]^\alpha [\eta_{ij}]^\beta}{\sum_{l \in N_i^k} [\tau_{il}]^\alpha [\eta_{il}]^\beta}
4

پس از اینکه همه عامل‌ها راه‌حل‌ها را تکمیل کردند، برازندگی هر راه‌حل را ارزیابی کنید. فرومون را به‌روزرسانی کنید: تمام ردپاها را با ضریب (1-rho) تبخیر کنید، سپس یال‌های استفاده‌شده توسط راه‌حل‌های خوب را با Delta_tau_ij^k متناسب با کیفیت راه‌حل تقویت کنید. به طور اختیاری اقدامات دیمون مانند تقویت بهترین جهانی را اعمال کنید.

فرمول
\tau_{ij} \leftarrow (1-\rho)\tau_{ij} + \sum_{k=1}^{m} \Delta\tau_{ij}^k
5

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

دام‌های رایج

  • تنظیم rho خیلی پایین باعث تجمع فرومون می‌شود که کلونی را در اوایل اجرا در یک بهینه محلی قفل می‌کند.
  • حذف یک جزء اکتشافی (eta = 1) دانش دامنه را هدر می‌دهد و همگرایی در مسائل ساختاریافته مانند TSP را کند می‌کند.
  • استفاده از تعداد کمی عامل تنوع را کاهش می‌دهد؛ استفاده از تعداد زیاد هزینه ارزیابی را بدون افزایش کیفیت متناسب افزایش می‌دهد — m را نسبت به اندازه مسئله کالیبره کنید.
  • اشتباه گرفتن AB-ACO با ACO استاندارد: اگر عامل‌ها فاقد وضعیت فردی، حافظه یا ناهمگونی رفتاری باشند، مدل به ACO ساده کاهش می‌یابد و چارچوب مبتنی بر عامل ارزشی اضافه نمی‌کند.
  • اعمال AB-ACO به فضاهای پیوسته بدون مرحله گسسته‌سازی یا جاسازی گراف منجر به عملکرد ضعیف می‌شود؛ در عوض از انواع ACO پیوسته استفاده کنید.

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

AB-ACO چگونه با ACO استاندارد تفاوت دارد؟

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

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

پاسخ جهانی وجود ندارد. یک نقطه شروع رایج برای مسائل با اندازه متوسط، m = ۱۰-۵۰ عامل و ۱۰۰-۵۰۰ تکرار است. چشم‌اندازهای بزرگتر و پیچیده‌تر به موارد بیشتری نیاز دارند. نمودارهای همگرایی (بهترین راه‌حل در مقابل تکرار) همیشه باید برای تأیید اکتشاف کافی بررسی شوند.

آیا AB-ACO می‌تواند مسائل چندهدفه را مدیریت کند؟

بله. افزونه‌های چندهدفه (مانند MOPACO، Pareto-ACO) ماتریس‌های فرومون جداگانه برای هر هدف حفظ می‌کنند یا از تسلط پارِتو برای هدایت به‌روزرسانی‌ها استفاده می‌کنند. فرمول‌بندی مبتنی بر عامل می‌تواند علاوه بر این اهداف عامل فردی و پروفایل‌های ترجیحی را ردیابی کند.

تبخیر فرومون چیست و چرا اهمیت دارد؟

تبخیر تمام سطوح فرومون را در هر تکرار با ضریب (۱-rho) کاهش می‌دهد و تضمین می‌کند که اطلاعات قدیمی از بین می‌رود و کلونی می‌تواند سازگار شود. بدون تبخیر، فرومون به طور نامحدود تجمع می‌یابد و باعث همگرایی زودهنگام می‌شود. نرخ rho یکی از حیاتی‌ترین پارامترها برای تنظیم است.

آیا AB-ACO برای بهینه‌سازی بی‌درنگ یا آنلاین مناسب است؟

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

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

منابع

  1. Dorigo, M., Stutzle, T. (2004). Ant Colony Optimization. MIT Press, Cambridge, MA.

    شابک: 9780262042192
    کپی شد.
  2. Bonabeau, E., Dorigo, M., Theraulaz, G. (1999). Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, New York.

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