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

بهینه‌سازی کلونی مورچه چندهدفه (MOACO)

معرفی‌شده توسط
Gambardella, Taillard & Agazzi; Dorigo & Stützle
سال
1999
نوع
Population-based metaheuristic
خانواده
Simulation / optimization

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

اندازه قلم

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

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

شهود پشت روش

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

تاریخ

بهینه‌سازی کلونی مورچه توسط مارکو دورایگو در پایان‌نامه دکتری سال ۱۹۹۲ او معرفی شد و با مانزیزو و کولورنی فرموله شد. گسترش‌های چندهدفه در اواخر دهه ۱۹۹۰ پدیدار شدند؛ MACS-VRPTW گامباردلا، تایارد و آگازی (۱۹۹۹) کلونی‌های مورچه متعدد را که اهداف مختلف را هدف قرار می‌دادند، نشان داد. چارچوب‌های بعدی توسط دورنر، هارتل و دیگران، MOACO را به عنوان یک کلاس فرموله کردند و کتاب درسی دورایگو و اشتوتزله در سال ۲۰۰۴ درمان الگوریتمی متعارف را ارائه داد. MOACO همچنان یک حوزه تحقیقاتی فعال با کاربردهایی در مسیریابی شبکه، بیوانفورماتیک و لجستیک پایدار است.

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

هنگامی که مسئله دارای دو یا چند هدف متعارض، فضای راه‌حل ترکیبی یا گسسته (مانند مسیریابی، زمان‌بندی، طراحی شبکه) و ترجیح قبلی قوی بر روی اهداف که توجیه کننده کاهش آنها به یک اسکالر باشد، نیست، از MOACO استفاده کنید. این روش در مسائل لجستیک، زنجیره تأمین و زمان‌بندی گردش کار که ACO در حال حاضر در اهداف منفرد عملکرد خوبی دارد، عالی است. از MOACO زمانی اجتناب کنید که مسئله پیوسته است و روش‌های چندهدفه مبتنی بر گرادیان (مانند NSGA-II با کدگذاری واقعی، یا بهینه‌سازی بیزی) کارآمدتر هستند؛ زمانی که بودجه محاسباتی به شدت محدود است، زیرا MOACO به ارزیابی‌های زیادی نیاز دارد؛ یا زمانی که یک جبهه پارتو دقیق برای مسئله‌ای که برنامه‌ریزی چندهدفه دقیق (مانند MILP چندهدفه) قابل حل است، مورد نیاز است.

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

  • نیاز به تنظیم دقیق چندین ابرپارامتر (α, β, ρ, اندازه کلونی, ظرفیت آرشیو) دارد و حساسیت به این تنظیمات می‌تواند بالا باشد.
  • همگرایی نسبت به حل‌کننده‌های دقیق برای مسائل کوچک و خوش‌ساختار که در آنها روش‌های برنامه‌ریزی عدد صحیح یا پویا قابل حل هستند، کندتر است.
  • کیفیت تقریب و تنوع جبهه پارتو تضمین شده نیست؛ نتایج به دلیل ساختار تصادفی در اجراهای مختلف متفاوت است.
  • مقیاس‌پذیری به فضاهای هدف با ابعاد بالا (بیش از ۳ هدف) دشوار است و ممکن است نیاز به استراتژی‌های تجزیه تخصصی داشته باشد.
  • اثبات همگرایی برای نمونه‌های مسئله دلخواه وجود ندارد؛ تضمین‌های نظری در مقایسه با برنامه‌ریزی ریاضی محدود هستند.

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

نقاط قوت

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

کاربردها

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

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

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

1

ماتریس‌های فرومون (یکی برای هر هدف یا یک ماتریس وزن‌دار مشترک) را با مقادیر یکنواخت مقداردهی اولیه کنید. اطلاعات شهودی η را برای هر جزء راه‌حل تعریف کنید. یک آرشیو پارتو خالی برای ذخیره راه‌حل‌های غیرمغلوب یافت شده در طول جستجو ایجاد کنید.

2

هر مورچه با انتخاب احتمالی اجزای راه‌حل، یک راه‌حل کامل را گام به گام می‌سازد. احتمال انتقال از قدرت فرومون τ و مطلوبیت شهودی η که به توان نمایانگرهای تنظیم α و β رسیده‌اند، استفاده می‌کند. انواع مختلف MOACO ماتریس‌های فرومون را برای هر هدف اختصاص می‌دهند یا از وزن‌های اسکالارسازی استفاده می‌کنند که در بین مورچه‌ها تغییر می‌کنند.

