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

الگوریتم مرتب‌سازی غیرمغلوب ژنتیکی II (NSGA-II)

سال
2002
نوع
Evolutionary multi-objective optimisation algorithm

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

اندازه قلم

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

NSGA-II (الگوریتم مرتب‌سازی غیرمغلوب ژنتیکی II) الگوریتم مرجع استاندارد برای بهینه‌سازی تکاملی چندهدفه است که در سال 2002 توسط Deb، Pratap، Agarwal و Meyarivan معرفی شد. این الگوریتم به جای ادغام چندین هدف متعارض در یک امتیاز واحد، جمعیتی از راه‌حل‌های کاندید را در طول نسل‌ها تکامل می‌دهد و مجموعه‌ای از راه‌حل‌های مصالحه پارتو-بهینه — جبهه پارتو — را با استفاده از مرتب‌سازی سریع غیرمغلوب و معیار فاصله ازدحام برای حفظ تنوع بازمی‌گرداند.

شهود پشت روش

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

تاریخ

NSGA-II توسط Kalyanmoy Deb و همکارانش در موسسه فناوری هند کانپور در سال 2002 به عنوان جانشین اصلاح شده و به طور قابل توجهی بهبود یافته NSGA اصلی (Srinivas & Deb, 1994) منتشر شد. نوآوری‌های کلیدی شامل رویه مرتب‌سازی سریع غیرمغلوب با پیچیدگی O(MN²)، یک اپراتور صریح فاصله ازدحام برای حفظ تنوع راه‌حل بدون پارامتر اشتراک‌گذاری، و یک مکانیزم انتخاب نخبه‌گرا بود. مقاله سال 2002 در IEEE Transactions on Evolutionary Computation به یکی از پر استنادترین آثار در محاسبات تکاملی تبدیل شد و NSGA-II را به عنوان معیار واقعی برای الگوریتم‌های تکاملی چندهدفه تثبیت کرد. نسخه‌های بعدی — NSGA-III (2014) و موارد دیگر — این چارچوب را به مسائل چندهدفه گسترش می‌دهند.

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

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

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

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

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

نقاط قوت

  • مجموعه‌ای متنوع از راه‌حل‌های مصالحه پارتو-بهینه را در یک اجرا تولید می‌کند و نیاز به تکرار بهینه‌سازی با وزن‌های مختلف را از بین می‌برد.
  • مرتب‌سازی سریع غیرمغلوب با زمان O(MN²) اجرا می‌شود (M هدف، N اندازه جمعیت)، که آن را برای اندازه‌های مسئله متوسط قابل مدیریت می‌کند.
  • انتخاب نخبه‌گرا تضمین می‌کند که راه‌حل‌های خوب یافت شده در اوایل هرگز دور ریخته نمی‌شوند.
  • برای متغیرهای تصمیم پیوسته، دودویی و دسته‌ای بدون فرض توزیعی قابل اجرا است.
  • به طور گسترده در حوزه‌های مهندسی، تحقیق در عملیات و علوم محاسباتی اعتبارسنجی شده است.

کاربردها

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

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

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

1

جمعیتی از راه‌حل‌های کاندید با نمونه‌برداری تصادفی (یا هدفمند) از متغیرهای تصمیم در محدوده‌هایشان ایجاد می‌شود. اندازه جمعیت به اندازه‌ای بزرگ تنظیم می‌شود که از ابتدا تنوع را در فضای هدف تضمین کند.

2

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

3

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

4

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

5

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

6

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

دام‌های رایج

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

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

NSGA-II به چند نسل نیاز دارد؟

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

جبهه پارتو چیست؟

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

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

بله، اما فاصله ازدحام — مکانیزم تنوع — با افزایش تعداد اهداف فراتر از سه یا چهار (رژیم 'چندهدفه') کمتر مؤثر می‌شود. برای مسائل با پنج هدف یا بیشتر، معمولاً NSGA-III یا الگوریتم‌های مبتنی بر تجزیه مانند MOEA/D ترجیح داده می‌شوند.

آیا NSGA-II قطعی است؟

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

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

منابع

  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. Zitzler, E., Deb, K. & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173-195.

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