الگوریتم بهینه سازی نخبه گرا //پایان نامه بهينه‌ سازي و الگوريتم ژنتيك

دانلود پایان نامه

الگوریتمهای بهینه سازی نخبه گرا براساس رتبه بندی پارتو

عبارت نخبه گرائی در ادبیات الگوریتم­های تکاملی به معنای نگهداری و حفظ والدین خوب و انتقال آنها از نسلی به نسل دیگر جهت شرکت دادن آنها در فرآیند انتخاب و ترکیب می باشد. سابقه اولین استفاده از مفهوم نخبه گرائی حدودا به همان سالهای اولیه توسعه الگوریتم­های MOGA، NSGA و NPGA برمی­گردد و به طور مشخص و مفصل در حدود  سال های 94-1993 مورد بررسی قرار گرفت.

در بعضی الگوریتم­های MOEA نخبه گرا، استراتژی نخبه گرائی، حفظ جوابهای غیرپست می باشد. حفظ این جواب­ها معمولا توسط یک جمعیت خارجی ممکن می­شود. بسیاری از طرح های اولیه این الگوریتم توسط Zitzler‌ مورد بررسی قرار گرفت ولی اولین مقاله منتشر شده در این زمینه، مقاله Parks و Miller است. آنان در الگوریتم خود از یک جمعیت خارجی استفاده کردند که اعضای آن تقریباً تمامی راه­حلهای غیرپست می باشند. در این الگوریتم، جمعیت موردنظر محدود بوده و یک راه حل تنها در صورتی می­تواند وارد آن شود که به طور قانع کننده­ای با جوابهای موجود متفاوت باشد. در ادامه کار، طی فرآیند انتخاب، الگوریتم بهینه سازی به طور فعالی از جمعیت موردنظر استفاده می­نماید. در مقاله مذکور، استراتژی­های مختلف انتخاب از میان جمعیت خارجی، مورد بررسی قرار گرفته­اند.

حدوداً سالهای 1994،‌ Zitzler  و Thiele کاربردی‌ترین الگوریتم MOEA را که تا به حال ارائه شده است، پیشنهاد دادند. این الگوریتم که SPGA نام دارد از دو جمعیت مجزا که یکی خارجی و دیگری داخلی می­باشد استفاده شده است. در الگوریتم مذکور، جمعیت خارجی که محدود نیز می باشد جهت ذخیره جوابهای غیرپست قبلی مورد استفاده قرار می گیرد. در ادامه روند بهینه سازی، با به دست آوردن یک جواب غیرپست جدید از درون جمعیت جدید داخلی  و وارد شدن آنها به مجموعه پارتو دو اتفاق رخ می دهد:

الف) جوابهایی که جواب غیرپست جدید بر آنها چیره شده است از این مجموعه حذف می شوند.

ب) تعدادی از این راه حلها نیز به صورت دسته­ای از جمعیت خارج می شوند.

اتفاق دوم برای اطمینان از محدود بودن مجموعه پارتو رخ می دهد.

در این الگوریتم، جمعیت داخلی جدید با انتخاب از درون مجموعه ای که ترکیب دو جمعیت داخلی و خارجی قبلی است حاصل می گردد. ایده جالب یا شاید نقطه قوت این الگوریتم نوع تعامل دو جمعیت داخلی و خارجی در نسبت دادن مقادیر برازندگی می باشد.

در الگوریتم SPGA، به هر عضو از جمعیت خارجی و براساس تعداد جوابهایی از جواب داخلی که جواب مذکور می تواند بر آنها غلبه کند یک توانایی نسبت داده می شود سپس به هرکدام از اعضای مجموعه داخلی یک عدد تقریبی برازندگی براساس مجموع تواناییهای جوابهای خارجی غلبه کننده بر آن نسبت داده می شود. فرایند تخصیص برازندگی مذکور یک رهیافت تکاملی- همکاری بین دو جمعیت خارجی و داخلی می باشد.

تعداد زیادی از الگوریتم های مختلف MOEA‌ نیز بر همین اساس ولی با تغییرات کوچکی در نحوه نسبت دادن مقادیر برازندگی، نحوه انتخاب از جمعیت و نیز روشهای مختلف حفظ پراکندگی ارائه شده است. الگوریتمهایی نظیر PAES، PESA و NSGA-II  از آن جمله­اند. هدف اصلی آنها ایجاد تغییراتی در ساختار این الگوریتمها جهت حفظ پراکندگی و محدود کردن فضای هدف که الگوریتمهای MOGA و NSGA با آنها دست به گریبان بوده اند می باشد. علاوه بر این، کنترل میزان نخبه گرائی از جمله مواردی است که در همین راستا مورد بررسی قرار گرفته است.

الگوریتمهای تکاملی چندهدفه که در آنها مرتب سازی به صورت غیرپست انجام می شود عموما سه مشکل عمده دارند:‌

1- پیچیدگی در محاسبات 2- رویکرد بدون نخبه گرایی 3- نیاز برای تعیین پارامترهای مشترک

برای رفع مشکلات موجود، الگوریتم NSGA-II توسط Srinvas و Deb در 2001 پیشنهاد شد که الگوریتمی سریع در محاسبات می باشد و در آن، انتخاب برپایه ترکیبی از دو نسل متفاوت (والد و فرزندان) می باشد که با انتخاب بهترین جوابها همراه است. این مدل نیاز به محاسبات کمتری دارد و به دلیل رویکرد نخبه گرایی آن و پارامترهای مشترک کمتر، نتایج بهتری از شبیه سازی با این روش به دست می آید.

گامهای این الگوریتم از این قرار می باشند:

الف) تولید تصادفی جمعیت والد (P0) با اندازه N

ب) مرتب سازی جمعیت والد براساس نقاط غیرپست

ت) برای هر جواب غیرپست، یک تابع برازش (رتبه) معادل سطح غیرپست آن درنظر بگیرد

ث) تولید جمعیت فرزندان (Q0) با اندازه N با استفاده از انتخاب و تزویج

ج) تولید نسل از روی نسل اولیه مطابق دستورات ذیل:

  • تولید مجموعه جواب (Qt،Pt) با نام Rt با اندازه 2N با ترکیب جمعیت والد (Pt) و جمعیت فرزندان (Qt)
  • مرتب سازی جمعیت ترکیب شده () مطابق با فرآیند مرتب سازی الگوریتم غیرپست به منظور تعیین جبهه­های غیرپست (Fl، ….، F2، F1)
  • تولید جمعیت والد نسل بعد (Pt+1) با اندازه N با اضافه کردن جوابهای غیرپست با رتبه اول (F1) و جبهه­های متوالی با رتبه غیرپست (Fl، ….، F2، F1) از اندازه N بیشتر می شود.

بدین منظور برای تولید N عضو، نیاز است که بعضی از جوابهای غیرپست با رتبه بدتر از آخرین جبهه حذف می شوند، این بدین معنی است که مرتب سازی برپایه عملگرهای مقایسه­ای اذحام براساس فاصله آنها در هر جوابی از جبهه غیرپست F1 ام انجام می­شود. بدین ترتیب، جمعیت والد جدید () با اندازه N ساخته می شود.

دانلود پایان نامه