نوع مقاله : مقاله پژوهشی فارسی
نویسندگان
1 مربی، دانشکده فنی و مهندسی، گروه کامپیوتر- دانشگاه صنعتی ارومیه- ارومیه- ایران
2 - استاد، دانشکده برق و کامپیوتر- دانشگاه صنعتی خواجه نصیرالدین طوسی- تهران- ایران
3 استادیار، دانشکده برق و کامپیوتر- دانشگاه صنعتی خواجه نصیرالدین طوسی- تهران- ایران
4 دانشجوی دکتری برق- قدرت، پژوهشکده برق جهاد دانشگاهی- تهران- ایران
چکیده
بهینه‌سازی بر پایه جغرافیای زیستی، الگوریتم تکاملی جدیدی بر اساس جمعیت است که ریاضیات جغرافیای زیستی، بر آن حاکم است و الگوریتم تکامل تفاضلی، الگوریتمی قدرتمند برای حل بسیاری از مسائل بهینه‌سازی است. الگوریتم تکامل تفاضلی در اکتشاف فضای جستجو و تعیین مکان مینیمم سراسری خوب، ولی در استخراج راه‌حل مسأله کند است. در این مقاله قابلیت اکتشاف الگوریتم تکامل تفاضلی با قابلیت استخراج الگوریتم بهینه‌سازی بر پایه جغرافیای زیستی، ادغام شده و با معرفی یک عملگر مهاجرت ترکیبی، الگوریتم جدیدی برای حل مسائل بهینه‌سازی چندهدفه ارائه شده است. در الگوریتم پیشنهادی از فرایند مرتب‌سازی غیرمغلوب برای بهبود همگرایی و از مفهوم فاصله جمعیتی محلی برای حفظ پراکندگی اعضای موجود در مجموعه پرتو استفاده شده است. در این مقاله کارایی الگوریتم پیشنهادی با استفاده از چند تابع آزمون رایج آزمایش شده و معیارهای مطرح در مسائل بهینه‌سازی چندهدفه تکاملی، ارزیابی و با الگوریتم‌های مطرح در این زمینه مقایسه شده است. نتایج حاصل بیانگر کارایی مطلوب الگوریتم پیشنهادی در رقابت با سایر الگوریتم‌های مطرح است.
کلیدواژه‌ها
عنوان مقاله [English]
Multi Objective Optimization Using Biogeography Based Optimization and Differentional Evolution Algorithm
نویسندگان [English]
- Samira Abdi 1
- Mohammad Teshnehlab 2
- Mahdi Aliyari Shouredeli 3
- hamid golahmadi 4
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 Dept. of Electrical and Computer Engineering, K.N. Toosi University of Technology, Tehran, Iran
4 Engineering Department, Iranian Research Institute for Electrical Engineering, ACECR, Tehran, Iran
چکیده [English]
Biogeography-Based Optimization (BBO) which is a new population based evolutionary optimization method inspired by biogeography and Differential Evolution (DE) is a fast and robust evolutionary algorithm for optimization problems. DE algorithm is good at the exploration of the search space and finds global minimum but is not good in exploitation of solutions. In this paper, we combine the exploration of DE with the exploitation of BBO to solve multi-objective problems by introducing a hybrid migration operator effectively.
The proposed algorithm (MOBBO/DE) makes the use of nondominated sorting approach improve the convergence ability efficiently and hence it can generate the promising candidate solutions. It also combines crowding distance to guarantee the diversity of Pareto optimal solutions. The proposed approach is validated using several test functions and some metrics taken from the standard literature on evolutionary multi-objective optimization. Results indicate that the approach is highly competitive and that can be considered a viable alternative to solve multi-objective optimization problems.
کلیدواژه‌ها [English]
- Biogeography Based Optimization Algorithm
- Differential Evolutionary algorithm
- Multi Objective Optimization
- Non domination Sort
- Crowding Distance
[*]بیشتر مسائل بهینه‌سازی که بشر در دنیای واقعی با آنها سرو کار دارد، بیش از یک هدف را دربرمی‌گیرند؛ به طوری که پاسخ بهینه مسأله هنگامی حاصل می‌گردد که کلیه اهداف به مرز خاصی از بهینگی رسیده باشند. این گونه مسائل را مسائل بهینه‌سازی چندهدفه [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): شمای کلی سه شبه‌جزیرهو جزایر
2-1- بهینه سازی بر پایه جغرافیای زیستی
BBO یک الگوریتم تکاملی بر پایه جمعیت است که از پدیده مهاجرت حیوانات و پرندگان بین جزایر الهام گرفته شده است. در‌واقع، جغرافیای زیستی مطالعه توزیع جغرافیایی گونه‌های زیستی می‌باشد. جزایری که مکان مناسبی برای گونه‌های جغرافیایی جهت اسکان هستند، دارای شاخص صلاحیت(HSI[4]) بالا هستند. ویژگی‌هایی که تعیین‌کننده HSIهستند، شامل فاکتورهایی مانند: بارندگی، تنوع گیاهی، ویژگی‌های نقشه‌برداری، خاک منطقه و دما
هستند (SIV[5]). جزایر با HSI بالا دارای گونه‌های زیادی هستند که به جزایر مجاور مهاجرت می‌کنند.
جزایر با HSI بالا دارای نرخ مهاجرت به داخل پایینی هستند، چراکه قبلاً توسط گونه‌های دیگر پر شده‌اند و نمی‌توانند پذیرای گونه‌های جدید باشند. جزایر با HSI پایین به خاطر جمعیت خلوت خود دارای نرخ مهاجرت به داخل بالایی هستند. مهاجرت به داخل گونه‌های جدید به مکان‌هایی با HSI پایین ممکن است که باعث افزایش HSI آن منطقه شود، زیرا مناسب بودن یک مکان متناسب با تنوع جغرافیایی آن است. کاربرد جغرافیای زیستی برای بهینه‌سازی نخستین بار به چگونگی استفاده از فرایندی طبیعی برای حل مسائل بهینه‌سازی پرداخته است. همان‌طور که برای سایر الگوریتم‌های تکاملی همانند GA، همواره عملگرهایی همانند عملگر جهش و برش مطرح میشود، در الگوریتم BBO نیز عملگرهای مهاجرت و جهش باعث ایجاد تغییرات مطلوب در روند تولید جمعیت نسل‌ها میشود.
2-1-1- عملگر مهاجرت
فرض کنید که ما یک مسأله و مجموعه‌ای از راهحلهای کاندید داریم که توسط برداری از اعداد صحیح نشان داده می‌شوند. هر عدد صحیح در بردار راه‌حل می‌تواند به عنوان یک 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 به صورت زیر بیان میشود :
- مقداردهی اولیه پارامترها: نگاشت راهحلهای مسأله به SIV ها و زیستگاه‌ها، تعیین بیشترین تعداد گونه‌ها، Smax، بیشترین نرخ مهاجرت E وI، بیشترین مقدار نرخ جهش، mmax، و پارامتر نخبه‌گرایی.
- تولید تصادفی راهحلهای اولیه (زیستگاه‌ها) .
- با کمک مقدار HSI تعداد گونه‌ها، S ، نرخ مهاجرت به داخل، λ، و نرخ مهاجرت به خارج، μ، مربوط به هر زیستگاه را به دست می‌آوریم.
- به کمک نرخ مهاجرت به داخل و خارج هر بوم غیرنخبه را اصلاح کرده، عملگر مهاجرت، و HSI را دوباره محاسبه می‌کنیم.
- برای هر زیستگاه، احتمال تعداد گونه‌های ساکن در آن را تغییر می‌دهیم. سپس هر زیستگاه غیرنخبه را جهش می‌دهیم، عملگر جهش و سپس مقدار HSI را برای هر بوم دوباره محاسبه می‌کنیم.
- برای تکرار بعدی به مرحله 3 باز می‌گردیم.
- این حلقه می‌تواند پس از تعداد از پیش تعیین شده نسل‌ها و یا بعد از یافتن راه‌حلی قابل قبول از مسأله، به اتمام برسد.
2-2 - الگوریتم تکاملی تفاضلی
استراتژی تکامل تفاضلی[6] یک روش بهینه‌سازی احتمالاتی مبتنی بر جمعیت است. در اصول پایه تولید جمعیت اولیه و ادامه تکامل نسل‌های آینده و نگاه به ارزش‌دهی تابع ارزیاب مطابق با الگوریتم ژنتیک است. تنها عملگرهای برش و پرش در این استراتژی با رویکرد دیگری استفاده میشود. این استراتژی توسط استورن و پرایس و پیشنهاد شده است[20]. تفاوت اصلی این الگوریتم با دیگر الگوریتم‌های تکاملی در انتخاب جهت و فاصله جمعیت فعلی از دیگر عضوهای جمعیت به منظور هدایت فرایند جستجو به سوی یک جهت مطلوب است. فرایند کلی الگوریتم فوق به شکل زیر است :
- ابتدا از عملگر جهش برای تولید یک بردار مطلوب استفاده میشود، عمل جهش در واقع از تأثیر بین افراد جمعیت فعلی صورت می‌پذیرد.
- عملگر اصلی برش که به صورت برش گسسته، دو جمله‌ای یا نمایی است، برای تولید فرزند جدید با استفاده از بردار مطلوب و یک راه‌حل (والد) به صورت احتمالی صورت می‌گیرد.
- در عمل اصلی برش همیشه یک فرزند تولید میشود که حجم محاسبات را تقریباً کاهش می‌دهد و جهت گیری فرزندان بر اساس بردار مطلوب صورت می‌پذیرد.
2-2-1- عملگر جهش DE
عملگر جهش، برداری آزمایشی برای هر راه‌حل اصلی، والد، با جهش دادن یک بردار هدف و یک تفاضل وزن دار بین دیگر والدها، که به صورت احتمالاتی انتخاب میشود، تولید میکند. لذا برای والد i – ام، بردار آزمایشی تولید میشود و سپس:
- یک بردار هدف از جمعیت انتخاب میشود؛ به گونه‌ای که باشد.
- به طور تصادفی دو والد دیگر؛ مثلاً و از جمعیت انتخاب می شود؛ به طوری‌که :
|
(4) |
بردار هدف برای والد i ام بدین شکل تولید گردد:
|
(5) |
که یک ضریب مقیاس است و میزان تغییر تفاضل را بین جمعیت کنترل میکند. استراتژی عملگر برش در واقع یک ترکیب گسسته از بردار هدف، ، و بردار والد، ، یا بردار آزمایش، برای تولید فرزند ارائه شده‌است که به شکل زیر به دست می‌آید:
|
(6) |
3- الگوریتم پیشنهادی (MOBBO/DE)
BBO الگوریتم تکاملی بر پایه جمعیت است که ریاضیات جغرافیای‌زیستی بر آن حاکم است. DE الگوریتم ساده و قدرتمندی در حل بسیاری از مسائل بهینه‌سازی است. DE در اکتشاف فضای جستجو و تعیین مکان مینیمم سراسری خوب، ولی در استخراج راه‌حل مسأله کند است. از این رو در این مقاله قصد داریم قابلیت اکتشاف DE را با قابلیت استخراج BBO ادغام کرده، با معرفی یک عملگر مهاجرت ترکیبی، الگوریتم جدیدی برای حل مسائل بهینه‌سازی چندهدفه ارائه دهیم.
3-1- عملگر مهاجرت ترکیبی
عملگر مهاجرت ترکیبی ارائه شده برای الگوریتم پیشنهادی به شکل زیر است :
- تعیین مقدار پارامترهای Fو CRو تولید تصادفی مقادیر برای هر یک از اعضای جمعیت؛
- محاسبه‌ی λ وµ مربوط به هر یک از اعضای؛
- برای تک‌تک SIV های هر یک از اعضای جمعیت، به صورت احتمالی و بر اساس مقدار ، تعیین می‌کنیم که آیا مهاجرت به داخل داشته باشد یا نه. در صورتی‌که این عضو برای اصلاح (مهاجرت به داخل) انتخاب شده باشد، بر اساس مقدار CR و به صورت احتمالی تعیین می‌کنیم که آیا این اصلاح از طریق عملگر مربوط به DE صورت گیرد و یا از روی نرخ مهاجرت به خارج سایر اعضا به صورت احتمالی مشخص شود که از چه عضوی به این عضو اصلاحات انجام گیرد؛
- در صورتی که این عضو برای مهاجرت به داخل انتخاب نشود، همان مقدار قبلی جایگزین خواهد شد.
در الگوریتم پیشنهادی، علاوه بر استفاده از عملگر مهاجرت ترکیبی از فرآیند مرتب‌سازی غیرمغلوب برای بهبود همگرایی و از مفهوم فاصله جمعیتی محلی برای حفظ پراکندگی اعضای موجود در پرتو استفاده شده است. پیش از پرداختن به جزئیات الگوریتم پیشنهادی مفهوم غلبه بین دو راه حل را بیان می‌کنیم:
یک مسألهm هدفه ، در نظر بگیرید. دو پاسخ و (هر کدام دارای n متغیر تصمیم هستند) نسبت به هم می‌توانند دو حالت داشته باشند: یا یکی از این دو دیگری را مغلوب میکند یا هیچ‌کدام دیگری را مغلوب نمی‌کند. اگر یکی از شرایط زیر برقرار باشد، می‌گوییم ، را مغلوب نموده است :
- پاسخ بدتر (اپراتور وضعیت بدتر و اپراتور وضعیت بهتر را نشان می‌دهد) از به ازای تمامی اهداف نباشد .
- پاسخ حداقل در یکی از اهداف اکیداً بهتر از پاسخ باشد ( در حداقل یکی از i ها که ).
اگر هیچ یک از شرایط بالا برقرار نباشد، آنگاه می‌گوییم پاسخ پاسخ را مغلوب نمی‌سازد. اگر پاسخ ، پاسخ را مغلوب نماید، می‌گوییم پاسخ توسط مغلوب شده است.
روش کار الگوریتم پیشنهادی به گونه‌ای است که به ازای هر تابعی که قصد بهینه کردن داریم، یک شبه جزیره در نظرگرفته میشود. به‌طوری‌که برای یک مسأله m هدفه، m شبه جزیره‌ای مجزا درنظرگرفته میشود که هر شبه جزیره شامل تعداد مشخصی از جزایر است. مراحل کلی الگوریتم پیشنهادی به صورت زیر است (شکل2) :
- ایجاد شبه‌جزایر اولیه و تولید جزایر موجود در این شبه‌جزایر (تولید جمعیت اولیه)؛
- ارزیابی هر یک از جزایر موجود در شبه‌جزایر به ازای تمامی توابع هدف؛
- بهبود جمعیت هر یک از شبه‌جزایر بر اساس عملگر ترکیبی پیشنهادی (معیار بهینه‌سازی برای شبه‌جزیره اول، تابع f1، برای شبه جزیره دوم تابع f2،...، برای شبه جزیره m ام تابعfm )؛
- تجمیع جمعیت تمام شبه‌جزایر در یک جمعیت منفرد و انتخاب بهترین اعضا بر اساس الگوریتم مرتب‌سازی غیرمغلوب؛
- وارد کردن جمعیت جدید به عنوان جمعیت نسل بعد برای هر یک از شبه جزایر؛
- در صورتی‌که شرط توقف الگوریتم دیده نشده باشد، بازگشت به مرحله دوم، در غیر این صورت، انتخاب اعضای غیرمغلوب جمعیت نهایی که در واقع همان جواب مسأله است.
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
نام نویسنده مسئول : سمیرا عبدی دویران
نشانی نویسنده مسئول : دانشکده فنی و مهندسی، گروه کامپیوتر- دانشگاه صنعتی ارومیه- ارومیه- ایران
)