تجزیه الگوریتمهای تکاملی برای بهینهسازی چندهدفه نویزی
چکیده:
مسائل چند هدفه یک دسته از مسائل بهینهسازی هستند، که شامل بیش از یک تابع هدف هستند و این توابع هدف باید به طور همزمان بهینهسازی شوند. توابع هدف باید متضاد باشند، پس مجموعهای از راهحلها بهجای یک راهحل نیاز است. این مجموعه به عنوان بهینگی پارتو شناخته شده است.
مشکلات بهینهسازی چند هدفه در بسیاری از برنامههای کاربردی دنیای واقعی به وجود میآید، جایی که چند هدف رقابتی با وجود تعادل میان اهداف متضاد، باید مورد ارزیابی قرار گیرد و راهحلهای بهینه را برای آنها پیدا کرد. بیشترین بازده همراه با کمترین ریسک سرمایهگذاری در بازار سهام، یا بیشترین عملکرد همراه با کمترین میزان مصرف سوخت و انتشار گاز خطرناک در هنگام خرید یک ماشین، نمونههای معمولی از دنیای واقعی چند هدفه مسائل بهینهسازی می باشد. در این مورد تعدادی از راه حل های بهینه را می توان یافت، که به عنوان راه حل های غیر قابل چیرگی و یا بهینگی پارتو شناخته میشوند. راهحلهای بهینگی پارتو برای بهبود یک هدف بدون بدتر شدن دیگران غیرممکن است.
راهحلهای کلاسیک برای رسیدگی به این مشکل از روش مستقیم یا روش های مبتنی بر گرادیانت استفاده می کند که ارائه دادن آنها برای مقیاس بزرگ یا مسائل ترکیبی ناکافی یا محاسباتی گران خواهد داشت. مشکلات دیگر روش های کلاسیک، مانند مسئله دانش، که امکان دارد در دسترس نباشد، یا حساسیت به برخی از ویژگی های مسئله هستند. به عنوان مثال، پیدا کردن راه حل در کل مجموعه بهینگی پارتو میتواند تنها برای مسائل برجسته تضمین شده باشد. روشهای کلاسیک برای تولید مجموعه جلو پارتو، اهداف را در توابع تکی یا پارامتری قبل از جستجو جمع میکنند. بنابراین، چند اجرا و تنظیم پارامتر برای رسیدن به یک مجموعه از راهحلهایی که تقریب بهینگی پارتو هستند انجام شده است.
در نتیجه روشهای جدیدی مبتنی بر کامپیوتر با الگوریتمهای فرا ابتکاری بسط داده شدهاند. بیشتر این الگوریتمهای فرا ابتکاری پیادهسازی نوعی از روش جستجوی تصادفی هستند، از جمله «الگوریتم تکاملی» که دقت زیادی طلب میکند. این روش دارای چند ویژگی است که یک روش مطلوب برای مقابله با مسائل چند هدفه است. در نتیجه، تعدادی از مطالعات در دهههای اخیر «الگوریتم تکاملی بهینهسازی چند هدفه (MOEA)» را به منظورهای مختلف توسعه دادند یا اصلاح کردند. این الگوریتم با یک گروه از راهحل کار میکند که قادر به جستجو برای چند راهحل بهینگی پارتو در یک اجرای واحد میباشد. ضمنا، تنها افراد مناسب در هر نسل برای تولید مثل و نمایندگی در نسل بعدی شانس دارند. تابع اختصاص سازگاری(The fitness assignment function) سیستم پرچمدار MOEA میباشد. ارزش سازگاری نشان دهنده قدرت یک فرد است.
متاسفانه، بسیاری از برنامه های کاربردی دنیای واقعی موجب رسیدن به درجه خاصی از نویز ناشی از اتفاقات طبیعی، مدل های ناکارآمد، تحریف سیگنال یا اطلاعات نامشخص میشوند. این نویز بر کارایی الگوریتمهای تابع سازگاری تاثیر گذار است و باعث ایجاد اختلال در روند بهینه سازی میشود. این پایاننامه به بررسی و هدف اثر این نویز مخرب بر عملکرد MOEA میپردازد.
ما نویز «مسئله چند هدفه بهینهسازی (MOP)» را مطالعه میکنیم و «الگوریتم تکاملی بهینه سازی چند هدفه مبتنی بر تجزیه (MOEA/D)» را برای بهتر کردن کارایی آن در محیط دارای نویز، تغییر میدهیم. برای رسیدن به این هدف، ما میخواهیم MOEA/D اصلی را با تکنیک «بهینه سازی ترتیبی» برای رسیدگی به ابهامات ترکیب کنیم. بخشهای مهمی از این پایان نامه به شرح زیر است.
- نخست، MOEA/D در یک محیط نویزی با سطوح مختلفی از نویز برای دادن درکی عمیق تر به ما که از کجا الگوریتم اصلی شکست میخورد، تست شده است.
- سپس، ما MOEA/D اصلی را برای بهبود هندل کردن نویز آن با استفاده از روش بهینه سازی ترتیبی گسترش میدهیم. این کار MOEA/D+OO را ایجاد میکند که MOEA/D در شرایط متنوع و همگرایی در محیط نویزی بهتر خواهد شد. این در برابر «مشکلات معیار» از سطوح مختلف مشکل تست شده است.
- در نهایت، برای تست برنامه کاربردی دنیای واقعی MOEA/D+OO، ما یک بهینه سازی سبد سهام نویزی را با استفاده از الگوریتم ارائه شده حل کردیم. مسئله بهینه سازی سبد سهام یک مورد کلاسیک در امور مالی است که چهره سرمایهگذار مایل به حداکثر کردن بازده سبد سهام است در حالی که کمترین ریسک را در سرمایه گذاری داشته باشد. بعد توسط انحراف معیار نرخ سبد سهام از نرخ بازگشت اندازه گیری شد. این دو هدف به وضوح یک مشکل چند هدفه را می سازد.