شکل۳-۱۱: شبه برنامه روش GAPSO

 

 

 

با توجه به اینکه هر کدام از الگوریتم­هاى بهینه­سازى، متناسب با ماهیت مسئله مى تواند بر دیگرى برترى داشته باشد و براى اینکه کارایى این الگوریتم­هاى تک هدفى بر روى مکانیزم شش­میله­ای مشخص شود، در فصل بعد مقایسه­اى از آنها در به دست آوردن مقدار بهینه توابع هدف مسئله موردنظر در این پایان نامه، بررسى مى­شوند.
٣-۴ روش هاى بهینه سازى چند هدفى
در اکثر زمینه­هاى علمى، مسائل بهینه­سازى بیش از یک تابع هدف دارند. همچنین در بیش­تر این مسائل، اهداف موردنظر که مى­بایست بهینه شوند، در تقابل با یکدیگر هستند. در چنین حالتى یافتن جوابى که بهترین تعادل ممکن را بین اهداف برقرار سازد، مطلوب است. به طور کلى هنگام حل یک مسئله بهینه­سازى چند­هدفى، دستیابى به نتایج زیر مدنظر است:
بیشینه کردن تعداد جواب­هاى مجموعه بهینه پارتو
تنوع جواب­ها به طورى که توزیع نقاط جبهه پارتو به صورت یکنواخت و همگن باشد.
٣-۴-١ روش بهینه­سازى مرتب سازى نقاط غیر برتر نسخه دوم[۸۲]) NSGA-II (
الگوریتم مرتب­سازى نقاط غیر برتر که مبتنى بر روش الگوریتم ژنتیک بود، توسط دکتر دب در سال ١٩٩۴ معرفى گردید. در روش NSGA-II پارامترى با عنوان  وجود دارد که مقدار آن در مسائل مختلف متفاوت است و کاربر با سعى و خطاهاى متعدد باید مقدار مناسبى براى آن بیابد. از آن جایى که این پارامتر تأثیر زیادى بر درستى پاسخ­هاى برنامه دارد و تعیین آن براى کاربران مشکل بود، روش NSGA-II توسط دکتر دب در سال ٢٠٠٢ پیشنهاد گردید [۵۲]. در این روش پارامتر حذف شده و جاى خود را به زیربرنامه CDA داده است. این زیربرنامه براى جلوگیرى از تجمع اعضاى جمعیت در یک فاصله کوچک و جلوگیرى از خالى ماندن بقیه بازه، طراحى شده است. نحوه محاسبه CDA در شکل ٣-١١ مشاهده مى­شود. همانطور که از شکل مشخص است، مقدار CDA اختصاص داده شده به هر کروموزوم در بهینه­سازى دو تابع هدف برابر با محیط مستطیلى است که توسط کروموزوم­هاى قبل و بعد آن ساخته مى­شود.
به دلیل این که در روش NSGA-II بیش از یک تابع هدف موردنظر است، تفاوت اصلى این روش با الگوریتم ژنتیک در مرتب سازى جواب­هاست. به همین منظور در این روش، دو مفهوم جدید معیار شلوغى[۸۳] یا ازدحام جمعیت و رتبه بندى نقاط غیر برتر[۸۴] نسبت به الگوریتم ژنتیک وجود دارد.
٣-۴-١-١ زیربرنامه Non-Dominant Sorting (NS)
ایده اصلى مرتب سازى غیر برتر اولین بار توسط گلدبرگ پیشنهاد شد[۵۳]. در این زیربرنامه هر کروموزوم با بقیه کروموزوم­هاى موجود، مقایسه مى­شوند. به عنوان مثال اگر مقادیر محاسبه شده توسط دو تابع هدف در صفحه  و  در نظر گرفته­ شود، هر کدام از کروموزوم­ها داراى دو مقدار f1 وf2 مى­باشند که نقطه اى از صفحه مى­باشد. در زیربرنامه NS تمام این نقاط دو به دو با هم مقایسه مى­شوند، سپس هر کدام از جواب ها (نقطه ها) هر چند بار که توسط جواب دیگر مغلوب شد، محاسبه مى­شود. بعد از این روند، دسته­اى از جواب­ها که توسط هیچ کدام از دیگر جواب­ها مغلوب نشدند، داراى رتبه یک هستند و درجبهه[۸۵] اول (F1) قرار مى­گیرند. سپس این نقاط را کنار گذاشته و دوباره عملیات مقایسه تکرار مى­شود تا تمامى جواب­ها جبهه­بندى شوند. این زیربرنامه اعضاى جمعیت را به عنوان ورودى مى­گیرد و آن ها را رتبه بندى مى­کند و در جبهه­هاى متناسب با رتبه آنها قرار مى­دهد.
٣-۴-١-٢ زیربرنامهCrowding Distance(CD)
براى مقایسه بین اعضاى یک جبهه که داراى رتبه برابر مى­باشند، از این زیربرنامه استفاده مى­شود یا به عبارت دیگر براى مرتب­سازى درون هر جبهه، از CD استفاده مى­شود. مقدار CD مربوط به هر عضو جمعیت، نسبت به عضو قبلى و بعدى و همچنین عضو اولى و آخرى جمعیت مطابق رابطه (٣-١۹) و شکل ٣-۱۲ محاسبه مى شود.

 

 

 

 

(۳-۱۹)

 

 

 

 

 

 

 

 

 

 

شکل۳-۱۲: نحوه محاسبه معیار ازدحام جمعیت در NSGA-II

 

 

 

لازم به ذکر است براى اینکه جواب مسئله بهترین باشد، ابتدا باید کیفیت مناسب داشته باشد (یعنى روى جبهه پارتو باشد) و در مرحله بعد باید به صورت منظم بر روى جبهه پارتو پخش شده­باشد. طبق این مفهوم، هر چه مقدار CD بیشتر باشد، نظم جواب­ها بر روى جبهه پارتو بیشتر است، بنابراین CD بزرگتر، معیار برترى نسبت به بقیه اعضاى درون همان جبهه است. در هنگام تعیین CD باید دقت شود که عضو اول و آخر جمعیت که در یک جبهه هستند، عضو قبلى و بعدى ندارند و عضو قبلى اولین عضو  و عضو بعدى آخرین عضو  در نظر گرفته مى­شود، بنابراین CD این نقاط  است و این نقاط اهمیت خاصى دارند.
پایان نامه - مقاله - پروژه
٣-۴-١-٣ روند کلى الگوریتم NSGA-II
ابتدا تعداد N جمعیت اولیه (  ) به صورت تصادفى تولید مى­شود. سپس مقادیر توابع هدف به ازاى جمعیت اولیه محاسبه مى­شوند و این اعضا رتبه بندى شده و معیار شلوغى آنها تعیین مى­شوند. سپس بر اساس رتبه و CD با روش انتخاب رقابتى دوتایى[۸۶]، والدها انتخاب شده و بر روى آنها عملگرهاى ترکیب و جهش صورت مى­گیرد. این جمعیت جدید (  ) با جمعیت قبلى ترکیب شده و دوباره عملیات مرتب سازى صورت مى­گیرد (جبهه­بندى و تعیین معیار تراکم). از بین کل جمعیت موجود، که تعدادش از جمعیت اولیه نیز بیشتر است، به تعداد N عضو بالایى جمعیت، براى نسل بعد انتخاب مى­شوند. براى انتخاب نسل بعد، ابتدا جبهه­هاى بالایى انتخاب و سپس اگر با انتخاب جبهه دیگر، تعداد اعضاى جمعیت از N بیشتر شود، درون آن جبهه به تعداد لازم با توجه به معیار CD انتخاب صورت مى­گیرد. روند کلى الگوریتم در شکل ٣-۱۳ نشان داده شده است.

 

 

­­­­

 

 

 

شکل۳-۱۳: نمای کلی از عملکرد الگوریتم NSGA-II

 

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...