پایان نامه رایگان درمورد نقاط بهینه

تعیین مقدار پارامتر “به اشتراک گذاری”: عموم روشهای ایجاد تنوع در جمعیت مبتنی بر مفهوم”به اشتراک گذاری” میباشند. بزرگ ترین مشکل این روشها، حساسیت کارایی آن به تنظیم پارامتر مربوطه میباشد. البته روش های تنظیم انطباقی پارامتر اشتراکگذاری در گذر از نسلهای مختلف نیز ارایه شده است اما آنها نیز نیاز به تنظیمات مربوط به خود را دارند.
در ادامه روش NSGA-II که در آن سعی در رفع کلیه مشکلات فوق شده است ارایه میشود.
برای تشریح روش NSGA-II سه موضوع مرتب سازی، تعیین تراکم افراد در فضای جستجو و نحوه انتخاب افراد برای تولید نسل بعد به ترتیب بیان میگردد
 روش مرتبسازی سریع برای جستجوی افراد غالب
 مشکل هزینه محاسباتی روشهای MOEA  مانند NSGA-II که برای ابعاد جمعیت N و تعداد توابع مطلوبیت  mمعادل O(mN^3) بود، با این الگوریتم حداکثر معادل O(mN^2)  خواهد شد. ذکر این نکته الزامی است که این مزیت در مقابل افزایش فضای ذخیره از ON به O(N^2) میسر میگردد. در صورتی که برای هر فرد i دو مشخصه محاسبه شود: ni تعداد افراد غالب برi و Si مجموعه افراد مغلوب i محاسبه این دو مشخصه O(mN^2)  مقایسه در پی خواهد داشت. افرادی که دارای=0 n_i هستند همان جبهه پارتو اول یا F_1 میباشند. اکنون برای هر فرد عضو  F_i مجموعه مغلوب S_i  را در نظر گرفته وnj مربوط به j امین عضو آن یکی کاهش داده میشود. افرادی که در آنها =0 n_j است به مجموعه H تعلق خواهند یافت. بعد از تکمیل H برای کلیه اعضای F_1 می توان گفت H جبهه پارتو دوم میباشد. برای ادامه کار F_1 را به کناری نهاده وH  به عنوان جبهه پارتو اول منظور و فرآیند فوق برای باقیمانده اعضاء تکرار میشود (براجعه، 1392).
پیش از تشریح روش انتخاب (به عنوان سومین جزء مورد نیاز برای بیان روش NSGA-II) بکارگرفته شده در این الگوریتم به توضیح مراحلی که قبل از مرحلهی انتخاب باید انجام گردد میپردازیم :
کدگذاری
الگوریتم ژنتیک به جای این که بر روی پارامتر‌ها یا متغییرهای مسئله کار کند، با شکل کد شده آن‌ها به طور مناسب سرو کار دارد.در این پژوهش از روش کدگذاری جایگشتی استفاده میشود، در این روش کروموزوم‌ها به صورت رشته‌ای از اعداد طبیعی نشان داده می‌شوند که هرکدام از این اعداد، مربوط به پارامتر ویژه‌ای در فضای حلّ مسأله است. ترتیب قرارگیری این اعداد مهم بوده و طول رشته دقیقاً با تعداد پارامترهای تعریف شده در مسأله برابر است.
ایجاد جمعیت اولیه
پس از تعیین سیستم کدینگ و مشخص شدن روش تبدیل هر جواب به کروموزوم، باید جمعیت اولیه‌ای از کروموزوم‌ها تولید نمود. در اکثر موارد، جمعیت اولیه به صورت تصادفی تولید می‌شود. اما گاهی اوقات برای بالا بردن سرعت و کیفیت الگوریتم از روش‌های ابتکاری نیز برای تولید جمعیت اولیه استفاده می‌گردد. در هر صورت عمومی‌ترین و راحت‌ترین روش، استفاده از یک رویکرد تصادفی می‌باشد. که در این پژوهش نیز همین رویکرد بکار گرفته شده است (خلیلی نیا،1390).
   محاسبه شاخص تراکم افراد در جمعیت