فرمول
p_{ij}^k = \frac{[\tau_{ij}]^\alpha \cdot [\eta_{ij}]^\beta}{\sum_{l \in \mathcal{N}_i^k} [\tau_{il}]^\alpha \cdot [\eta_{il}]^\beta}
3

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

4

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

5

تمام مسیرهای فرومون را با ضریب (۱ - ρ) تبخیر کنید تا اطلاعات قدیمی محو شوند. فرومون جدید را بر روی اجزای راه‌حل متعلق به راه‌حل‌های آرشیو (نخبگان) واریز کنید. مقدار واریز Δτ منعکس کننده کیفیت خاص هدف یا رتبه مبتنی بر ازدحام است و اجزای مرتبط با راه‌حل‌های پارتو بهینه پراکنده را تقویت می‌کند.

فرمول
\tau_{ij} \leftarrow (1 - \rho)\,\tau_{ij} + \sum_{k: s^k \in \mathcal{A}} \Delta\tau_{ij}^k
6

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

دام‌های رایج

  • استفاده از یک ماتریس فرومون مشترک واحد بدون تمایز خاص هدف، اغلب جبهه‌های پارتو جانبدارانه و با پراکندگی ضعیف تولید می‌کند.
  • نادیده گرفتن مدیریت تنوع آرشیو منجر به یک جبهه متراکم در یک منطقه و شکاف‌های بزرگ در مناطق دیگر می‌شود و تصویر گمراه‌کننده‌ای از مبادلات ارائه می‌دهد.
  • تنظیم نرخ تبخیر ρ بیش از حد بالا باعث شستشوی فرومون و از دست رفتن یادگیری انباشته می‌شود؛ بیش از حد پایین منجر به رکود در اطراف راه‌حل‌های زیربهینه می‌شود.
  • مقایسه نتایج MOACO در بین اجراها بدون تکرار آماری (بذر متعدد، شاخص حجم ابر) ارزیابی‌های کیفی گمراه‌کننده‌ای تولید می‌کند.
  • فراموش کردن نرمال‌سازی مقادیر هدف قبل از محاسبه مغلوبیت یا واریز فرومون، جستجو را در زمانی که اهداف مقیاس‌های بسیار متفاوتی دارند، تحریف می‌کند.

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

MOACO چگونه با اجرای ACO تک‌هدفه چندین بار با ترکیب وزن‌های مختلف تفاوت دارد؟

اجراهای ACO تک‌هدفه وزن‌دار نیاز به تعیین وزن‌ها از قبل دارند و هر اجرا تنها یک نقطه پارتو بهینه را تقریب می‌زند. MOACO در یک اجرا آرشیوی از راه‌حل‌های غیرمغلوب در سراسر سطح مبادله تولید می‌کند و به‌روزرسانی فرومون آن راه‌حل‌های با کیفیت بالا و متنوع را به جای یک بهینه اسکالر تقویت می‌کند.

از کدام نوع MOACO باید برای یک مسئله جدید استفاده کنم؟

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

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

پاسخ جهانی وجود ندارد، اما یک پیکربندی شروع رایج برای مسائل ترکیبی با اندازه متوسط، ۲۰ تا ۱۰۰ مورچه در هر کلونی و ۵۰۰ تا ۲۰۰۰ تکرار است. فضاهای راه‌حل بزرگتر و اهداف بیشتر به تکرارهای بیشتری نیاز دارند. همیشه چندین تکرار مستقل اجرا کنید و شاخص‌های حجم ابر یا IGD را که به طور متوسط از بذرها محاسبه شده‌اند، گزارش دهید.

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

ACO استاندارد برای فضاهای گسسته طراحی شده است. انواع MOACO پیوسته (مانند مبتنی بر ACOR) وجود دارند اما به طور کلی در مسائل پیوسته توسط NSGA-II یا MOEA/D بهتر عمل می‌کنند. MOACO را برای مسائل ترکیبی یا عدد صحیح مختلط که در آنها ساختار مبتنی بر گراف آن مزیت طبیعی را می‌دهد، رزرو کنید.

اندازه آرشیو پارتو چگونه باید تنظیم شود؟

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

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

منابع

  1. Gambardella, L. M., Taillard, E., & Agazzi, G. (1999). MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In D. Corne, M. Dorigo, & F. Glover (Eds.), New Ideas in Optimization (pp. 63–76). McGraw-Hill.

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

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