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

بهینه‌سازی شبیه‌سازی شده چندهدفه (MOSA)

معرفی‌شده توسط
Serafini, P.; Czyzak, P. and Jaszkiewicz, A.
سال
1992–1998
نوع
Metaheuristic / Pareto-based optimizer
خانواده
Simulation / optimization

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

اندازه قلم

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

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

شهود پشت روش

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

تاریخ

شبیه‌سازی شبیه‌سازی شده توسط کرک‌پاتریک و همکاران در سال 1983 معرفی شد. سرافینی (1992) از اولین کسانی بود که به طور رسمی گسترش آن را به اهداف چندگانه پیشنهاد داد. چزاک و یاشکیویچ (1998) شبیه‌سازی شبیه‌سازی شده پرتو (PSA) را توسعه دادند که آرشیو پرتو را به عنوان ساختار خروجی مرکزی ایجاد کرد و فرمول‌بندی معیار پذیرش را که امروزه به طور گسترده پذیرفته شده است، ارائه داد. از آن زمان MOSA در طراحی مهندسی، زمان‌بندی و لجستیک به کار گرفته شده است.

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

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

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

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

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

نقاط قوت

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

کاربردها

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

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

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

1

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

2

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

3

تمام توابع هدف را برای همسایه کاندید ارزیابی کنید. تعیین کنید که آیا نسبت به راه‌حل فعلی و راه‌حل‌های موجود در آرشیو پرتو، مغلوب می‌کند، مغلوب می‌شود، یا غیرمغلوب است. کاندیدهای غیرمغلوب به آرشیو اضافه می‌شوند؛ اعضای مغلوب آرشیو حذف می‌شوند.

4

یک معیار پذیرش چندهدفه اعمال کنید. اگر همسایه نسبت به راه‌حل فعلی غیرمغلوب باشد، پذیرفته می‌شود. اگر مغلوب باشد، همچنان با احتمال P = exp(−ΔF / T) پذیرفته می‌شود که در آن ΔF وخامت اهداف را تجمیع می‌کند و امکان فرار از جبهه‌های پرتو محلی را فراهم می‌آورد.

فرمول
P(\text{accept}) = \exp\!\left(-\frac{\Delta f}{T}\right)
5

دما را طبق یک برنامه خنک‌کاری، معمولاً هندسی، کاهش دهید: T_{k+1} = α · T_k با α ∈ (0.8, 0.99). دماهای پایین‌تر پذیرش حرکات پائین‌تر را محدود می‌کنند و به تدریج جستجو را در نزدیکی مناطق امیدوارکننده جبهه پرتو تشدید می‌کنند.

فرمول
T_{k+1} = \alpha \cdot T_k, \quad \alpha \in (0,1)
6

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

دام‌های رایج

  • تنظیم دمای اولیه خیلی پایین منجر به همگرایی زودهنگام به یک منطقه محلی از جبهه پرتو می‌شود؛ همیشه T_0 را طوری کالیبره کنید که نرخ پذیرش اولیه حدود 70 تا 90 درصد باشد.
  • استفاده از نرخ خنک‌کاری α که خیلی نزدیک به 1.0 است، اجرای الگوریتم را به طور غیرقابل تحملی طولانی می‌کند؛ خیلی نزدیک به 0 باعث همگرایی سریع قبل از کاوش کافی جبهه پرتو می‌شود.
  • تعریف ΔF برای احتمال پذیرش با جمع ساده تفاوت‌های هدف، مقیاس‌های غیرقابل مقایسه را مخلوط می‌کند — هر هدف را قبل از تجمیع نرمال کنید.
  • نادیده گرفتن حذف دوره‌ای راه‌حل‌های مغلوب از آرشیو، آن را متورم کرده و کیفیت خروجی نهایی را کاهش می‌دهد.
  • ارزیابی موفقیت در یک اجرا با توجه به تغییرات تصادفی گمراه‌کننده است؛ همیشه نتایج را بر اساس چندین اجرای مستقل تجمیع کنید.

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

MOSA چگونه با NSGA-II تفاوت دارد؟

NSGA-II یک الگوریتم تکاملی مبتنی بر جمعیت است که مجموعه‌ای از راه‌حل‌ها را به طور همزمان با استفاده از تقاطع، جهش و مرتب‌سازی غیرمغلوب تکامل می‌دهد. MOSA یک روش مبتنی بر مسیر است که با استفاده از حرکات احتمالی، یک راه‌حل را در یک زمان کاوش می‌کند. MOSA معمولاً پیاده‌سازی ساده‌تری دارد و برای مسائل ترکیبی به خوبی کار می‌کند، در حالی که NSGA-II عموماً پوشش جبهه پرتو بهتری برای مسائل پیوسته ارائه می‌دهد و به طور قابل پیش‌بینی‌تری مقیاس می‌شود.

دمای اولیه T_0 را چگونه باید تنظیم کنم؟

یک روش ابتکاری رایج این است که یک فاز مقدماتی کوتاه اجرا کرده و T_0 را طوری انتخاب کنید که تقریباً 80٪ از حرکات همسایه تصادفی پذیرفته شوند. این امر کاوش گسترده در ابتدا را تضمین می‌کند. کالیبراسیون خاص مسئله توصیه می‌شود زیرا مقیاس دمای مناسب به بزرگی تفاوت‌های تابع هدف بستگی دارد.

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

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

چگونه بفهمم الگوریتم چه زمانی باید متوقف شود؟

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

آیا MOSA برای مدل‌های شبیه‌سازی پرهزینه مناسب است؟

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

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

منابع

  1. Czyzak, P., Jaszkiewicz, A. (1998). Pareto simulated annealing — a metaheuristic technique for multiple-objective combinatorial optimization. Journal of Multi-Criteria Decision Analysis, 7(1), 34–47.

    باز کردن مرجع DOI
    کپی شد.
  2. Serafini, P. (1992). Simulated annealing for multi-objective optimization problems. In Proceedings of the Tenth International Conference on Multiple Criteria Decision Making, Taipei, Taiwan, pp. 87–96.

    باز کردن مرجع انتشار
    کپی شد.