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

بهینه‌سازی چندهدفه مبتنی بر عامل — جستجوی تکاملی غیرمتمرکز در میان اهداف رقیب

معرفی‌شده توسط
Bonabeau, Dorigo, Theraulaz; Coello Coello et al.
سال
1990s–2000s
نوع
Simulation-driven multi-objective search
خانواده
Simulation / optimization

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

اندازه قلم

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

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

شهود پشت روش

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

تاریخ

بهینه‌سازی چندهدفه مبتنی بر عامل در اواخر دهه ۱۹۹۰ و اوایل دهه ۲۰۰۰ ظهور کرد، زیرا محققان چارچوب‌های مدل‌سازی مبتنی بر عامل (NetLogo, Repast, MASON) را با الگوریتم‌های تکاملی چندهدفه ترکیب کردند. کارهای بنیادی Bonabeau, Dorigo, و Theraulaz در مورد هوش ازدحامی و Coello Coello و همکاران در مورد بهینه‌سازی تکاملی چندهدفه، پایه‌های نظری را که در ABMOO ترکیب شده‌اند، بنا نهادند. این رویکرد در طول دهه‌های ۲۰۰۰ و ۲۰۱۰ در علم سیستم‌های پیچیده، برنامه‌ریزی شهری و مدیریت زیست‌محیطی محبوبیت یافت.

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

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

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

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

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

نقاط قوت

  • چشم‌اندازهای هدف غیرخطی، نوظهور و وابسته به مسیر را که در برابر فرمول‌بندی فرم بسته مقاومت می‌کنند، مدیریت می‌کند.
  • یک جبهه پارتو کامل تولید می‌کند و به تصمیم‌گیرندگان دید صریح از بده‌بستان‌ها به جای یک نقطه واحد می‌دهد.
  • به طور طبیعی با میانگین‌گیری تکرارهای شبیه‌سازی در ارزیابی برازندگی، با تصادفی بودن سازگار می‌شود.
  • با جمعیت‌های عامل ناهمگن با قوانین رفتاری متنوع و توپولوژی‌های تعاملی، مقیاس‌پذیر است.
  • با الگوریتم‌های چندهدفه تثبیت‌شده (NSGA-II, MOEA/D, MOPSO) به عنوان محرک بهینه‌سازی سازگار است.

کاربردها

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

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

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

1

تعداد m هدف f_1, ..., f_m (که همگی باید کمینه یا بیشینه شوند) و متغیرهای تصمیم‌گیری که در ژنوم یا مجموعه قوانین هر عامل رمزگذاری شده‌اند را فهرست کنید. محدودیت‌ها و محیط شبیه‌سازی را که تصمیمات عامل را به نتایج قابل مشاهده تبدیل می‌کند، تعریف کنید.

2

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

3

شبیه‌سازی مبتنی بر عامل را برای T گام زمانی به جلو اجرا کنید. در پایان هر اجرا، مقادیر هدف f_1(x), ..., f_m(x) را برای هر عامل یا برای سیستم جمعی بخوانید. ممکن است چندین تکرار برای مدیریت نویز تصادفی میانگین‌گیری شوند.

4

مرتب‌سازی غیرمغلوب را اعمال کنید: عامل‌ها را بر اساس تسلط پارتو رتبه‌بندی کنید. یک عامل x عامل y را مغلوب می‌کند اگر x در تمام اهداف بدتر نباشد و حداقل در یکی بهتر باشد. جبهه غیرمغلوب (جبهه پارتو) را حفظ کنید و از فاصله ازدحام یا مشارکت حجم (hypervolume) برای حفظ تنوع استفاده کنید.

5

عملگرهای ژنتیکی (تقاطع، جهش) یا به‌روزرسانی‌های سرعت به سبک ازدحام را به جمعیت بازمانده اعمال کنید. عامل‌های کاندید جدید ژنوم اعضای جبهه پارتو را به ارث می‌برند، ترکیب می‌کنند یا بر هم می‌زنند، سپس برای ارزیابی مجدداً وارد شبیه‌سازی می‌شوند.

6

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

دام‌های رایج

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

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

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

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

کدام الگوریتم چندهدفه به عنوان بهینه‌ساز در ABMOO بهترین عملکرد را دارد؟

NSGA-II به دلیل مرتب‌سازی غیرمغلوب و فاصله ازدحام، پرکاربردترین است. MOEA/D و MOPSO نیز رایج هستند. انتخاب به شکل و ابعاد جبهه پارتو بستگی دارد؛ انتخاب بهترین جهانی وجود ندارد - ابتدا در یک اجرای کوچک محک بزنید.

چند تکرار شبیه‌سازی را باید برای هر ارزیابی عامل اجرا کنم؟

به اندازه‌ای که نویز را کاهش دهد تا مقایسه‌های تسلط پارتو قابل اعتماد باشند. یک قاعده سرانگشتی رایج این است که تا زمانی که ضریب تغییرات هر هدف به زیر ۵ تا ۱۰ درصد کاهش یابد، اجرا کنید. این ممکن است بسته به تصادفی بودن سیستم به ۱۰ تا ۵۰ تکرار نیاز داشته باشد.

آیا ABMOO می‌تواند بیش از دو هدف را مدیریت کند؟

بله، اما عملکرد با افزایش تعداد اهداف کاهش می‌یابد (نفرین ابعاد در تسلط پارتو). فراتر از سه هدف، الگوریتم‌های چندهدفه مانند NSGA-III یا MOEA/D را در نظر بگیرید و از تکنیک‌های تجسم کاهش ابعاد برای جبهه حاصل استفاده کنید.

چه زمانی باید بهینه‌سازی قوی (robust optimization) را به ABMOO استاندارد ترجیح دهم؟

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

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

منابع

  1. Bonabeau, E., Dorigo, M., & Theraulaz, G. (2002). Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press.

    شابک: 9780195131598
    کپی شد.
  2. Coello Coello, C. A., Lamont, G. B., & Van Veldhuizen, D. A. (2007). Evolutionary Algorithms for Solving Multi-Objective Problems (2nd ed.). Springer.

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