روشهای بهینهسازی و الگوریتم ژنتیک


Widget not in any sidebars
بیشینه کردن تعداد جوابهاى مجموعه بهینه پارتو
تنوع جوابها به طورى که توزیع نقاط جبهه پارتو به صورت یکنواخت و همگن باشد.
٣-۴-١ روش بهینهسازى مرتب سازى نقاط غیر برتر نسخه دوم) NSGA-II (
الگوریتم مرتبسازى نقاط غیر برتر که مبتنى بر روش الگوریتم ژنتیک بود، توسط دکتر دب در سال ١٩٩۴ معرفى گردید. در روش NSGA-II پارامترى با عنوان وجود دارد که مقدار آن در مسائل مختلف متفاوت است و کاربر با سعى و خطاهاى متعدد باید مقدار مناسبى براى آن بیابد. از آن جایى که این پارامتر تأثیر زیادى بر درستى پاسخهاى برنامه دارد و تعیین آن براى کاربران مشکل بود، روش NSGA-II توسط دکتر دب در سال ٢٠٠٢ پیشنهاد گردید [52]. در این روش پارامتر حذف شده و جاى خود را به زیربرنامه CDA داده است. این زیربرنامه براى جلوگیرى از تجمع اعضاى جمعیت در یک فاصله کوچک و جلوگیرى از خالى ماندن بقیه بازه، طراحى شده است. نحوه محاسبه CDA در شکل ٣-١١ مشاهده مىشود. همانطور که از شکل مشخص است، مقدار CDA اختصاص داده شده به هر کروموزوم در بهینهسازى دو تابع هدف برابر با محیط مستطیلى است که توسط کروموزومهاى قبل و بعد آن ساخته مىشود.
به دلیل این که در روش NSGA-II بیش از یک تابع هدف موردنظر است، تفاوت اصلى این روش با الگوریتم ژنتیک در مرتب سازى جوابهاست. به همین منظور در این روش، دو مفهوم جدید معیار شلوغى یا ازدحام جمعیت و رتبه بندى نقاط غیر برتر نسبت به الگوریتم ژنتیک وجود دارد.
٣-۴-١-١ زیربرنامه Non-Dominant Sorting (NS)
ایده اصلى مرتب سازى غیر برتر اولین بار توسط گلدبرگ پیشنهاد شد[53]. در این زیربرنامه هر کروموزوم با بقیه کروموزومهاى موجود، مقایسه مىشوند. به عنوان مثال اگر مقادیر محاسبه شده توسط دو تابع هدف در صفحه و در نظر گرفته شود، هر کدام از کروموزومها داراى دو مقدار f1 وf2 مىباشند که نقطه اى از صفحه مىباشد. در زیربرنامه NS تمام این نقاط دو به دو با هم مقایسه مىشوند، سپس هر کدام از جواب ها (نقطه ها) هر چند بار که توسط جواب دیگر مغلوب شد، محاسبه مىشود. بعد از این روند، دستهاى از جوابها که توسط هیچ کدام از دیگر جوابها مغلوب نشدند، داراى رتبه یک هستند و درجبهه اول (F1) قرار مىگیرند. سپس این نقاط را کنار گذاشته و دوباره عملیات مقایسه تکرار مىشود تا تمامى جوابها جبههبندى شوند. این زیربرنامه اعضاى جمعیت را به عنوان ورودى مىگیرد و آن ها را رتبه بندى مىکند و در جبهههاى متناسب با رتبه آنها قرار مىدهد.
٣-۴-١-٢ زیربرنامهCrowding Distance(CD)
براى مقایسه بین اعضاى یک جبهه که داراى رتبه برابر مىباشند، از این زیربرنامه استفاده مىشود یا به عبارت دیگر براى مرتبسازى درون هر جبهه، از CD استفاده مىشود. مقدار CD مربوط به هر عضو جمعیت، نسبت به عضو قبلى و بعدى و همچنین عضو اولى و آخرى جمعیت مطابق رابطه (٣-١9) و شکل ٣-12 محاسبه مى شود.
(3-19)
شکل3-12: نحوه محاسبه معیار ازدحام جمعیت در NSGA-II
لازم به ذکر است براى اینکه جواب مسئله بهترین باشد، ابتدا باید کیفیت مناسب داشته باشد (یعنى روى جبهه پارتو باشد) و در مرحله بعد باید به صورت منظم بر روى جبهه پارتو پخش شدهباشد. طبق این مفهوم، هر چه مقدار CD بیشتر باشد، نظم جوابها بر روى جبهه پارتو بیشتر است، بنابراین CD بزرگتر، معیار برترى نسبت به بقیه اعضاى درون همان جبهه است. در هنگام تعیین CD باید دقت شود که عضو اول و آخر جمعیت که در یک جبهه هستند، عضو قبلى و بعدى ندارند و عضو قبلى اولین عضو و عضو بعدى آخرین عضو در نظر گرفته مىشود، بنابراین CD این نقاط است و این نقاط اهمیت خاصى دارند.
٣-۴-١-٣ روند کلى الگوریتم NSGA-II
ابتدا تعداد N جمعیت اولیه () به صورت تصادفى تولید مىشود. سپس مقادیر توابع هدف به ازاى جمعیت اولیه محاسبه مىشوند و این اعضا رتبه بندى شده و معیار شلوغى آنها تعیین مىشوند. سپس بر اساس رتبه و CD با روش انتخاب رقابتى دوتایى، والدها انتخاب شده و بر روى آنها عملگرهاى ترکیب و جهش صورت مىگیرد. این جمعیت جدید ( ) با جمعیت قبلى ترکیب شده و دوباره عملیات مرتب سازى صورت مىگیرد (جبههبندى و تعیین معیار تراکم). از بین کل جمعیت موجود، که تعدادش از جمعیت اولیه نیز بیشتر است، به تعداد N عضو بالایى جمعیت، براى نسل بعد انتخاب مىشوند. براى انتخاب نسل بعد، ابتدا جبهههاى بالایى انتخاب و سپس اگر با انتخاب جبهه دیگر، تعداد اعضاى جمعیت از N بیشتر شود، درون آن جبهه به تعداد لازم با توجه به معیار CD انتخاب صورت مىگیرد. روند کلى الگوریتم در شکل ٣-13 نشان داده شده است.
شکل3-13: نمای کلی از عملکرد الگوریتم NSGA-II
3-5 نتیجهگیری و جمعبندی فصل
در این فصل، پس از تبیین مفاهیم اساسی بهینهسازی تک هدفه و چند هدفه، روشهای بهینهسازی تک هدفه و چند هدفه که برای انجام این پایاننامه مورد بررسی قرار گرفتهاند، تشریح شد. در بخش معرفی الگوریتمهای تک هدفه، سه الگوریتم ژنتیک، الگوریتم تجمعی ذره و ترکیب این دو الگوریتم و شیوه استفاده شده برای کار خود تشریح شد. و همچنین الگوریتم تکامل تفاضلی که نتایج کار قرار است با نتایج حاصل از آن مقایسه شود معرفی شد. در بخش بهینهسازی چند هدفه، به معرفی و تشریح الگوریتم NSGAII که برای بهینهسازی چند هدفه کار خود از آن بهره میگیریم، پرداختیم.
در فصل بعد با معرفی توابع هدف برای بهینهسازی و به کار گیری الگوریتمهای معرفی شده، به بهینه سازی و سنتز مکانیزم استفن سون نوع سوم میپردازیم.
فصل4 بهینهسازی مکانیزم ششمیلهای
4-1 مقدمه
در این فصل به ارائه سنتز بهینه ابعادی مکانیزم شش میلهای با قیدهای دورانی میپردازیم که در آن عضو کوپلری اضافه شده به مکانیزم پایه چهار میلهای، که منجر به تشکیل مکانیزم شش میلهای مورد نظر میشود، مسیر را تولید میکند. هدف از سنتز این است که مسیر تولید شده تا حد امکان به مسیر مطلوب مسئله نزدیک باشد. بهینهسازی را ابتدا تک هدفه و با یک تابع که خطای مسیر است انجام میدهیم و در مرحله بعد بهینهسازی دو هدفه که با افزودن تابع هدف انحراف زاویه انتقال است ادامه میدهیم.
دو مسیر مطلوب برای مسئله تعریف میکنیم و برای هر یک جداگانه سنتز بهینه را انجام میدهیم. مسیرها را به بخشهای ساده تر تقسیم میکنیم که مسیر اول شامل دو بخش، بخش خط راست، با شیب صفر، و بخش دوم قطاعی از دایره است. مسیر دوم به ترتیب شامل یک خط راست، با شیب صفر، و سپس قطاع دایروی و در نهایت خط راست با شیب مثبت نسبت به محور مختصات، میباشد. مکانیزمهای زیادی طی بهینه سازی با روشهای تکاملی و با بکارگیری متد کاهش کنترل شده انحراف مجاز بدست میآید. متد کاهش انحراف مجاز توسط بولاتوویچ و دوردویچ در الگوریتم تکامل تفاضلی مورد استفاده قرار گرفته است]27[. که ما از آن در دیگر الگوریتمهای مورد استفاده خود برای کاهش حداکثری انحراف بهره میبریم. شرایط مرزی اولیه یا بازه مناسب برای انحراف مجاز، ما را به سمت انباشت قابل توجه نقاط بدست آمده مسیر اطراف نقاط مطلوب مسئله هدایت میکند. مسیر مطلوب با تعداد متعددی نقاط دقت تعریف میشود.
روشهای عددی در ماشینها و ابزار حتی زمانی که مسیر مطلوب شکل ایده آلی نداشته باشد با موفقیت عمل میکند]27[. همین امر کافی است که مسیر طی شده بر طبق انحراف مجاز به مسیر مطلوب نزدیک و نزدیک تر شود. از آنجا که افزایش اعضای مکانیزم با پایین آمدن دقت در صنعت توام میشود و به موجب آن دقت مسیر نیز کاهش مییابد، ضروری است که تمرکز بیشتری بر روی مکانیزمهای با اعضای کمتر شود. از آنجا که امکان تولید مسیرهای پیچیده با کاهش اعضای مکانیزم کمتر میشود، با توجه به تنوع شکل مسیرها، بنابر این ضروری است که مسیرهای پیچیده با شکلهای نا متعارف را به مسیر های ایده آل و ساده تر تقسیم کنیم. میبایست توزیع نقاط دقت بر روی مسیر مطلوب بوسیله تابعی با زوایای ورودی عضو مولد حرکت مرتبط شوند. مقادیر انحراف از مسیر نشان دهنده توانایی کنترل سرعت عضو واسط (عضو تولید کننده مسیر) در فرآیند میباشد.
در اینجا ما قصد داریم مکانیزم شش میلهای استفنسون نوع سوم، با جفتهای سینماتیکی دوار، را سنتز بهینه کنیم. ساختار مکانیزم با افزودن یک جفت عضو با قید لولایی دورانی به یک مکانیزم پایه چهار میله ای بدست میآید. عضو اول به عضو کوپلری مکانیزم چهار میلهای افزوده میشود و عضو دوم به لولای ثابت متصل میگردد. مسیر مطلوب توسط نقطه M از عضو کوپلری مکانیزم تولید میشود.(شکل4-1)

Share this post

Post navigation

You might be interested in...