Document Type : Research Article
Authors
1 Dept. of Electrical and Computer Engineering, Urmia University of Technology, Urmia, Iran
2 Dept. of Electrical and Computer Engineering, K.N. Toosi University of Technology, Tehran, Iran
3 Engineering Department, Iranian Research Institute for Electrical Engineering, ACECR, Tehran, Iran
Abstract
Keywords
[*]بیشتر مسائل بهینه‌سازی که بشر در دنیای واقعی با آنها سرو کار دارد، بیش از یک هدف را دربرمی‌گیرند؛ به طوری که پاسخ بهینه مسأله هنگامی حاصل می‌گردد که کلیه اهداف به مرز خاصی از بهینگی رسیده باشند. این گونه مسائل را مسائل بهینه‌سازی چندهدفه [1]می‌نامیم. اهداف مطرح در مسائل بهینه‌سازی چند هدفه ممکن است با هم در تضاد باشند، از این رو، با مجموعه‌ای از پاسخ‌های بهینه مواجه خواهیم بود. از آنجا که روش‌های کلاسیک در هر مرحله از اجرای الگوریتم تنها یک پاسخ را می‌توانند بیابند، نمی‌توانند برای یافتن مجموعه‌ای از پاسخ‌های بهینه مناسب باشند. امروزه الگوریتم‌های تکاملی ابزار مناسبی برای حل مسائل بهینه‌سازی چندهدفه در نظر گرفته می‌شوند[1]. برای مثال، استفاده از الگوریتم ژنتیک برای حل مسائل چندهدفه[2]، مرتب‌سازی غیرمغلوب الگوریتم ژنتیک (NSGA)[3] ، الگوریتم ژنتیک مبتنی بر نیچینگ (NPGA) [4] و VEGA[5]. در این نوع الگوریتم‌ها مکانیزم انتخاب بر اساس رتبه‌بندی پرتو بوده است. پس از آن الگوریتم‌های تکاملی دیگری ارائه شدند که از استراتژی نخبه‌گرایی استفاده می‌کردند، همانند نسخه بهبود یافتهNSGA (NSGAII) [6] ، SPEA [7] و نسخه بهبود یافته الگوریتم فوق (SPEA2)[8]. در تمام الگوریتم‌های مطرح شده برای ارزیابی جمعیت از عملگر جفت‌گیری و عملگر جهش الگوریتم ژنتیک استفاده شده است. علاوه بر این، الگوریتم‌های تکاملی ترکیبی نیز ارائه شده‌اند، همانند الگوریتم چندهدفه بر اساس اجتماع ذرات (MOPSO)[9]، کلونی مورچه‌ها (MOACO)[10] و غیره.
یکی از الگوریتم‌های تکاملی که در سال 2008 توسط شخصی به نام دن سیمون ارائه گردیدBBO[2] می‌باشد[11]. از این الگوریتم برای بهینه‌سازی تک‌هدفه بسیاری از توابع معیار[14-12] و حل بسیاری از مسائل بهینه‌سازی جهان واقعی استفاده شده است، همانند مسأله انتخاب سنسور برای تخمین کارایی موتور هواپیما [11] و دسته‌بندی تصاویر ماهواره‌ای [15]. از این الگوریتم برای حل مسائل بهینه‌سازی چندهدفه نیز استفاده شده‌است. در [16] از ویژگی خوشه‌بندی جزایر استفاده شده و جزایر را داخل شبه‌جزایری در نظر گرفته است. الگوریتم مطرح شده فوق از مرتب‌سازی غیرمغلوب و فاصله جمعیتی برای همگرایی و تنوع در جامعه استفاده کرده و در نهایت نتایج الگویتم فوق با دو الگوریتم مطرح در زمینه بهینه‌سازی چندهدفه (NSGAII,AMGA) بر پایه سه معیار ارزیابی مقایسه شده است و نتایج حاصل حاکی از همگرایی بهتر و تنوع بیشتر این الگوریتم نسبت به دو الگوریتم دیگر است. الگوریتم پیشنهادی از ایده شبه جزایره الگوریتم فوق الهام گرفته و با اعمال عملگر مهاجرت ترکیبی بر روی این شبه‌جزایر سعی در بهبود راه‌حل های یافت شده در طی نسل‌های متمادی داشته است.در[17] کار دیگری در زمینه بهینه‌سازی چند هدفه با الگوریتم BBO انجام گرفته است، که از الگوریتم BBO برای بهینه‌سازی چندهدفه سیستم‌های پیچیده استفاده شده است. در[18] کاربرد دیگری از BBO در حل مسایل بهینه‌سازی چندهدفه بیان شده است.در [19] نسخه چندهدفه الگوریتمBBO با الگوریتم شکار-شکارچی[3] معرفی و نتایج چشمگیری حاصل شده است .
در این مقاله با در نظر گرفتن مجموعه‌ای از جزایر به عنوان یک شبه جزیره و تولید شبه‌جزایری به تعداد توابع مساله چندهدفه و اعمال عملگر مهاجرت ترکیبی، شکل (1) الگوریتمی برای حل مسائل چندهدفه ارائه خواهیم کرد. برای این منظور، در بخش دوم مقاله ابتدا به کلیاتی از الگوریتم‌های تکاملی BBO و DE پرداخته شده و سپس مفاهیمی از بهینه‌سازی چندهدفه آورده شده‌است. در بخش سوم به معرفی الگوریتم پیشنهادی خواهیم پرداخت و در بخش چهارم چگونگی ارزیابی الگوریتم پیشنهادی، توابع تست به کار‌رفته و معیارهای ارزیابی تشریح و در نهایت، نتایج شبیه‌سازی ارائه شده‌است. نتایج مقایسات با سایر الگوریتم‌های مطرح در این زمینه نشان دهنده این است که الگوریتم پیشنهادی قابل رقابت با الگوریتم‌های مطرح در زمینه بهینه‌سازی چندهدفه مانند NSGAII بوده و همواره از همگرایی مطلوب‌تر و در برخی موارد از تنوع بهتری برخوردار است. در انتهای مقاله نیز پیشنهاداتی برای تحقیقات آینده و همچنین، نتیجه‌گیری کلی ذکر خواهد شد.
شکل(1): شمای کلی سه شبه‌جزیرهو جزایر
BBO یک الگوریتم تکاملی بر پایه جمعیت است که از پدیده مهاجرت حیوانات و پرندگان بین جزایر الهام گرفته شده است. در‌واقع، جغرافیای زیستی مطالعه توزیع جغرافیایی گونه‌های زیستی می‌باشد. جزایری که مکان مناسبی برای گونه‌های جغرافیایی جهت اسکان هستند، دارای شاخص صلاحیت(HSI[4]) بالا هستند. ویژگی‌هایی که تعیین‌کننده HSIهستند، شامل فاکتورهایی مانند: بارندگی، تنوع گیاهی، ویژگی‌های نقشه‌برداری، خاک منطقه و دما
هستند (SIV[5]). جزایر با HSI بالا دارای گونه‌های زیادی هستند که به جزایر مجاور مهاجرت می‌کنند.
جزایر با HSI بالا دارای نرخ مهاجرت به داخل پایینی هستند، چراکه قبلاً توسط گونه‌های دیگر پر شده‌اند و نمی‌توانند پذیرای گونه‌های جدید باشند. جزایر با HSI پایین به خاطر جمعیت خلوت خود دارای نرخ مهاجرت به داخل بالایی هستند. مهاجرت به داخل گونه‌های جدید به مکان‌هایی با HSI پایین ممکن است که باعث افزایش HSI آن منطقه شود، زیرا مناسب بودن یک مکان متناسب با تنوع جغرافیایی آن است. کاربرد جغرافیای زیستی برای بهینه‌سازی نخستین بار به چگونگی استفاده از فرایندی طبیعی برای حل مسائل بهینه‌سازی پرداخته است. همان‌طور که برای سایر الگوریتم‌های تکاملی همانند GA، همواره عملگرهایی همانند عملگر جهش و برش مطرح میشود، در الگوریتم BBO نیز عملگرهای مهاجرت و جهش باعث ایجاد تغییرات مطلوب در روند تولید جمعیت نسل‌ها میشود.
فرض کنید که ما یک مسأله و مجموعه‌ای از راهحلهای کاندید داریم که توسط برداری از اعداد صحیح نشان داده می‌شوند. هر عدد صحیح در بردار راه‌حل می‌تواند به عنوان یک SIV (همانند ژن در GA) در نظرگرفته شود. علاوه بر این، فرض کنید که روش‌هایی برای تعیین میزان مطلوب بودن راه‌حل‌ها موجود باشد. راهحلهای مطلوب دارای HSI بالا (زیستگاه با گونه‌های زیاد) و راه حل‌های ضعیف دارای HSI پایین (زیستگاه با گونه‌های کم) هستند HSIدر BBO مشابه Fitness در سایر الگوریتم‌های بهینه‌سازی بر پایه جمعیت است.
هر زیستگاه (راه حل) در BBO دارای نرخ مهاجرت به داخل (λ) و نرخ مهاجرت به خارج (μ) است که از آنها برای به اشتراک گذاری اطلاعات به صورت احتمالی بین راه حل‌ها استفاده شده، با روابط زیر محاسبه می‌شوند:
|
(1) |
|
|
(2) |
که در آن I و E به ترتیب بیشترین مقدار نرخ مهاجرت به داخل و مهاجرت به خارج است که راه‌حل‌ها می‌توانند داشته باشند وk(i) نشان‌دهنده تعداد گونه‌ها در زیستگاه i ام است که مقداری است بین 1 تا n که n تعداد اعضای جمعیت است (مقدار n برای بهترین راه حل و مقدار 1 برای بدترین راه حل). با احتمالی هر راه حل بر اساس راهحلهای دیگر اصلاح میشود. اگر یک راه حل، برای اصلاح انتخاب شود، از نرخ مهاجرت به داخل آن (λ ) استفاده میشود تا به شکل احتمالی تعیین شود که آیا هر یک از SIVهای موجود در راه‌حل باید اصلاح شوند یا نه. اگر یک SIV موجود در راه حل Si برای اصلاح انتخاب شد، با کمک نرخ مهاجرت به خارج (μ) راهحلهای دیگر، به شکل احتمالی، تصمیم می‌گیریم که کدام یک از راه‌حل‌ها باید باعث مهاجرت یک SIV، که به صورت تصادفی انتخاب شده است، به راه‌حل Si گردد.
2-1-2- جهش
تحولات ناگهانی می‌تواند مقدار HSI یک زیستگاه را تغییر دهد. همچنین، می‌تواند باعث شوند که تعداد گونه‌ها با مقدار متعادل خود متفاوت باشند (مواد غیر‌طبیعی که از بوم‌های همسایه با آب به منطقه آورده میشود، بیماری، بلایای طبیعی و غیره). این امر را به عنوان جهش SIV در BBO مدل می‌کنیم و از احتمال تعداد گونه‌های موجود در زیستگاه برای مشخص کردن نرخ جهش استفاده میشود.
|
(3) |
که در آن (بیشترین مقدار نرخ جهش) که توسطکاربر تعریف میشود. ps احتمال اینکه زیستگاه دقیقاً دارای S گونه باشد (برای جزئیات بیشتر رک : [11]). این الگوی جهش منجر به افزایش تنوع در جمعیت می شود.
2-1-3- الگوریتم BBO
به‌طورکلی، الگوریتمBBO به صورت زیر بیان میشود :
2-2 - الگوریتم تکاملی تفاضلی
استراتژی تکامل تفاضلی[6] یک روش بهینه‌سازی احتمالاتی مبتنی بر جمعیت است. در اصول پایه تولید جمعیت اولیه و ادامه تکامل نسل‌های آینده و نگاه به ارزش‌دهی تابع ارزیاب مطابق با الگوریتم ژنتیک است. تنها عملگرهای برش و پرش در این استراتژی با رویکرد دیگری استفاده میشود. این استراتژی توسط استورن و پرایس و پیشنهاد شده است[20]. تفاوت اصلی این الگوریتم با دیگر الگوریتم‌های تکاملی در انتخاب جهت و فاصله جمعیت فعلی از دیگر عضوهای جمعیت به منظور هدایت فرایند جستجو به سوی یک جهت مطلوب است. فرایند کلی الگوریتم فوق به شکل زیر است :
2-2-1- عملگر جهش DE
عملگر جهش، برداری آزمایشی برای هر راه‌حل اصلی، والد، با جهش دادن یک بردار هدف و یک تفاضل وزن دار بین دیگر والدها، که به صورت احتمالاتی انتخاب میشود، تولید میکند. لذا برای والد i – ام، بردار آزمایشی تولید میشود و سپس:
|
(4) |
بردار هدف برای والد i ام بدین شکل تولید گردد:
|
(5) |
که یک ضریب مقیاس است و میزان تغییر تفاضل را بین جمعیت کنترل میکند. استراتژی عملگر برش در واقع یک ترکیب گسسته از بردار هدف، ، و بردار والد، ، یا بردار آزمایش، برای تولید فرزند ارائه شده‌است که به شکل زیر به دست می‌آید:
|
(6) |
3- الگوریتم پیشنهادی (MOBBO/DE)
BBO الگوریتم تکاملی بر پایه جمعیت است که ریاضیات جغرافیای‌زیستی بر آن حاکم است. DE الگوریتم ساده و قدرتمندی در حل بسیاری از مسائل بهینه‌سازی است. DE در اکتشاف فضای جستجو و تعیین مکان مینیمم سراسری خوب، ولی در استخراج راه‌حل مسأله کند است. از این رو در این مقاله قصد داریم قابلیت اکتشاف DE را با قابلیت استخراج BBO ادغام کرده، با معرفی یک عملگر مهاجرت ترکیبی، الگوریتم جدیدی برای حل مسائل بهینه‌سازی چندهدفه ارائه دهیم.
3-1- عملگر مهاجرت ترکیبی
عملگر مهاجرت ترکیبی ارائه شده برای الگوریتم پیشنهادی به شکل زیر است :
در الگوریتم پیشنهادی، علاوه بر استفاده از عملگر مهاجرت ترکیبی از فرآیند مرتب‌سازی غیرمغلوب برای بهبود همگرایی و از مفهوم فاصله جمعیتی محلی برای حفظ پراکندگی اعضای موجود در پرتو استفاده شده است. پیش از پرداختن به جزئیات الگوریتم پیشنهادی مفهوم غلبه بین دو راه حل را بیان می‌کنیم:
یک مسألهm هدفه ، در نظر بگیرید. دو پاسخ و (هر کدام دارای n متغیر تصمیم هستند) نسبت به هم می‌توانند دو حالت داشته باشند: یا یکی از این دو دیگری را مغلوب میکند یا هیچ‌کدام دیگری را مغلوب نمی‌کند. اگر یکی از شرایط زیر برقرار باشد، می‌گوییم ، را مغلوب نموده است :
اگر هیچ یک از شرایط بالا برقرار نباشد، آنگاه می‌گوییم پاسخ پاسخ را مغلوب نمی‌سازد. اگر پاسخ ، پاسخ را مغلوب نماید، می‌گوییم پاسخ توسط مغلوب شده است.
روش کار الگوریتم پیشنهادی به گونه‌ای است که به ازای هر تابعی که قصد بهینه کردن داریم، یک شبه جزیره در نظرگرفته میشود. به‌طوری‌که برای یک مسأله m هدفه، m شبه جزیره‌ای مجزا درنظرگرفته میشود که هر شبه جزیره شامل تعداد مشخصی از جزایر است. مراحل کلی الگوریتم پیشنهادی به صورت زیر است (شکل2) :
4- نتایج شبیه‌سازی
در این بخش ابتدا توابع تست به کار رفته، معیارهای ارزیابی مطرح و سپس نتایج شبیه‌سازی آورده شده‌است. در انتهای این بخش نتایج حاصل از اجرای الگوریتم با نتایج حاصل از سایر الگوریتم‌های مطرح در زمینه حل مسائل چندهدفه مقایسه میشود.
|
شکل 2 : فلوچارت الگوریتم پیشنهادی |
4-1- توابع تست برای ارزیابی کارایی
در سال 1999، depروش قانونمندی برای تولید توابع تست چندهدفه مطرح کرد، [27] Zitzler و سایرین [21] با استفاده از این روش شش مسأله چندهدفه پیشنهاد کردند. در اینجا پنج مسأله از بین شش مسأله ارائه شده، برای بررسی کارایی الگوریتم پیشنهادی انتخاب شده که عبارتند از ZDT6، ZDT4، ZDT3، ZDT2، ZDT1 .
این توابع دارای دو تابع هدف هستند:
|
(7) |
این توابع آزمون در نحوه تعریف 3 تابع ، و با یکدیگر متفاوتند. در تمامی این توابع بهینه پرتو با قرار دادن حاصل می‌گردد. هیچ یک از این توابع دارای محدودیت نیست. این توابع در جدول (1) توضیح داده شده‌اند. تعداد متغیرها، محدوده مجاز برای آنها و مجموعه پرتو بهینه و ویژگی مجموعه پرتو بهینه برای هر یک از آنها در جدول آورده است. شایان ذکر است تابع ZDT5 به علت ماهیت متفاوتی که نسبت به سایر توابع داشته است، در شبیه‌سازی‌ها در نظر گرفته نشده است. ابعاد تابع فوق (متغیرهای تصمیم) به صورت باینری بوده، حالت پیوسته ندارد.
4-2- معیارهای ارزیابی
همواره معیارهای گوناگونی برای بررسی کارایی الگوریتم‌های بهینه‌سازی چندهدفه ارائه شده است [23-21]. در این مقاله دو معیار انتخاب شده: یکی برای بررسی همگرایی و دیگری برای بررسی پراکندگی مجموعه پاسخ‌های به دست آمده :
4-2-1- معیار همگرایی
این معیار فاصله بین پاسخ‌های غیر مغلوب نهایی تولید شده توسط الگوریتم و مجموعه پرتو بهینه را پیدا میکند که در آن فاصله اقلیدسی(در فضای اهداف) بین راه‌حل و نزدیکترین عضو ، Q مجموعه نهایی پاسخ‌های غیرمغلوب، مجموعه پرتو بهینه و تعداد نقاط تعیین شده در ناحیه بهینه پرتو هستند.
|
(8) |
4-2-2- معیار پراکندگی
این معیار توسط Deb معرفی شد و به منظور سنجش میزان پراکندگی پاسخ‌های تولید شده در ناحیه پرتو بهینه به کار می‌رود. این معیار به صورت زیر تعریف می‌گردد:
|
(9) |
که در آن Q مجموعه نهایی پاسخ‌های غیرمغلوب به دست آمده توسط الگوریتم است، m تعداد نقاط تعیین شده در ناحیه بهینه پرتو و فاصله همسایگی در مجموعه جبهه پرتو به دست آمده است و مقدار میانگین تمامی و فاصله میان پاسخ‌های نهایی در مجموعه بهینه پرتو و مجموعه Q در راستای m-امین تابع هدف است. در صورتی که راه حل‌ها به طور یکنواخت گسترده شده باشند، فاصله مطابق کوچک خواهد بود.
4-3- نتایج آزمایش‌ها
نتایج حاصل از اجرای الگوریتم پیشنهادی بر روی توابع تست در نظر گرفته شده، در شکل(3) آورده شده است. در این شبیه سازی تعداد جمعیت اولیه هر یک از شبه جزایر 200 و تعداد تکرار الگوریتم 100 در نظر گرفته شده و مجموعه اعضای غیر مغلوب به‌دست‌آمده در آخرین تکرار الگوریتم به عنوان مجموعه پرتو حاصل از اجرای الگوریتم، نشان داده شده است. شایان ذکر است که منحنی نشان داده شده در هر یک از توابع بیانگر پرتو بهینه متناظر با هر تابع است که در جدول (1) نحوه به‌دست آوردن آن شرح داده شده است. همان‌طور که مشاهده میشود، الگوریتم پیشنهادی در همگرایی به پرتو بهینه خوب عمل کرده و ازdiversity مناسبی نیز برخوردار است.
در شبیه‌سازی دیگری که به منظور بررسی کارایی الگوریتم پیشنهادی در حالت‌های مختلف اجرا، از جمله تعداد جمعیت اولیه کم (تعداد جمعیت اولیه=50) و تعداد تکرارهای متغیر در نظر گرفته شده، به این نتیجه رسیدیم که الگوریتم فوق برای تعداد جمعیت‌های کم و تعداد تکرارهای پایین نیز از همگرایی مطلوب و diversity نسبتاً مناسبی برخوردار است. نتایج این شبیه سازی در شکل 4 آورده شده است. همان‌طور که مشاهده میشود، در تکرارهای پایین (تعداد نسل‌ها=10 و 20) الگوریتم قادر به یافتن اعضای غیر مغلوب نبوده ولی از نسل 30 به بعد بهبود چشمگیری در عملکرد الگوریتم مشاهده شده است و اعضای به دست آمده بسیار نزدیک به بهینه پرتو هستند و در نهایت، در نسل صدم کاملاً بر روی پرتو قرار گرفته و اعضای پرتو بدست آمده بر روی پرتو بهینه توزیع شده‌اند. اما نکته قابل توجه در مورد تابع ZDT4 است، همان‌طور که در شکل(4) دیده میشود این تابع برای تعداد جمعیت اولیه 50، برای تعداد نسل‌های متغیر رفتار متفاوتی از خود نشان داده است، زیرا در سایر توابع با افزایش تعداد نسل‌ها همگرایی به بهینه پرتو بیشتر شده، ولی در مورد این تابع در حالتی که تعداد نسل‌ها 100 در نظر گرفته شده است، پرتو به دست آمده همگرایی ضعیف‌تری دارد نسبت به حالتی که تعداد نسل‌ها 70، 50 و حتی 30 در نظر گرفته شده است و اما دلیلی که برای این امر می‌توان داشت (با توجه به جدول 1 برای ZDT4) به خاطر تعداد زیاد پرتو محلی‌هایی که این تابع دارد، احتمال افتادن در پرتو محلی بسیار بالاست.
به دلیل ویژگی این تابع، بررسی‌های بیشتری صورت گرفت و نتایجی نیز حاصل شد که نتیجه این آزمایش‌ها در شکل(5) آورده شده است. همان‌طور که دیده میشود، با افزایش تعداد جمعیت اولیه از 50 به 100 نتایج مطلوبتری بدست آمد و با افزایش تعداد نسل‌ها به 200 پرتو حاصل همگرایی بالایی به پرتو بهینه داشته است. از روی شبیه‌سازی‌های صورت گرفته بر روی این تابع، به این نتیجه رسیدیم که در صورتی که تعداد جمعیت اولیه را 200 در نظر بگیریم (حتی در تعداد نسل‌های کم)، احتمال اینکه پرتو مسأله در پرتو محلی قرار بگیرد، به شدت پایین آمده؛ به طوری که در 10 بار اجرای جداگانه الگوریتم همواره پرتو به دست آمده همگرایی بالا و diversity مطلوبی داشته است، اما برای بررسی کارایی الگوریتم پیشنهادی نسبت به سایر الگوریتم‌های مطرح از معیارهای سنجش کارایی مطرح شده در بخش (4-2) استفاده کردیم.
جدول (1): توابع تست استاندارد برای بررسی کارایی
|
ZDT 1 |
|
, , , پرتو بهینه (جبهه پرتو بهینه به صورت محدب) |
|
ZDT 2 |
|
, , , پرتو بهینه (جبهه پرتو بهینه به صورت غیر محدب) |
|
ZDT 3 |
|
, , , پرتو بهینه (جبهه پرتو بهینه به صورت گسسته) |
|
ZDT 4 |
|
, ,
پرتو بهینه (دارای تعداد زیاد جبهه پرتو بهینه محلی( )) |
|
ZDT 6 |
|
, , , پرتو بهینه (تراکم ناچیز راه حل‌ها در کنار جبهه پرتو) |
الگوریتم‌های مطرح زیادی برای حل مسائل بهینه سازی ایجاد شده‌اند که از بین آنها ما الگوریتم‌های NSGA-II [6] و SPEA[7] و PAES [24] و PDEA [25] و MODE [26] را انتخاب کردیم. نتایج حاصل از محاسبه معیارهای γو∆ با اجرای این الگوریتم‌ها بر روی توابع ZDT و نتایج حاصل از اجرای الگوریتم پیشنهادی، در جدول (2) آورده شده است.
نکته قابل توجه این است که برای تمام این شبیه سازی‌ها تعداد جمعیت اولیه 100 و تعداد نسل‌ها 250 در نظر گرفته شده است؛ به این معنی که دو معیار γو∆ برای مجموعه پرتو به‌دست آمده در انتهای نسل 250 ام محاسبه شده است. پارامترهای در نظر گرفته شده برای الگوریتم‌های مورد سنجش مطابق با مقادیری است که در مراجع آورده شده‌اند. با دقت در جدول(2) می‌توان فهمید الگوریتم پیشنهادی قابل رقابت با الگوریتم‌های مطرح در زمینه بهینه سازی مسائل چند هدفه است و حتی در بسیاری از موارد به همگرایی بهتری نسبت به سایر الگوریتم‌ها رسیده است. شایان ذکر است که اعداد قرار گرفته در جدول (2) میانگین(سطر اول) و انحراف معیار(سطر دوم) مجموعه اعداد به دست آمده برای هر یک از معیارها در 10 بار اجرای الگوریتم‌هاست (به جز برای الگورریتم MODE که برای 30 بار اجرای مستقل الگوریتم است). نتایج مقایسه این الگوریتم‌ها با سایر الگوریتم‌ها در منابع[6،27،28] آورده شده‌اند.
|
ZDT2
|
ZDT1
|
|
ZDT4
|
ZDT3
|
|
|
|
|
ZDT5
|
|
شکل(3) : نتایج حاصل از اجرای الگوریتم بر روی توابع ZDT برای تعداد جمعیت =100 و تعداد نسل‌ها=100
|
ZDT 2
|
ZDT 1
|
|
ZDT 3
|
ZDT 4
|
|
ZDT 5
|
|
شکل (4) : نتایج حاصل از اجرای الگوریتم پیشنهادی بر روی توابع ZDT با اعمال تغییرات در تعداد نسل‌ها
|
(الف) |
(ب) |
شکل(5): نتایج حاصل از اجرای الگوریتم بر روی تابعZDT4 با اعمال تغییرات در تعداد نسل‌ها.
الف) تعداد جمعیت=100 ب) تعداد جمعیت=200
5- نتیجه گیری
در این مقاله با در نظر گرفتن مجموعه‌ای از جزایر به عنوان یک شبه جزیره و تولید شبه جزایری به تعداد توابع هدف و ادغام قابلیت اکتشاف DE با قابلیت استخراج BBO، عملگر مهاجرت ترکیبی معرفی کردیم که برای حل مسائل چندهدفه ZDT استفاده شد. در این الگوریتم از فرآیند مرتب سازی غیر مغلوب برای بهبود همگرایی و از مفهوم فاصله جمعیتی محلی برای حفظ پراکندگی اعضای موجود در مجموعه پرتو استفاده شد. کارایی الگوریتم پیشنهادی با استفاده از چندین تابع تست و معیارهای مطرح در مسائل بهینه سازی چند هدفه تکاملی، ارزیابی شد. نتایج حاصل بیانگر کارایی مطلوب الگوریتم پیشنهادی حتی در تعداد تکرارهای پایین (50) و تعداد جمعیت اولیه کم (50 ) در رقابت با الگوریتم‌های مطرح دیگر است (به جز برای تابع ZDT4 که برای تعداد جمعیت اولیه کم، به دلیل پرتوهای محلی نتایج مطلوب حاصل نشد).
جدول (2): نتایج حاصل از مقایسه کارایی الگوریتم پیشنهادی با سایر الگوریتم‌ها بر اساس معیار همگرایی (γ) و معیار پراکندگی (∆).
|
توابع |
معیارها |
MOBBO/DE |
NSGA-II |
MODE |
PDEA |
PAES |
SPEA |
|
ZDT 1 |
γ |
0.002120 0.000109 |
0.033482 0.004750 |
0.005800 0.000000 |
N/A |
0.082085 0.008679 |
0.001799 0.000001 |
|
∆ |
0.585413 0.040133 |
0.390307 0.001876 |
N/A |
0.298567 0.000742 |
1.229794 0.004839 |
0.784525 0.004440 |
|
|
ZDT 2 |
γ |
0.000835 0.000053 |
0.072391 0.031689 |
0.005500 0.000000 |
N/A |
0.126276 0.036877 |
0.001339 0.000000 |
|
∆ |
0.574398 0.068690 |
0.430776 0.004721 |
N/A |
0.317958 0.001389 |
1.165942 0.007682 |
0.755148 0.004521 |
|
|
ZDT 3 |
γ |
0.010562 0.001529 |
0.114500 0.007940 |
0.021560 0.000000 |
N/A |
0.023879 0.000011 |
0.047517 0.000047 |
|
∆ |
0.750836 0.055183 |
0.738540 0.019706 |
N/A |
0.623812 0.000225 |
0.789920 0.001653 |
0.672938 0.003587 |
|
|
ZDT 4 |
γ |
0.365303 0.256633 |
0.513053 0.118460 |
0.638950 0.500200 |
N/A |
0.854816 0.527238 |
7.340299 6.572516 |
|
∆ |
0.686312 0.056378 |
0.702612 0.064648 |
N/A |
0.840852 0.035741 |
0.870458 0.101399 |
0.798463 0.014616 |
|
|
ZDT 6 |
γ |
0.003450 0.002232 |
0.296564 0.013135 |
0.026230 0.000861 |
N/A |
0.085469 0.006664 |
0.221138 0.000449 |
|
∆ |
0.750576 0.108341 |
0.668025 0.009923 |
N/A |
0.473074 0.009923 |
1.153052 0.003916 |
0.849389 0.002713 |
[*] تاریخ ارسال مقاله : 23/12/1390
تاریخ پذیرش مقاله : 24/11/1391
نام نویسنده مسئول : سمیرا عبدی دویران
نشانی نویسنده مسئول : دانشکده فنی و مهندسی، گروه کامپیوتر- دانشگاه صنعتی ارومیه- ارومیه- ایران
)