پیشینه الگوریتم ژنتیک چند هدفه (NSGA)
الگوریتمهای تکاملی متعددی برای یافتن پاسخهای نامغلوب مسائل چندهدفه توسعه داده شده اند، که از جمله آنها میتوان به الگوریتم ژنتیک با مرتبسازی نامغلوب اشاره کرد. در بهینهیابی چندهدفه، چند تابع هدف مختلف وجود دارند که تمایل به یافتن کمینه یا بیشینهی آنها به طور همزمان وجود دارد. اغلب این توابع هدف در نقطهی مقابل یکدیگر قرار دارند، به طوری که بهبود یکی از آنها، با بدتر شدن دیگری مواجه می شود. بنابراین در اینگونه مسائل برخلاف مسائل تکهدفی که تنها یک نقطهی اکسترمم برای مسئله وجود دارد، مجموعه ای از پاسخهای بهینه به عنوان جواب بهدست میآیند که به اصطلاح نقاط بهینه پارتو یا منحنی پارتو خوانده میشوند.
روشهای بهینهیابی چندهدفهی مبتنی بر پارتو، در مقایسه با روشهای بهینهیابی تکهدفه، دارای مزایایی میباشند. اول اینکه، پاسخ بهینه پارتو دربردارندهی مجموعه ای از پاسخها میباشد که می تواند شامل پاسخهایی که دارای نقض قید میباشند نیز باشد، بنابراین یک پاسخ با نقض قید مجاز اگر ارزش تابع هدف بالایی داشته باشند، نیز می تواند در نظر گرفته شود. دوم اینکه، با تجزیهی مسئله اصلی به چندین مسئله، اهداف مختلف انعطاف پذیری بیشتری در جستوجوی فضای پاسخ خواهند داشت.
الگوریتم ژنتیک با مرتب سازی نامغلوب، یکی از مطرح ترین و پرکاربردترین الگوریتم های بهینه سازی در زمینه ی بهینه سازی چندهدفه می باشد. اسرینیباس و دِب در سال ۱۹۹۵ روش بهینه سازی (NSGA) را برای حل مسائل بهینه سازی چند هدفه معرفی نمودند. نکات برجسته ای که در مورد این روش بهینه سازی وجود دارند، عبارتند از:
- جوابی که هیچ جواب دیگری، به طور قطع بهتر از آن نباشد، دارای امتیاز بیشتری است. جواب ها بر اساس این که چند جواب بهتر از آن ها وجود داشته باشند، رتبه بندی و مرتب می شوند.
- شایستگی (برازندگی) برای جواب ها بر حسب رتبه آن ها و عدم غلبه سایر جواب ها، اختصاص می یابد.
- از شیوه اشتراک برازندگی (Fitness Sharing) برای جواب های نزدیک استفاده می شود تا به این ترتیب پراکندگی جواب ها به نحو مطلوبی تنظیم شود و جواب های به طور یکنواخت در فضای جستجو پخش شوند.
با توجه به حساسیت نسبتا زیادی که نحوه عملکرد و کیفیت جواب های الگوریتم (NSGA) به پارامترهای اشتراک برازندگی و سایر پارامترها دارند، نسخه دوم این الگوریتم با نام (NSGA-II)
توسط دِب و همکارانش در سال ۲۰۰۰ معرفی گردید [54]. ویژگی های عمده این الگوریتم عبارتند از:
- تعریف فاصله تراکمی (Crowding Distance) به عنوان ویژگی جایگزین برای شیوه هایی مانند اشتراک برازندگی
- استفاده از عملگر انتخاب تورنومنت دو-دویی
- ذخیره و آرشیو کردن جواب های نامغلوب که در مراحل قبلی الگوریتم به دست آمده اند (نخبه گرایی)
در فصل بعد پس از ارائه مدل ریاضی مورد نظر، به طور کامل در مورد این الگوریتم و ویژگی های آن بحث خواهیم کرد.
[پنجشنبه 1400-03-06] [ 08:47:00 ب.ظ ]
|