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

NSGA-II مقاوم — بهینه‌سازی چندهدفه تحت عدم قطعیت

معرفی‌شده توسط
Kalyanmoy Deb and Himanshu Gupta
سال
2006
نوع
Robust evolutionary multi-objective optimization algorithm
خانواده
Simulation / optimization

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

اندازه قلم

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

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

شهود پشت روش

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

تاریخ

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

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

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

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

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

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

نقاط قوت

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

کاربردها

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

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

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

1

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

2

برای هر راه‌حل کاندید x در جمعیت، M تحقق عدم قطعیت را از توزیع‌های پارامتر مشخص شده (یا یک همسایگی ساختاریافته را شمارش کنید) استخراج کنید. همه توابع هدف را تحت هر تحقق ارزیابی کنید و نتایج را در تخمین‌های هدف مقاوم جمع‌آوری کنید. تجمیع رایج: از میانگین به عنوان تخمین مقاومت برای عملکرد مورد انتظار استفاده کنید و یک جریمه متناسب با انحراف معیار برای در نظر گرفتن واریانس اضافه کنید، بنابراین یک هدف مقاوم به صورت f_robust(x) = mean[f(x, xi)] + lambda * std[f(x, xi)] می‌شود.

3

مرتب‌سازی سریع غیرمسلط را با استفاده از تخمین‌های هدف مقاوم به جای مقادیر اسمی، بر روی جمعیت اعمال کنید. هر راه‌حل را بر اساس تسلط پارتو اهداف مقاوم، به یک جبهه غیرمسلط F1، F2 و غیره اختصاص دهید. راه‌حل‌های موجود در F1 به طور مقاوم غیرمسلط هستند: هیچ راه‌حل دیگری به طور همزمان در همه اهداف مقاوم بهتر نیست.

4

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

5

انتخاب تورنمنت دودویی را با استفاده از عملگر مقایسه-ازدحام بر روی جبهه‌های مقاوم و فواصل ازدحام اعمال کنید. یک جمعیت فرزند Q به اندازه N از طریق عملگرهای تقاطع (تقاطع دودویی شبیه‌سازی شده) و جهش (جهش چندجمله‌ای) تولید کنید. راه‌حل‌های فرزند را با استفاده از ارزیابی مقاومت با M نمونه عدم قطعیت برای هر فرد مجدداً ارزیابی کنید. این مرحله زمانی که M بزرگ است، زمان اجرا را تحت تأثیر قرار می‌دهد.

6

جمعیت والد P و فرزند Q را در یک مجموعه ترکیبی از 2N راه‌حل ادغام کنید. مجدداً بر اساس غیرتسلط مقاوم و فاصله ازدحام مرتب‌سازی کنید. N فرد برتر را برای تشکیل نسل بعدی انتخاب کنید و نخبه‌گرایی را حفظ کنید. زمانی که حداکثر حد نسل فرا رسید، ابرحجم راکد شد، یا بودجه محاسباتی به اتمام رسید، خاتمه دهید. جبهه پارتو مقاوم نهایی F1 را بازگردانید.

دام‌های رایج

  • استفاده از تعداد بسیار کمی از نمونه‌های عدم قطعیت در هر ارزیابی (M کمتر از 20-30) نویز ارزیابی را ایجاد می‌کند که رتبه‌بندی غیرتسلط را مخدوش کرده و یک جبهه پارتو مقاوم غیرقابل اعتماد را به دست می‌دهد.
  • خلط مقاومت مقادیر هدف با مقاومت راه‌حل‌های بهینه: یک راه‌حل مقاوم در فضای هدف ممکن است همچنان به مقادیر متغیر تصمیم دقیق نیاز داشته باشد که پیاده‌سازی آنها دشوار است.
  • اعمال فاصله ازدحام پیش‌فرض NSGA-II در فضای هدف مقاوم بدون بررسی اینکه آیا اهداف مقاوم در مقیاس‌های متناسب هستند یا خیر؛ اهداف را قبل از محاسبه فواصل نرمال‌سازی کنید.
  • اجرای یک تکرار واحد و در نظر گرفتن نتیجه به عنوان قطعی؛ همیشه چندین تکرار مستقل را اجرا کنید و آمار ابرحجم را برای در نظر گرفتن تغییرات تصادفی گزارش دهید.
  • انتخاب یک lambda (وزن جریمه واریانس) به صورت دلبخواهی بدون تحلیل حساسیت؛ lambda انتخاب شده به طور ضمنی یک نگرش ریسک را کدگذاری می‌کند که باید صریح و توجیه شده باشد.

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

NSGA-II مقاوم چه تفاوتی با NSGA-II استاندارد دارد؟

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

چند نمونه عدم قطعیت M باید برای هر فرد استفاده کنم؟

هیچ قانون جهانی وجود ندارد. یک نقطه شروع رایج M = 30 تا 50 نمونه مونت کارلو است اگر ارزیابی‌های هدف ارزان باشند. برای ارزیابی‌های گران‌قیمت، M = 5 تا 10 ممکن است ضروری باشد. یک مطالعه حساسیت انجام دهید: M را افزایش دهید تا زمانی که تخمین‌های هدف مقاوم تثبیت شوند. نمونه‌برداری شبه‌تصادفی (لاتین هایپرمکعب یا سوبول) پوشش بهتری نسبت به نمونه‌برداری کاملاً تصادفی برای همان M به دست می‌دهد.

آیا می‌توانم از NSGA-II مقاوم با بیش از سه هدف استفاده کنم؟

این الگوریتم قابل استفاده است، اما عملکرد به همان دلیلی که NSGA-II استاندارد دارد، کاهش می‌یابد: فاصله ازدحام قدرت تمایز خود را در فضای هدف با ابعاد بالا از دست می‌دهد و بیشتر راه‌حل‌ها در جبهه غیرمسلط اول قرار می‌گیرند. برای چهار یا بیشتر هدف، یک نوع مقاوم از NSGA-III را در نظر بگیرید که به جای فاصله ازدحام از انتخاب مبتنی بر نقطه مرجع استفاده می‌کند.

چه معیار مقاومتی را باید انتخاب کنم؟

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

چگونه می‌توانم اعتبار راه‌حل‌های بازگردانده شده را به عنوان واقعاً مقاوم تأیید کنم؟

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

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

منابع

  1. 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
    کپی شد.
  2. Deb, K., & Gupta, H. (2006). Introducing robustness in multi-objective optimization. Evolutionary Computation, 14(4), 463-494.

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