بهینهسازی تصادفی چندهدفه — بهینهسازی چندین هدف متعارض تحت عدم قطعیت
- معرفیشده توسط
- Various (Fonseca, Fleming, Deb, Zitzler, and others)
- سال
- 1990s–2000s
- نوع
- Stochastic metaheuristic optimization
- خانواده
- Simulation / optimization
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
بهینهسازی تصادفی چندهدفه (SMOO) دستهای از روشها است که به طور همزمان دو یا چند هدف متعارض را در زمانی که پارامترها، هزینهها یا محدودیتها نامشخص یا تصادفی هستند، بهینهسازی میکند. به جای یک راهحل بهینه واحد، مجموعهای از راهحلهای پارتو غیرمغلوب را تولید میکند که هر کدام نمایانگر تعادل متفاوتی بین اهداف تحت عدم قطعیت مدلسازی شده است.
شهود پشت روش
بیشتر تصمیمات واقعی شامل بدهبستان بین چندین هدف است — کاهش هزینه ضمن افزایش کیفیت و سرعت — و جهان نامشخص است. SMOO تصدیق میکند که مقادیر تابع هدف اعداد ثابت نیستند بلکه متغیرهای تصادفی هستند که تحت تأثیر ورودیهای نامشخص مانند تقاضا، قیمتها یا نرخهای خرابی شکل میگیرند. با نمونهبرداری یا انتشار تحلیلی آن عدم قطعیت از طریق ارزیابیهای چندهدفه، این روش مجموعهای از راهحلهای بدهبستان قوی را پیدا میکند که در طول تحققهای واقعی عدم قطعیت غیرمغلوب باقی میمانند و به تصمیمگیرندگان به جای پاسخهای واحد با دقت کاذب، انتخابهای صادقانه ارائه میدهد.
تاریخ
بهینهسازی چندهدفه تحت عدم قطعیت در دهه ۱۹۹۰ همزمان با ظهور بهینهسازی چندهدفه تکاملی پدیدار شد. مشارکتهای بنیادی توسط Fonseca و Fleming (۱۹۹۳) و Deb و همکاران (۲۰۰۲) چارچوبهای تکاملی مبتنی بر پارتو را ایجاد کردند. ادغام عناصر تصادفی — از طریق اهداف مقدار مورد انتظار، محدودیتهای احتمالی، و رویکردهای مبتنی بر سناریو — از طریق دهه ۲۰۰۰ و ۲۰۱۰ به یک حوزه تحقیقاتی فعال تبدیل شد، که با قدرت محاسباتی فزاینده که جستجوی فشرده مونت کارلو را ممکن میساخت، پشتیبانی میشد.
چه زمانی استفاده شود
هنگامی که دو یا چند هدف واقعاً متعارض وجود دارد و پارامترهای کلیدی (تقاضا، هزینهها، مدت زمان، احتمالات خرابی) نامشخص یا متغیر هستند، از SMOO استفاده کنید. این روش برای طراحی مهندسی تحت عدم قطعیت، برنامهریزی زنجیره تأمین، بهینهسازی سبد انرژی، و ارزیابی سیاست با معیارهای رفاه چندگانه مناسب است. زمانی که تمام پارامترها قطعی هستند (به جای آن از MOO استاندارد استفاده کنید)، زمانی که فقط یک هدف مهم است (از بهینهسازی تکهدفه تصادفی استفاده کنید)، زمانی که عدم قطعیت معرفتی و غیرقابل کمیسازی است، یا زمانی که بودجه محاسباتی برای پشتیبانی از ارزیابیهای مکرر تابع تصادفی بیش از حد محدود است (هر راهحل کاندید ممکن است به دهها تا هزاران نمونه مونت کارلو نیاز داشته باشد)، از آن استفاده نکنید.
محدودیتها و ملاحظات
- از نظر محاسباتی پرهزینه: هر ارزیابی تابع نیازمند نمونهبرداری مونت کارلو یا شمارش سناریو است که در تعداد ارزیابیهای مورد نیاز برای جستجوی چندهدفه ضرب میشود.
- نتایج به شدت به کیفیت مدل عدم قطعیت بستگی دارد؛ فرضیات توزیعی نادرست منجر به جبهههای پارتوی گمراهکننده میشود.
- همگرایی به جبهه پارتوی تصادفی واقعی دشوارتر از حالت قطعی تضمین میشود؛ اطمینان به نتایج نیازمند تحلیل آماری دقیق است.
- تعداد زیاد راهحلهای پارتو بدون ابزارهای مؤثر بصریسازی یا بیان ترجیحات میتواند تصمیمگیرندگان را سردرگم کند.
- نیاز به داده کافی یا دانش دامنه برای مشخص کردن توزیعهای عدم قطعیت برای هر پارامتر نامشخص دارد.
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- به طور صریح عدم قطعیت در مقادیر هدف را در نظر میگیرد و راهحلهایی تولید میکند که نسبت به تغییرات پارامتر قوی هستند، نه اینکه فقط تحت مقادیر ثابت مفروض بهینه باشند.
- مجموعهای کامل از راهحلهای بدهبستان پارتو را تولید میکند و خودمختاری تصمیمگیرنده را برای انتخاب بین جایگزینها بر اساس ترجیح حفظ میکند.
- سازگار با طیف گستردهای از نمایشهای عدم قطعیت (توزیعها، سناریوها، مجموعههای ابهام) و موتورهای بهینهسازی (الگوریتمهای تکاملی، تجزیه، روشهای کمکی جایگزین).
- روابط تسلط تصادفی را بین راهحلها که MOO قطعی قادر به درک آن نیست، ثبت میکند.
- در دامنههای متنوعی از جمله مهندسی، لجستیک، مالی و سیاست عمومی قابل اجرا است.
کاربردها
- طراحی مهندسی: بهینهسازی همزمان وزن سازه، هزینه و قابلیت اطمینان زمانی که خواص مواد نامشخص هستند.
- مدیریت زنجیره تأمین: متعادل کردن هزینه، سطح خدمات و انتشار کربن تحت تقاضا و زمانهای تحویل نامشخص.
- سیستمهای انرژی: برنامهریزی سبدهای تولید که هزینه و انتشار را با حداقل رساندن در حالی که اهداف قابلیت اطمینان را تحت خروجی متغیر تجدیدپذیر برآورده میکنند.
- بهینهسازی سبد مالی: حداکثر کردن بازده مورد انتظار ضمن حداقل رساندن ریسک (CVaR) تحت بازده دارایی نامشخص.
- طراحی شبکه حمل و نقل: حداقل رساندن زمان سفر و هزینه زیرساخت تحت تقاضای ترافیک نامشخص آینده.
- تخصیص منابع مراقبتهای بهداشتی: متعادل کردن نتایج درمان و بودجه تحت نرخهای ورود بیمار و اثربخشی درمان نامشخص.
چگونه کار میکند
چگونه کار میکند
بردار توابع هدف f(x) = [f1(x,xi), f2(x,xi), ..., fk(x,xi)] را تعریف کنید که در آن x بردار متغیر تصمیم و xi پارامترهای نامشخص را نشان میدهد. حدود متغیر تصمیم، محدودیتهای قطعی و تصادفی، و ساختار عدم قطعیت (توزیعها، سناریوها، یا مجموعههای ابهام) را مشخص کنید.
پارامترهای نامشخص را از طریق توزیعهای احتمال (مانند نرمال، یکنواخت، تجربی)، مجموعههای سناریوی گسسته با احتمالات مرتبط، یا مجموعههای ابهام قوی نمایش دهید. نمایشی را انتخاب کنید که با دادههای موجود مطابقت داشته باشد: رویکردهای مبتنی بر سناریو به فرضیات توزیعی کمتری نیاز دارند؛ مدلهای توزیعی کامل امکان نمونهبرداری مونت کارلو را فراهم میکنند.
یک الگوریتم جستجوی چندهدفه — معمولاً یک الگوریتم تکاملی مانند NSGA-II، MOEA/D، یا SPEA2، یا تجزیه برنامهریزی ریاضی — را برای کاوش فضای تصمیم و حفظ جمعیتی یا آرشیوی از راهحلهای غیرمغلوب کاندید در طول تکرارها اعمال کنید.
برای هر راهحل کاندید x که در طول جستجو مشاهده میشود، اهداف تصادفی را با محاسبه مقادیر مورد انتظار E[fi(x,xi)]، واریانسها، ارزش در معرض خطر شرطی (CVaR)، یا مقادیر میانگین سناریو از طریق نمونهبرداری مونت کارلو یا انتگرالگیری تحلیلی ارزیابی کنید. این کار ارزیابیهای تابع قطعی را با تخمینهای برازش آماری قوی جایگزین میکند.
آرشیو غیرمغلوب را با استفاده از روابط تسلط پارتو که بر روی مقادیر تخمینی اهداف تصادفی اعمال میشود، بهروزرسانی و هرس کنید. راهحل x بر راهحل x' تسلط دارد اگر بردار هدف تخمینی آن در تمام ابعاد بدتر نباشد و حداقل در یک بعد بهتر باشد، با در نظر گرفتن عدم قطعیت تخمین در صورت نیاز.
جبهه پارتوی تصادفی تخمینی را به تصمیمگیرندگان ارائه دهید، همراه با فواصل اطمینان یا توزیعهای احتمال بر روی اهداف برای هر راهحل پارتو. امکان انتخاب راهحل ترجیحی را با استفاده از مقیاسبندی تابع ارزش، روشهای نقطه مرجع، یا تحلیل بدهبستان تعاملی فراهم کنید.
دامهای رایج
- استفاده از نمونههای مونت کارلو بسیار کم در هر ارزیابی منجر به تخمینهای برازش نویزی میشود که مقایسههای تسلط پارتو را فاسد کرده و جستجو را گمراه میکند.
- در نظر گرفتن اهداف نامشخص به صورت قطعی با جایگزینی مقادیر میانگین پارامتر، واریانس را نادیده میگیرد و میتواند راهحلهایی تولید کند که در تحققهای واقعی عملکرد ضعیفی دارند.
- درهم آمیختن بهینهسازی قوی (بدترین حالت) با بهینهسازی تصادفی (مقدار مورد انتظار): این دو فرمولبندی جبهههای پارتوی متفاوتی تولید میکنند و برای نگرشهای ریسک متفاوت مناسب هستند.
- نادیده گرفتن عدم قطعیت محدودیتها: عدم مدلسازی محدودیتهای تصادفی به عنوان محدودیتهای احتمالی یا محدودیتهای مقدار مورد انتظار، منجر به راهحلهای غیرعملی در عمل میشود.
- گزارش جبهه پارتو بدون فواصل اطمینان، ذینفعان را گمراه میکند تا باور کنند که تخمینهای هدف دقیق هستند.
پرسشهای متداول
تفاوت SMOO با بهینهسازی چندهدفه استاندارد (قطعی) چیست؟
در MOO قطعی، مقادیر تابع هدف برای یک بردار تصمیم معین ثابت هستند. در SMOO، اهداف متغیرهای تصادفی هستند زیرا برخی پارامترها نامشخص هستند. هر راهحل کاندید باید با تخمین عملکرد مورد انتظار آن (یا معیار ریسک) در طول تحققهای عدم قطعیت، معمولاً از طریق نمونهبرداری مونت کارلو، ارزیابی شود و این امر بهینهسازی را به طور قابل توجهی از نظر محاسباتی پرهزینهتر میکند.
چه تعداد نمونه مونت کارلو در هر ارزیابی راهحل مورد نیاز است؟
قانون جهانی وجود ندارد؛ این بستگی به واریانس اهداف و دقت تخمین مورد نیاز دارد. نقطه شروع رایج ۱۰۰ تا ۱۰۰۰ نمونه در هر ارزیابی است، اما متخصصان باید یک مطالعه آزمایشی برای ارزیابی تعداد نمونههای مورد نیاز برای تولید تخمینهای برازش پایدار و رتبهبندیهای پارتوی پایدار انجام دهند.
آیا میتوانم از هر الگوریتم چندهدفه به عنوان موتور جستجو استفاده کنم؟
بله. NSGA-II، MOEA/D، SPEA2 و سایر الگوریتمهای مبتنی بر پارتو یا مبتنی بر تجزیه را میتوان با جایگزینی ارزیابیهای تابع قطعی با ارزیابیهای تصادفی تطبیق داد. انواع کمکی جایگزین به طور فزایندهای محبوب میشوند تا تعداد ارزیابیهای تصادفی پرهزینه را کاهش دهند.
از چه معیار ریسکی باید برای اهداف تصادفی استفاده کنم؟
این بستگی به زمینه تصمیم دارد. مقدار مورد انتظار برای ذینفعان ریسکگریز مناسب است؛ واریانس یا انحراف معیار تغییرپذیری را جریمه میکند؛ CVaR (ارزش در معرض خطر شرطی) ریسک دم را برای تنظیمات ریسکگریز ثبت میکند. برای قابلیت اطمینان مهندسی، احتمال برآورده شدن محدودیت (محدودیتهای احتمالی) اغلب معنادارتر از مقدار مورد انتظار است.
آیا بهینهسازی قوی همان بهینهسازی چندهدفه تصادفی است؟
خیر. بهینهسازی قوی معمولاً از مدلهای عدم قطعیت بدترین حالت (فرمولبندیهای حداقل-حداکثر) بدون نیاز به توزیعهای احتمال استفاده میکند. SMOO از مدلهای احتمالی استفاده میکند و مقادیر هدف مورد انتظار یا تعدیل شده با ریسک را بهینه میکند. هر دو به عدم قطعیت میپردازند، اما نگرشهای ریسک متفاوتی را رمزگذاری میکنند و به انواع مختلفی از اطلاعات عدم قطعیت نیاز دارند.
روشهای مرتبط
منابع
Deb, K. (2001). Multi-Objective Optimization Using Evolutionary Algorithms. Wiley, Chichester.
شابک: 9780471873396کپی شد.Caramia, M., Dell'Olmo, P. (2008). Multi-Objective Management in Freight Logistics. Springer, London.
باز کردن مرجع DOIکپی شد.