برای تعیین میزان تراکم افراد جمعیت حول یک نقطه مشخص که معیاری برای تنظیم تنوع در جمعیت به دست خواهد داد، متوسط نزدیکترین افراد در دو طرف نقطه مزبور برای کلیه توابع مطلوبیت درنظر گرفته میشود. کمیت idistance  مبین اندازه بزرگترین فرامستطیلی است که اولاً فرد i را در برمیگیرد و ثانیاً هیچ فرد دیگری را دربر نمیگیرد که به آن فاصله ازدحام می گویند (براجعه، 1392).
شکل 3-1 این مفهوم را برای دو تابع مطلوبیت نشان میدهد.
عملگر انتخاب در NSGA-II
در NSGA-II از روش تورنمت باینری برای عملگر انتخاب استفاده میشود. این عملگر انتخاب امکان دستیابی به جبهه پارتو در نسل آخر را به صورت یکنواخت و همگون میسر میسازد.این در حالی است که حتی الگوریتم های دیگرMOEA  مانند PAES  در صورت همگرایی به جبهه پارتو، تضمین دسترسی یکنواخت به تمامی نقاط جبهه پارتو را نمیدهند. با فرض کردن دو مشخصه irank(درجه غلبه) و idistance  (فاصله ازدحام موضعی) برای هر فرد در جمعیت، می توان عملگر مقایسه ازدحام را به صورت زیر تعریف نمود:
If ((irank = jrank) and (idistance > jdistance))
or (irank < jrank) then i≥n j  در واقع هنگام مقایسه دو فرد، فردی انتخاب میشود که مربوط به جبهه پارتو بالاتر(بهتر) یا درجه غلبه کمتری داشته باشد. در صورتی که هر دو فرد مربوط به یک جبهه پارتو باشند یعنی درجه غلبه یکسان داشته باشند، فردی انتخاب میشود که مشابه کمتری داشته باشد یعنی در محیط کم تراکمتر یا با فاصله ازدحام بزرگتری قرار گرفته باشد. شرط اول باعث همگرایی جمعیت به سمت نقاط بهینه و شرط دوم باعث همگون شدن نقاط بهینه در سراسر جبهه پارتو اول میشود (براجعه، 1392). ترکیب یکی از روشهای ترکیب جابجایی دودویی78 است، روش‌های معمول جابجایی تک نقطه79، دو نقطه80 و جابجایی یکنواخت81 می‌باشد. ساده‌ترین جابجا کردن، جابجایی تک نقطه‌ای است. در جابجایی تک نقطه‌ای، ابتدا جفت کروموزوم والد (رشته دودوئی) در نقطه مناسبی در طول رشته بریده شده و سپس قسمت‌هایی از نقطه برش، با هم عوض می‌شوند، بدین ترتیب دو کروموزوم جدید به دست می‌آید که هر نقطه از آن ژن‌هایی را از کروموزوم‌های الد به ارث می‌برند. برای جابجایی چند نقطه‌ای82 ، m موقعیت جابجا شدن، که نقطه جابجایی و طول کروموزوم می‌باشد را به صورت تصادفی و بدون تکرار انتخاب می‌کنیم، سپس جهت ایجاد فرزندی جدید بیت‌های بین نقاط مشخص شده در والدین با هم عوض می‌شوند. که در کدینگ جایگشتی و در این پژوهش از این روش استفاده گردیده است. جهش در طبیعت برخی عوامل مانند تابش اشعۀ ماوراءِ بنفش باعث به وجود آمدن تغییرات غیرقابل پیش‌بینی در کروموزوم‌ها می‌شوند. از آنجایی که الگوریتم‌های ژنتیکی از قانون تکامل پیروی می‌کنند در این الگوریتم‌ها نیز عملگر جهش با احتمال کم اعمال می‌شود. جهش باعث جستجو در فضاهای دست نخورده مسأله می‌شود می‌توان استنباط کرد که مهمترین وظیفه جهش اجتناب از همگرایی به بهینه محلّی است. در جهش ممکن است ژنی از مجموعه ژن‌های جمعیت حذف شود یا ژنی که تا حال در جمعیت وجود نداشته است به آن اضافه شود. جهش یک ژن به معنای تغییر آن ژن است و وابسته به نوع کدگذاری، روش‌های متفاوت جهش استفاده می‌شود. در این پژوهش به دلیل استفاده از کدینگ جایگشتی از روش تغییر ترتیب قرارگیری استفاده میشود. 3-4-2- پیاده سازی الگوریتم NSGA-II ابتدا جمعیت والد اولیه p_0 ایجاد میگردد. جمعیت بر اساس الگوریتم مرتبسازی، مرتب سازی شده و به هر فرد درجه غلبه یا رتبه جبهه پارتو آن نسبت داده میشود. اکنون مساله بهینهسازی چندگانه به یک مساله ساده کمینهسازی تابع مطلوبیت جبهه پارتو تبدیل شده است. عملگرهای انتخاب تورنمنت باینری، لقاح و جهش برای ایجاد جمعیت فرزندان Q_0 به تعداد N فرزند به کار گرفته میشوند. از این نسل به بعد روش کار به دلیل اعمال فرآیند الیتیسم متفاوت خواهد بود. فرآیند الیتیسم که در آن ابتدا یک جمعیت ترکیبی از والدین و فرزندان Rt= U Pt Qt تشکیل میشود. تعداد افراد در این جمعیت ۲N خواهد بود. سپس جمعیت ترکیبی بر اساس عملگر مقایسه ازدحام مرتبسازی شده و N فرد بهتر آن به عنوان جمعیت نسل آتی Pt+1 درنظر گرفته میشود. سپس با استفاده از جمعیت N تایی Pt+1 و با به کارگیری عملگرهای انتخاب، لقاح و جهش، جمعیت N تایی Qt+1  ساخته میشود و باید توجه  گردد که انتخاب با عملگر تورنمنت باینری صورت میگیرد اما معیار انتخاب بر مبنای عملگر مقایسه ازدحام ≥ n  خواهد بود. در این الگوریتم تنوع جمعیت در هر نسل با اعمال عملگر مقایسه ازدحام هنگام انتخاب تورنمنت باینری تضمین خواهد شد که در آن اصولاً نیازی به هیچ گونه پارامتر “به اشتراک گذاری” نمیباشد. لذا ضعف روش های دیگر مانند NSGA را نخواهد داشت. هم چنین می توان دید که فاصله ازدحام در فضای توابع مطلوبیت محاسبه میگردد که البته با فضای پارامترها نیز قابل محاسبه میباشد. نکته دیگر این که در ساخت جمعیت هر نسل، روش انتخاب a+b بجای (a,b) به کار رفته است که این امر پایداری روش را بالاتر خواهد برد و عدم حذف افراد خوب نسل قبل را در نسل جدید بیمه خواهد نمود (براجعه، 1392). فصل چهارم

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *