بخشی از مقاله
چکیده
الگوریتمهای ژنتیک فشردهالف - CGAs - به جای کار با جمعیتی از پاسخها، بر روی یک شرح آماری از جمعیت کار میکنند. در نتیجه این الگوریتمها در مراحل اولیه جستجو به دلیل ماهیت تصادفی خود رفتار اکتشافی بالایی دارند. به همین دلیل برای حل مسائل بهینهسازی در ابعاد بالا، به خصوص در مسائل با جبهه متمایل - وجود تراکم متمایل بر روی جبهه پارتو - ، توانایی خوبی در فرار از بهینههای محلی از خود نشان میدهند.
در مقابل عملگرهای تکاملی والد-مرکزب مانند SBX در ابعاد بالا توانایی خوبی در استخراج محیط نزدیک به والدین دارند. در این مقاله، با ترکیب این دو روش تعادل خوبی بین رفتار اکتشافی و استخراجی الگوریتم بهینهسازی ایجاد شده است. همچنین، راهکارهایی برای افزایش فشار انتخاب و حفظ تنوع جمعیت پیشنهاد شدهاند. الگوریتم پیشنهادی با شش تا از جدیدترین الگوریتمهای حل مسائل بهینهسازی چندین هدفه بر روی مسئله چندین هدفه DTLZ4 با جبهه متمایل با تعداد اهداف تا پانزده هدف مقایسه شده است. نتایج نشان دهنده برتری روش پیشنهادی در پیدا کردن یک توزیع خوب از پاسخ ها بر روی جبهه پارتو در تابع تست انتخاب شده میباشد.
.1 مقدمه
بسیاری مسائل دنیای واقعی در ذات خود چندین هدفه هستند که در اکثر مواقع این اهداف با هم در تناقض هستند. همچنین، هیچ پاسخی در فضای جستجو وجود ندارد که همه اهداف را با هم به طور همزمان بهینه کند. بنابراین، پاسخهای این گونه مسائل در واقع بهترین مبادله ممکن بین این اهداف هستند. با این که الگوریتمهای بهینه سازی چند هدفه میتوانند در شرایط ملایم یک مجموعه جواب به خوبی همگرا شده و به خوبی توزیع شده را ایجاد کنند مشکلاتی در طراحی الگوریتم های بهینه سازی چندین هدفه وجود دارند [1]، :[2] - الف - برای مسائل با بیش از 15هدف تقریباً تمام جمعیت مغلوب نشده می شوند.
- ب - عملگر تکاملی بازترکیب کارایی خود را به دلیل دوری والدین از هم از دست میدهند. - ج - تعداد پاسخهای مورد نیاز برای تخمین کل جبهه پارتو با افزایش تعداد اهداف به صورت نمایی افزایش مییابد. - د - محاسبه تنوع جمعیت از لحاظ محاسباتی پرهزینه میشود. به مشکل کاهش توانایی جستجو با افزایش تعداد اهداف، در تعدادی از مقالات اشاره شده است [3]، [4]، .[2] یک روش برای بهبود الگوریتمهای بهینهسازی برای مسائل چندین هدفه افزایش فشار انتخاب به سمت جبهه پارتو است [5] که با استفاده از روابط غلبه جایگزین و یا نرم شده انجام میشود، که توانایی مرتب سازی الگوریتمها را بهبود می دهد.
همچنین، از معیارهای افزایش تنوع مانند فاصله جمعیت3 - CD - در [6] NSGA-II و ساختار نقاط مرجع در NSGA-[1] III برای انتخاب پاسخها از یک سطح پارتو استفاده شده است. بعلاوه، از الگوریتمهای مبتنی بر رتبه بندی مانند رابطه برتری [7]، بهینگیkB در [8] و امتیاز برنده [9] نیز برای رتبه بندی پاسخ های یک سطح پارتو استفاده میکنند . همچنین، از مفهوم منطق فازی [10] برای تعریف رابطه غلبه پارتو فازی در مسائل بهینهسازی چندین هدفه [11] استفاده شده است.
الگوریتمهای مبتنی بر تجزیه نوع دیگر الگوریتم ها هستند که توسط توابع اسکالر کننده یک مسئله چند هدفه را به یک مجموعه از مسائل تک هدفه تبدیل می کنند. الگوریتم [12] MOEA/D از معروف ترین الگوریتمهای این دسته است. در [13] یک نسخه از MOEA/D پیشنهاد شده که برای حذف پاسخها در روش وضعیت ثابت از توابع اسکالر کننده استفاده میکند. در [14] از غلبه- برای افزایش فشار انتخاب استفاده شده است.
در سالهای اخیر توجه به توسعه الگوریتم های تخمین توزیع - EDA - 4 برای حل مسائل بهینه سازی چندین هدفه بیشتر شده است. در [17] از یک شبکه بیزین چند بعدی به عنوان مدل احتمالاتی استفاده میکند. مقایسههایی دربرخی مقالات [15]، [16] بین روشهای موجود انجام دادهاند و به این نتیجه رسیدهاند که هیچ فاصله مشخصی بین الگوریتمهای موجود وجود ندارد و هر یک بسته به خصوصیات مسئله نقاط ضعف و قوت خود را دارند.
در الگوریتم پیشنهادی از خاصیت تصادفی بودن الگوریتمهای فشرده برای اکتشاف بهتر محیط در مسائل با تراکم متمایل بر روی جبهه پارتو استفاده شده است. مفهوم همسایگی برای انتخاب والدین به منظور بهبود عملکرد عملگرهای تکاملی به کار رفته است. همچنین، اولویتدهی بر اساس کوچکترین مجموع مقادیر PBI پاسخهای پتانسیل نقاط مرجع جهت تقویت همگرایی جمعیت در عمل انتخاب محیط انجام میگیرد. ادامه این مقاله به شرح زیر سازماندهی شده است. بخش 2 آشنایی با مفاهیم پایه و الگوریتمهای - CDE - ، NSGA-III و MOEA/D است. در بخش 3 توضیح کامل الگوریتم پیشنهادی بیان شده است. در بخش 4 نتایج حاصل از الگوریتمهای ارائه شده تحت شرایط مساوی مورد بررسی قرار گرفتهاند. در نهایت، در بخش 5 نتیجهگیری پایانی و کارهای آینده بیان شدهاند.
.2 کارهای مرتبط
- x - هدف iامی است که باید به حداقل برسد، و Ω ناحیه ممکن است. برای دو بردار x1, x 2 ∈ Ω، میگوییم x1 بر x2 غلبه میکند، اگر و تنها اگر، x1 در هیچ یک از M هدف خود بدتر از x2 نباشد و حداقل در یک هدف از x2اکیداً بهتر باشد. یک نقطه x1 ∈ Ω بهینه پارتو جهانی است اگر هیچ x ∈ Ω وجود نداشته باشد به نحوی که بر x1 غلبه کند. به مجموعه همه این نقاط بهینه پارتو مجموعه پارتو - PS - 5 گفته میشود و به مجموعه بردارهای هدف مربوط به آنها جبهه پارتو - PF - 6 گفته میشود.
.1-2 الگوریتم تکامل دیفرانسیل فشرده CDE
الگوریتم تکامل فشرده [18] از ساختار تکاملی [ 19] RCGA و منطق جستجوی DE استفاده میکند. به جای کار با جمعیت تنها بروی شرح آماری از جمعیت کار میکند. به این صورت که از یک بردار احتمال برای نمونه برداری پاسخهای جدید استفاده میشود.
.2-2 الگوریتم NSGA-III
قالب کلی الگوریتم [1] NSGA -III مشابه الگوریتم NSGA-[6] II است با این تفاوت که در انتخاب محیط، به جای CD از ایدهای مشابه ایده وزنها در الگوریتم MOEA/D استفاده میکند. هر پاسخ با یک نقطه مرجع مرتبط میشود. سپس، جمعیت به ترتیب بر اساس سطوح مغلوب نشده و بعد از آن کوتاهترین فاصله عمود تا نقاط مرجع برای نسل بعد انتخاب میشوند. همچنین، از شمارش موقعیت برای حفظ تنوع استفاده شده است.
.3-2 الگوریتم MOEA/D
این الگوریتم از روشهای تجزیه در قالب تکاملی استفاده میکند. جعیت در MOEA/D شامل زیر مسائلی است که به صورت موازی حل میشوند و در آخر جواب هر زیر مسئله یک پاسخ بهینه پارتو برای مسئله چند هدفه داده شده میباشد. در [12] از سه تابع اسکالر کننده مجموع وزنها، چبیشف، و تقاطع مرزی مبتنی بر خطا - PBI - 7 استفاده شدهاند. در روش PBI مسئله بهینهسازی به صورت زیر است.
.3 الگوریتم پیشنهادی
چهارچوب اصلی الگوریتم پیشنهادی مطابق الگوریتم [1] NSGA -III است با تغییراتی در ساختار پاسخهای جمعیت، روند ایجاد پاسخهای فرزندان و نحوه انتخاب پاسخها برای نسل بعد. الگوریتم پیشنهادی در مرحله اول از زیرگروههای فشرده برای اکتشاف بیشتر محیط استفاده میکند.
