Stochastic NSGA-II — بهینهسازی چندهدفه تکاملی تحت عدم قطعیت
- معرفیشده توسط
- Deb, K. et al. (NSGA-II base); Hughes, E. J. and subsequent researchers for stochastic extensions
- سال
- 2001–2002
- نوع
- Evolutionary multi-objective optimization under uncertainty
- خانواده
- Simulation / optimization
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
Stochastic NSGA-II الگوریتم تکاملی NSGA-II را برای مدیریت توابع هدفی که نویزی، نامطمئن یا احتمالی هستند، گسترش میدهد. با میانگینگیری یا نمونهبرداری از اهداف تصادفی در ارزیابیهای متعدد، راهحلهای بهینه پارتو را شناسایی میکند که در برابر عدم قطعیت مقاوم هستند و آن را برای طراحی مهندسی، زنجیره تأمین و مسائل بهینهسازی خطمشی که در آن تغییرپذیری دنیای واقعی اهمیت دارد، مناسب میسازد.
شهود پشت روش
NSGA-II یکی از مؤثرترین الگوریتمها برای یافتن مجموعهای متنوع از راهحلهای مصالحه بهینه پارتو در مسائل چندهدفه است. با این حال، نسخه استاندارد فرض میکند ارزیابی اهداف قطعی هستند. در عمل، شبیهسازیها، آزمایشها و سیستمهای واقعی اغلب خروجیهای نویزی برمیگردانند. Stochastic NSGA-II با نمونهبرداری مجدد یا تخمین آماری برازش (fitness) واقعی هر راهحل به این موضوع میپردازد، سپس از مرتبسازی سریع غیرمغلوب و انتخاب فاصله ازدحام NSGA-II برای پیمایش قابل اعتماد جبهه پارتو علیرغم نویز استفاده میکند. بینش کلیدی این است که رتبهبندی راهحلها بر اساس عملکرد مورد انتظار — یا احتمال غلبه آنها — حتی زمانی که ارزیابیهای فردی غیرقابل اعتماد هستند، ساختار صحیح پارتو را بازیابی میکند.
تاریخ
NSGA-II در سال 2002 توسط Deb و همکاران به عنوان یک الگوریتم ژنتیکی سریع و نخبهگرا برای مسائل چندهدفه معرفی شد و به سرعت به یک استاندارد معیار تبدیل شد. پس از مدت کوتاهی، نسخههای تکاملی تصادفی با انگیزه جوامع بهینهسازی مهندسی که نیاز به مدیریت نویز شبیهسازی داشتند، پدیدار شدند. Hughes (2001) رتبهبندی چندهدفه تحت عدم قطعیت را به طور رسمی بیان کرد. از اواسط دهه 2000، انواع متعددی ظاهر شدهاند که شامل نمونهبرداری تطبیقی، احتمال غلبه و بهبود حجم هایپروولوم مورد انتظار تحت نویز میشوند.
چه زمانی استفاده شود
هنگامی که با یک مسئله بهینهسازی چندهدفه روبرو هستید که در آن اهداف از طریق شبیهسازی، آزمایش یا سنسورهای نویزی ارزیابی میشوند و به راهحلهایی نیاز دارید که در دامنه عدم قطعیت خوب باقی بمانند — نه فقط به طور متوسط — از Stochastic NSGA-II استفاده کنید. این روش به ویژه برای طراحی مهندسی تحت تلرانسهای تولید، بهینهسازی زنجیره تأمین با عدم قطعیت تقاضا، و مدلهای زیستمحیطی یا خطمشی با ورودیهای تصادفی مناسب است. زمانی که اهداف قطعی و ارزیابی آنها ارزان است (NSGA-II استاندارد کافی است)، زمانی که تعداد تکرارهای مورد نیاز برای تخمین قابل اعتماد، بودجه کل را غیرعملی میکند، یا زمانی که مسئله تکهدفه است (به جای آن از EAs تکهدفه تصادفی استفاده کنید) از آن استفاده نکنید. از آن زمانی که توزیع نویز بسیار ناهمگن یا ساختاریافته به گونهای است که فرض نمونهبرداری i.i.d. را نقض میکند، اجتناب کنید.
محدودیتها و ملاحظات
- هزینه محاسباتی با تعداد تکرار r در هر ارزیابی، ضرب در اندازه جمعیت و نسلها مقیاس میشود — برای شبیهسازیهای گرانقیمت میتواند نامتناسب شود.
- انتخاب تعداد مناسب تکرار r غیر بدیهی است: تعداد کم باعث خطاهای رتبهبندی میشود، تعداد زیاد بودجه را هدر میدهد.
- هیچ تضمین همگرایی رسمی به جبهه پارتو تصادفی واقعی وجود ندارد؛ کیفیت به بودجه و سطح نویز بستگی دارد.
- مقایسههای غلبه با استفاده از میانگینهای تخمینی، عدم قطعیت تخمین را نادیده میگیرد، که میتواند باعث رتبهبندی نادرست در نویز بالا شود.
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- یافتههای قوی جبهه پارتو و حفظ تنوع NSGA-II را از طریق مرتبسازی غیرمغلوب و فاصله ازدحام به ارث میبرد.
- به طور صریح نویز تابع هدف را در نظر میگیرد و راهحلهایی تولید میکند که در استقرار دنیای واقعی مقاوم و قابل اعتماد هستند.
- چارچوب انعطافپذیر — تخمین تصادفی میتواند از میانگینگیری، مقاومت مبتنی بر کوانتیل، یا احتمال غلبه بدون تغییر الگوریتم اصلی استفاده کند.
- قابل اعمال بر مدلهای شبیهسازی جعبه سیاه که در آنها اطلاعات گرادیان در دسترس نیست.
- یک جبهه پارتو کامل به جای یک راهحل واحد تولید میکند و به تصمیمگیرندگان انتخابهای مصالحه صریح میدهد.
کاربردها
- طراحی مهندسی مقاوم: بهینهسازی اجزای سازهای یا مکانیکی تحت تلرانسهای تولید و تغییرپذیری بار.
- طراحی شبکه زنجیره تأمین: حداقلسازی هزینه و زمان تحویل زمانی که مقادیر تقاضا و عرضه تصادفی هستند.
- مدلسازی خطمشی زیستمحیطی: یافتن استراتژیهای بهینه پارتو برای کاهش انتشار زمانی که مدلهای تأثیر آبوهوا دارای پارامترهای نامشخص هستند.
- بهینهسازی سبد سهام: متعادل کردن بازده مورد انتظار و ریسک زمانی که بازده داراییها از فرآیندهای تصادفی پیروی میکنند.
- تخصیص منابع مراقبتهای بهداشتی: بهینهسازی هزینه و نتایج بیمار تحت نرخهای ورود بیمار و اثربخشی درمان نامشخص.
- برنامهریزی سیستمهای انرژی: تعیین اندازه تأسیسات انرژی تجدیدپذیر تحت پروفیلهای تولید باد و خورشید تصادفی.
چگونه کار میکند
چگونه کار میکند
مسئله بهینهسازی چندهدفه را با k تابع هدف تصادفی f_1(x,xi), ..., f_k(x,xi) تعریف کنید، که در آن xi پارامترهای تصادفی کشیده شده از یک توزیع شناخته شده یا تخمینی را نشان میدهد. حدود متغیر تصمیم، محدودیتها و تعداد ارزیابیهای تکراری (تکرار) r مورد استفاده برای تخمین مقدار مورد انتظار هر هدف را مشخص کنید.
یک جمعیت N از راهحلهای کاندید را به طور تصادفی در فضای تصمیم امکانپذیر مقداردهی اولیه کنید. برای هر فرد، یک بردار تخمین برازش به طول k اختصاص دهید که با صفر مقداردهی اولیه شده است. شمارنده نسل g = 0 را تنظیم کنید و معیارهای توقف (حداکثر نسل G_max یا تلرانس همگرایی) را تعریف کنید.
برای هر فرد x_i در جمعیت، هر هدف f_j(x_i, xi) را دقیقاً r بار با نمونهبرداری xi از توزیع آن (یا اجرای r تکرار شبیهسازی) ارزیابی کنید. هدف واقعی را به عنوان میانگین نمونه تخمین بزنید: f_j_hat(x_i) = (1/r) * sum_{l=1}^{r} f_j(x_i, xi_l). به طور اختیاری خطاهای استاندارد را برای اطلاعرسانی استراتژیهای نمونهبرداری تطبیقی محاسبه کنید.
مرتبسازی سریع غیرمغلوب را بر روی بردارهای هدف تخمینی اعمال کنید. راهحل x_a راهحل x_b را غالب میکند اگر f_j_hat(x_a) <= f_j_hat(x_b) برای همه j و به طور اکید کمتر برای حداقل یک j. هر راهحل را به یک رتبه جبهه پارتو F_1, F_2, ... اختصاص دهید که در آن F_1 شامل راهحلهایی است که توسط هیچ راهحل دیگری مغلوب نشدهاند.
والدین را با استفاده از انتخاب تورنمنت دوتایی بر اساس رتبه پارتو و فاصله ازدحام (برای حفظ تنوع) انتخاب کنید. عملگرهای ژنتیکی — تقاطع شبیهسازی شده باینری (SBX) و جهش چندجملهای — را برای تولید جمعیتی از فرزندان Q به اندازه N اعمال کنید. جمعیت والدین و فرزندان (اندازه 2N) را ادغام کنید، اهداف تصادفی را دوباره ارزیابی کنید، دوباره مرتب کنید و N راهحل برتر را بر اساس رتبه و سپس فاصله ازدحام انتخاب کنید.
g را افزایش دهید. اگر g < G_max و جبهه پارتو تثبیت نشده است، از مرحله ارزیابی تصادفی تکرار کنید. در غیر این صورت، جبهه پارتو نهایی F_1 را به عنوان مجموعه راهحلهای مقاوم غیرمغلوب برگردانید. جبهه پارتو تقریبی را در فضای هدف برای انتخاب تصمیمگیرنده گزارش دهید.
دامهای رایج
- استفاده از یک تکرار واحد (r=1) برای هر فرد، نویز را به عنوان سیگنال در نظر میگیرد و منجر به جبهههای پارتوی بسیار ناپایدار در طول اجراها میشود — همیشه از r >= 3 به عنوان حداقل استفاده کنید و همگرایی را تأیید کنید.
- نادیده گرفتن واریانس اهداف تصادفی میتواند راهحلهایی را انتخاب کند که به طور متوسط خوب به نظر میرسند اما در سناریوهای دم عملکرد ضعیفی دارند — هنگام اهمیت یافتن ریسک دم، فرمولبندیهای کوانتیل یا بدترین حالت اهداف را در نظر بگیرید.
- اعمال روش بدون بررسی اینکه آیا نویز ایستا است: اگر خواص نویز با مقادیر متغیر تصمیم تغییر میکند، نمونهبرداری تطبیقی یا مدلهای ناهمگن مورد نیاز است.
- جبهه پارتوی خروجی را به عنوان تصمیم نهایی بدون ارزیابی مقاومت خارج از نمونه در نظر گرفتن — همیشه راهحلهای توصیهشده را با اجرای شبیهسازیهای نگهداشته تأیید کنید.
پرسشهای متداول
چند تکرار r را باید در هر ارزیابی فردی استفاده کنم؟
یک نقطه شروع رایج r = 5–30 است که بسته به ضریب تغییرپذیری هدف متفاوت است. استراتژیهای تطبیقی که تکرارهای بیشتری را به راهحلهای نخبه اختصاص میدهند یا از نمونهبرداری متوالی تا زمانی که معیار اطمینان برآورده شود استفاده میکنند، کارآمدتر هستند. برای شبیهسازیهای گرانقیمت، r = 3–5 با جمعیت بزرگ اغلب مصالحه عملی است.
Stochastic NSGA-II چگونه با NSGA-II استاندارد تفاوت دارد؟
تنها تفاوت ساختاری در ارزیابی هدف است: NSGA-II استاندارد f(x) را یک بار ارزیابی میکند و فرض میکند نتیجه دقیق است، در حالی که Stochastic NSGA-II، f(x, xi) را r بار ارزیابی میکند و از میانگین نمونه (یا آمار مقاومت دیگر) به عنوان هدف مؤثر استفاده میکند. تمام مکانیسمهای مرتبسازی، انتخاب و عملگرهای ژنتیکی یکسان باقی میمانند.
آیا میتوانم از Stochastic NSGA-II به جای اهداف میانگین با احتمال غلبه استفاده کنم؟
بله. رویکردهای احتمال غلبه، مقایسههای غلبه قطعی را با احتمالات غلبه تصادفی جایگزین میکنند که تحت نویز بالا اصولیتر است. این امر به نمونههای بیشتری در هر مقایسه نیاز دارد اما در صورت بزرگ بودن نویز نسبت به تفاوتهای هدف، رتبهبندیهای قابل اطمینانتری تولید میکند.
اگر شبیهسازی من برای تکرارهای متعدد خیلی گران باشد چه؟
رویکردهای مبتنی بر سورگیت (surrogate-assisted) را در نظر بگیرید: یک مدل جایگزین (متامدل) گوسی یا شبکههای عصبی از تابع هدف بسازید، از آن برای تخمین ارزان هر دو میانگین و واریانس استفاده کنید و معیارهای بهبود مورد انتظار یا احتمال بهبود را به جای ارزیابیهای مستقیم مکرر اعمال کنید.
آیا Stochastic NSGA-II تضمین شده است که جبهه پارتو تصادفی واقعی را پیدا کند؟
خیر. مانند همه الگوریتمهای تکاملی، این یک روش اکتشافی است که هیچ تضمین همگرایی در زمان محدود به جبهه واقعی ندارد. راهنمایی عملی: چندین اجرای مستقل را اجرا کنید، جبهههای حاصل را با استفاده از شاخصهای حجم هایپروولوم مقایسه کنید و اندازه جمعیت یا نسلها را در صورت تفاوت قابل توجه جبههها در طول اجراها افزایش دهید.
روشهای مرتبط
منابع
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182–197.
باز کردن مرجع DOIکپی شد.Hughes, E. J. (2001). Evolutionary multi-objective ranking with uncertainty and noise. In Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization (EMO 2001), Lecture Notes in Computer Science, vol. 1993, pp. 329–343. Springer.
باز کردن مرجع DOIکپی شد.