پژوهش های کارشناسی ارشد با موضوع طراحی بهینه پارتوئی مکانیزم شش میله ای برای تولید مسیر با استفاده از ... |
شکل۳-۱۱: شبه برنامه روش 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
فرم در حال بارگذاری ...
[جمعه 1400-07-30] [ 11:25:00 ق.ظ ]
|