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

الگوریتم ژنتیک مقاوم — بهینه‌سازی تکاملی تحت عدم قطعیت

معرفی‌شده توسط
Jin, Y. and Branke, J. (systematic formalization); roots in Holland (1975)
سال
2005 (systematic survey); earlier applications from late 1990s
نوع
Metaheuristic evolutionary optimizer with robustness mechanism
خانواده
Simulation / optimization

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

اندازه قلم

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

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

شهود پشت روش

یک الگوریتم ژنتیک کلاسیک به دنبال بهترین راه‌حل می‌گردد، اما «بهترین» تحت شرایط ایده‌آل ممکن است در عمل شکننده باشد — تغییرات کوچک در ورودی‌ها می‌تواند عملکرد را مختل کند. یک GA مقاوم سوال متفاوتی می‌پرسد: کدام راه‌حل‌ها در تمام دامنه اغتشاشات مورد انتظار به طور قابل قبولی خوب باقی می‌مانند؟ این کار را با نمونه‌برداری از همسایگی هر کاندید در طول ارزیابی برازندگی و پاداش دادن به کاندیداهایی انجام می‌دهد که عملکردشان به جای فاجعه‌بار، به آرامی کاهش می‌یابد. نتیجه، جمعیتی تکامل‌یافته است که نه تنها بهینه، بلکه تحت شرایط عملیاتی واقع‌بینانه به طور قابل اعتمادی نزدیک به بهینه است.

تاریخ

بهینه‌سازی مقاوم در محاسبات تکاملی در اواخر دهه ۱۹۹۰ پدیدار شد، که توسط مسائل طراحی مهندسی که در آنها تلرانس‌های تولیدی، طرح‌های اسمی بهینه را غیرقابل اعتماد می‌کردند، هدایت شد. بررسی IEEE جین و برانکه در سال ۲۰۰۵ این حوزه را نظام‌مند کرد و انواع عدم قطعیت و معیارهای مقاومت را متمایز ساخت. بررسی جامع بایر و سندهاف در سال ۲۰۰۷ مبانی نظری مرتبط کننده EA مقاوم با بهینه‌سازی مقاوم کلاسیک را بنا نهاد و الگوریتم ژنتیک مقاوم را به عنوان یک زیرشاخه شناخته شده از محاسبات تکاملی تثبیت کرد.

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

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

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

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

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

نقاط قوت

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

کاربردها

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

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

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

1

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

2

یک معیار مقاومت برای هر راه‌حل کاندید x انتخاب و فرموله کنید. انتخاب‌های رایج عبارتند از: (۱) برازندگی مورد انتظار بر روی توزیع اغتشاش E[f(x+δ)]؛ (۲) ترکیب وزنی میانگین و واریانس E[f] + λ·Var[f]؛ یا (۳) بدترین برازندگی min بر روی یک مجموعه عدم قطعیت محدود. این معیار جایگزین یا تکمیل‌کننده تابع برازندگی اسمی می‌شود.

3

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

4

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

5

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

6

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

دام‌های رایج

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

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

الگوریتم ژنتیک مقاوم چه تفاوتی با یک الگوریتم ژنتیک استاندارد دارد؟

یک GA استاندارد برازندگی هر کاندید را در نقطه طراحی اسمی آن ارزیابی می‌کند. یک GA مقاوم برازندگی را با نمونه‌برداری در یک همسایگی از اغتشاشات اطراف هر کاندید ارزیابی می‌کند، بنابراین فشار انتخاب به راه‌حل‌هایی پاداش می‌دهد که به طور متوسط (یا در بدترین حالت) عملکرد خوبی دارند نه فقط در یک نقطه. این امر معنای «بهتر» را در طول تکامل تغییر می‌دهد.

معمولاً چند نمونه اغتشاش به ازای هر فرد مورد نیاز است؟

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

آیا می‌توان الگوریتم ژنتیک مقاوم را با بهینه‌سازی چندهدفه ترکیب کرد؟

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

چه چیزی مقاومت مبتنی بر انتظار را از مقاومت بدترین حالت در RGA متمایز می‌کند؟

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

آیا الگوریتم ژنتیک مقاوم زمانی که توزیع عدم قطعیت ناشناخته است، مناسب است؟

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

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

منابع

  1. Jin, Y., Branke, J. (2005). Evolutionary optimization in uncertain environments — a survey. IEEE Transactions on Evolutionary Computation, 9(3), 303–317.

    باز کردن مرجع DOI
    کپی شد.
  2. Beyer, H.-G., Sendhoff, B. (2007). Robust optimization — A comprehensive survey. Computer Methods in Applied Mechanics and Engineering, 196(33–34), 3190–3218.

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