بخشی از مقاله
چكیده
الگوریتم مناسب ژنتیک طبقه بندی شده - NSGA_III - یک الگوریتم بهینه چندگانه می باشد که با استفاده از چند جهت مرجع از پیش تعریف شده و در عین حال سازگار به حفظ تنوع در میان راه حل های آن است. خصوصا طراحی حل مسائل چندگانه ای که دارای چهار یا بیشتر تابع هدف است. محدودیتی وجود دارد که مانع از استفاده NSGA_III به مسائل بهینه سازی تک هدفه که در آن تنها یک جهت مرجع وجود دارد شده است که برای این منظور یک الگوریتم یکپارچه U_ NSGA_III به تازگی طراحی شده تا مطالعه این مقاله را به عهده گیرد.U_ NSGA_III قابلیت تطبیق دهی خودکار به ابعاد شکل را دارد.
به هر حال طراحان در این مقاله امکان چشم پوشی از محدوده NSGA_III و استفاده از ارزیابی عملکرد چند گانه برای حل مسائل چند گانه ، ضربه دری و تکی را داریم.در اینجا عملکرد ارزیابی روی یک سری مسائل چند گانه ،ضربه دری ، تکی ثابت و غیر ثابت به این منظورانجام می شوند که ضعف و عیب NSGA_III چند رشته ای در مقایسه با U_ NSGA_III بررسی شوند نقطه قوت NSGA_III در هر نوع مساله نیز شرح داده شده است این مطاله یک ارزیابی مقایسه ای در مورد روند کاری NSGA_III اصلی فراهم می کند .
كلمات كلیدي:NSGA - III، بهینه سازی ،U_NSGA_III
مقدمه
جذابیت حل الگوریتم های بهینه سازی شده چندگانه برای حل مسائل چهار مورد یا بیشتر در طی ده سال گذشته رشد بسیاری کرده است.طراح به روشی از روی الگوریتم های طراحی شده تلاش می کند تا به مسائل سه گانه و دوگانه مانند ، SPEA2 و PESA[4] رسیدگی کند.زمانی که نود تای ابتدای الگوریتم ها قابلیت رسیدن به 10 یا 15 مورد را داشته باشند از الگوریتم های MOEA/D, BORG [9]و در بین دیگر موارد اخیرا از NSGA_III [6],[3] استفاده می کنند.در همه این مطالعات بیشتر تآکیدات را روی ازمایشات به شکل های مختلف و یا تکنیک مدیریتی متفاوت[1]، برای نگه داری یک تعادل بین همگرایی و اختلاف اعضای گروه داشته است. بعضی محققان نیز به اپراتورهای طراحی شده یا اپراتورهای ترکیبی موجود نگاه می کنند تا کاربرد الگوریتم های آنها را ارزیابی نمایند.
به هر حال اپراتور انتخابی بیشتر مواقع یک قسمت ثابت در اکثریت این الگوریتم ها دارد که تاثیر انتخاب به عنوان بعد مساله افزاینده ، هنوز بررسی نشده است. در این تحقیق ما از NSGA_IIIو U_ NSGA_III استفاده می کنیم تا اثر انتخاب را در سناریو های چند موردی ، ضربه دری و تکی بررسی کنیم NSGA_III از یک مکانیسم هدایتی خارجی استفاده می کند تا اختلاف بین راه حلها را نگه دارد[5] در بین پروسه های بهینه سازی هر راه حل ممکن ،تلاش می کند تا به یک جهت مرجع خارج از سری جهت های مرجع از قبل مشخص شده وصل شود. این جهت ها می توانند به صورت غیر رسمی در غیاب هر اطلاعات مرجع در بین موارد کار کند یک نرمال سازی تابعی نردبانی حاصل شده ASFدر NSGA_III جای گرفته تا موارد با رنج های مختلف را مدیریت کند.
به علاوه NSGA_III مثل پروفوسور NSGA_III تاکید روی راه حل های بی جهت داردکنیم. برای مسائل کم شده مورد تکی،روند محدود سازی بعد NSGA_III برای رسیدن به محدوده فعالیت خواسته شده تنزل پیدا کرده است . به صورت تئوری گونه فقط یک جهت مرجعی در این مورد وجود دارد - که H=1است - که خط واقعی مثبت می باشد بنابراین ،نرمال سازی و از رده خارج سازی ، ارزیابی مناسب در مورد های تکی می باشد. با توجه به محدوده قراردادی در NSGA_III با اندازه گروه - - N=Hفقط یک نفر در گروه وجود دارد . به دلیل جفت عملیات مسابقه ای ترکیبی یک اندازه گیری چند گانه چهار تایی پیشنهاد می شود. بنابراین ان چهار نفر اعضا دو عضو نتیجه در یک حرکت به وجود می اورند .بنابراین برای H=1 یک اندازه گیری گروه N=4 وجود دارد که برای ارزیابی همه مسائل بهینه سازی تکی به کار گرفته می شود.
همه محققان و برنامه نویسان گروهی ارزیابی با تجربه، می دانند که این برای یک گروه خیلی کوچیک است تا حتی برای مسائل بهینه سازی ساده به کار روند. یک الگوریتم EC گروهی نیاز به یک اندازه گروه کوچک مشخص برای اپراتور ترکیبی دارد تا اعضای حاصله مفید رابرای تحقیق اماده کند تا مناطق مربوط به فضای تحقیقاتی را ادامه دهد . [7]برای مسائل با موارد مشابه NSGA_III انتظار می رود که ناتوان باشد چون کمبود هر گونه اپراتور انتخابی دارد. با حل این مسائل در این مقالات U_ NSGA_III ، یک ضریب یکپارچه از NSGA_III را به تازگی قرار داد کردند.U_ NSGA_III در مورد توانایی برای تنزل پیدا کردن از یک الگوریتم بهینه چند مورده ضروری منحصر به فرد است چون به این صورت است که یک الگوریتم بهینه با موارد بسیار زیاد به یک الگوریتم ضربه دری تنزل می یابد و پس از ان به یک الگوریتم تکی.
با طراحی U_ NSGA_III یک اپراتور مناسب انتخابی در محدوده خاصی به NSGA_III اضافه می شود .اپراتور جدید یک عملکرد انتخابی را انجام می دهد اگر دو نفر متعلق به همان محدوده باشند واگر انها این کار را کردند ،شخص با مرتبه پایین تر انتخاب می شود . اگر هر دو یک درجه داشته باشند یکی که نزدیکتر به جهت مرجع باشد انتخاب می شود.شکل 2 نشان می دهد که چگونه اپراتور انتخابی جدید در U_NSGA_III کار می کند .به صورت اشکار انتخاب به صورت مکرر به کار می روند به عنوان مرجع - N-H - بزرگترمیشوند.
بنابراین U_ NSGA_III از محدوده N=H درNSGA_III مجزا می باشد.اندازه گیری گروه - N - بزرگتر از تعداد جهت های مرجع - H - می باشند. فرکلانس و اثر انتخابی وابسته به مقدار نسبی انها است. برای مثال در سناریوهای موارد تکی جایی که H=1 وN>>H است انتخاب در هر زمانی شکل می گیرد چون همه اشخاص به همان مرجع یکتا تعلق دارد. به عبارتی در سناریوهای موارد چند گانه جایی که N=H محدود شده تا ضریب الگوریتم سازد،هر راه حلی انتظار می رود که به یک جهت متفاوت متصل شود این به این معنا ست که انتخاب در واقع غایب است. در این مطالعه ،ما قادر بودیم که ضریب U_ NSGA_III را در مسائل موارد چند گانه ،ضربه دری و تکی نشان دهیم و موقعیت های ثابت و غیر ثابت مربوط به انها را نیز نشان می دهیم.
ما U_ NSGA_III نا محدود قرار دادی را با NSGA_III محدوده موجود با هم مقایسه می کنیم - در جایی که N=H است - اگر محدوده اعضا چشم پوشی شوند هیچ کدام از شبیه سازی ها شامل مطالعه تست شده عملیات NSGA_III نیست. در این مقاله ما امکان چشم پوشی N=H را زمانی که NSGA_III را برای انواع مختلف مسائل به کار می رود را بررسی می کنیم . عملکرد NSGA_III نا محدود با عملکرد U_ NSGA_III در یک رنج وسیع از مسائل محدود و نامحدود مقایسه می شود . ما دو فرضیه اساسی در این مطالعه در نظر می گیریم و تلاش می کنیم به صورت تجربی دقت انها را ارزیابی کنیم. در بخش 2 ما دو فرضیه مان را ارایه می دهیم و هر کدام از بحث ها را توجیه می نماییم .B2فرضیات :
از بخش قبل ما می بینیم که دو مشخصه اصلی NSGA_III نبود جهت های مرجع می باشند که یک مکانیسم هدایتی خارجی برای ارایه راه حل های مختلف داشته باشد.در دو بخش آتی فرضیه های ما جا گرفته اند و با جزییات بحث شده اند [2]
الف - کانون : NSGA_III به محض اینکه اندازه گروه برابر با تعداد ابعاد مراجع شود ، انتظار نمی رود که نبود انتخاب روی نتایج تاثیری داشته باشد چون هر بعد مرجعی انتظار می رود که فقط به یک نقطه وصل شود همان طور که انها به همین منوال نسلها پیشرفت کرده اند . به هر حال موقعیت متفاوت می شود اگر N بزرگتر از H باشد. در یک مورد بعضی از اعضای گروه با جهت های مرجع هدایت می شوند زمانی که دیگران به صورت تصادفی در فضای تحقیقاتی معلق هستند تا به دلیل نبود فشار انتخابی برای انها که در هر جایی در فضای تحقیقاتی تمرکز داشته باشند. هیچ انتخابی برای انتخاب اعضا نبودن و جهت های مرجعی ناکافی برای هدایت همه گروه باعث نمی شود این تاثیر مشهود تر باشد همان طور که شکافت هوایی بین N,H بزرگتر می شود این ما را به سمت اولین فرضیه مان هدایت می کند .
فرضیه :1در NSGA_III یک کاربر از اندازه گروه بزرگتر از تعداد ابعاد مرجع به اهستگی در کانون الگوریتم به سمت بهینه پیش می رود. یک نتیجه مستقیم از فرضیه 1 بالا این است که NSGA_III اهسته تر از هر الگوریتم تکاملی همسان شامل هر فرم انتخابی می باشد که راه حل های بهتری را ارایه می دهد. این واقعیت می تواند به صورت متفاوت جای گیرد با گفتن اینکه NSGA_III نسبت به دیگر الگوریتم های تکاملی کمتر حریص است.
ب - NSGA_III و بهینه سازی محلی : اگر چه NSGA_III انتظار می رود که اهسته تر از موارد انتخابی باشند ،این همیشه هم یک ضرر نمی باشد . در واقع این در بعضی موارد مفید هم هست به دلیل تنوع ذاتی راه حل ها با اعضای گروه اضافی در NSGA_III که در بالا بحث شد الگوریتم انتظار می رود که یک توانایی بیشتر برای فرار از بهینه سازی محلی داشته باشد همچنین انتظار می رود که روی اپراتورهای جهشی استقلال کمتری داشته باشند داشتن ذات کمتر حریص بودن الگوریتم ها درباره این رفتار رضایتمند است. از این رو ما می توانیم فرضیه دوم را ارایه دهیم
فرضیه :2
اگر N>H باشد NSGA_III یک توانایی بیشتر برای فرار از ارزیابی مقایسه ای نسبت به مورد انتخابی دارد و به ترتیب این استقلال کمتری روی اپراتور های جهشی دارد در بخش 3 نتایج ارزیابی مقایسه ای ما نشان داده شده و موارد مهم این دو فرضیه را به بحث گذاشته است علاوه بر حمایت فرضیه هایمان مانند یک تصویر روشن از عملکرد NSGA_III چند رشته ای برای مسائل بهینه سازی شده چند موردی ، ضربه دری و تکی ارایه می دهیم . ما دو ازمایش انجام می دهیم در هر دو ازمایش ما NSGA_III را با U_ NSGA_III مقایسه می کنیم همان طور که قبلا گفته شد U_ NSGA_III یک تنوع از NSGA_III با اپراتور انتخابی تو رفته اضافی است.نویسنده قبلا نشان داد که U_ NSGA_III در شبیه سازی تک مورد برابر با یک استراتژی تکاملی استاندارد - λ+µ - است. پارامترهای به کار رفته در شبیه سازی های تک مورد ما در جدول 1 نشان داده شده اند .
برای هر مساله N=20 - تعداد متغییر ها - به کار می رود . نتایج نشان داده شده در همه نقاط این مطالعه میانگین 11 شبیه سازی با همان سری پارامتر ها است. با توجه به ابعاد بالا تر U_ NSGA_III و NSGA_III با یکدیگر با رعایت موقعیت N=H در هر دوی الگوریتم ها مقایسه می شوند. با استفاده از همان تنظیمات U_ NSGA_III و NSGA_III تنزل می یابد بعد از اینکه اپراتور انتخابی اضافی تاثیرش را از دست داد اینجا در همه مقایسه ها یمان ،از همان تعدادگروه ها برای هر دوی الگوریتم ها استفاده می کنیم این ما را ناتوان می کند تا اثر انتخاب را در ابعاد بالاتر به خوبی بررسی نماییم. ازمایش اول مقایسه NSGA_III و U_ NSGA_III با استفاده از رشته های اعضای چند گانه می باشد. در مورد مسائل تک مورده فقط یک جهت مرجع وجود دارد که تقریبا موقعیت n>>h دارد ارزیابی مقایسه ای ما روی یک گره غیر ثابت به علاوه مسائل ثابت در یک رنج وسیع از مسائل انجام می شود.
مسائل تست غیر ثابت با نام های Ellipsoidal ،Rosenbrock ، Schwefel ،Ackley و Rastriginsفهرست شده در روابط 1تا 5 می باشد در حالی که مسائل ثابت با فرم , G01, G02 ,G04 , G06, G07,G08 , G10, G18 G24از موقعیت G تست استاندارد می باشد هر شکل هر دو روش را برای سه نوع اندازه گروه 100:و300و500 با هم مقایسه می کند تنها استثنا نسبتا مساله ساده ellipsoidalاست که برای این است که ما از N=48 و100 و 148 استفاده می کنیم.
