دانلود مقاله محاسبه پارامتر کنترلی به نام فاصله جمعیت و الگوریتم بهینه سازی

دانلود پایان نامه

3-11-1. الگوریتم ژنتیک با مرتب سازی نامغلوب (چند هدفه)


همانطور که در فصل قبل نیز به آن اشاره شد، الگوریتم ژنتیک با مرتب سازی نامغلوب توسط دِب و همکارانش در سال ۲۰۰۰ معرفی گردید که ویژگی های عمده آن عبارتند از:
تعریف فاصله تراکمی (Crowding Distance) به عنوان ویژگی جایگزین برای شیوه هایی مانند اشتراک برازندگی
استفاده از عملگر انتخاب تورنومنت دو-دویی
ذخیره و آرشیو کردن جواب های نامغلوب که در مراحل قبلی الگوریتم به دست آمده اند (نخبه گرایی) 
در الگوریتم (NSGA-II) از میان جواب های هر نسل، تعدادی از آن ها با استفاده از روش انتخاب تورنمنت دو-دویی انتخاب می شوند. در روش انتخاب دو-دویی، دو جواب به تصادف از میان جمعیت انتخاب می شوند و سپس میان این دو جواب، مقایسه ای انجام می شود و هر کدام که بهتر باشد، نهایتا انتخاب می شود. معیارهای انتخاب در الگوریتم (NSGA-II) در درجه اول، رتبه جواب و در درجه دوم فاصله تراکمی مربوط به جواب است. هر چه قدر رتبه جواب کمتر باشد و دارای فاصله تراکمی بیشتری باشد، مطلوب تر است.
با تکرار عملگر انتخاب دو-دویی بر روی جمعیت هر نسل، مجموعه ای از افراد آن نسل برای شرکت در تقاطع (Crossover) و جهش (Mutation) انتخاب می شوند. بر روی بخشی از مجموعه افراد انتخاب شده، عمل تقاطع و بر روی بقیه، عمل جهش انجام می شود و جمعیتی از فرزندان و جهش یافتگان ایجاد می شود. در ادامه، این جمعیت با جمعیت اصلی ادغام می شود. اعضای جمعیت تازه تشکیل یافته، ابتدا برحسب رتبه و به صورت صعودی مرتب می شوند. اعضایی از جمعیت که دارای رتبه یکسانی هستند، بر حسب فاصله تراکمی و به صورت نزولی مرتب می شوند. حال اعضای جمعیت در درجه اول بر حسب رتبه، و در درجه دوم بر حسب فاصله تراکمی مرتب سازی شده اند. برابر با تعداد افراد جمعیت اصلی، اعضایی از بالای فهرست مرتب شده انتخاب می شوند و بقیه اعضای جمعیت دور ریخته می شوند. اعضای انتخاب شده جمعیت نسل بعدی را تشکیل می دهند. و چرخه مذکور در این بخش، تا محقق شدن شرایط خاتمه، تکرار می شود. جواب های نا مغلوب به دست آمده از حل مسأله بهینه سازی چندهدفه، غالبا به نام جبهه پارتو شناخته می شوند. هیچ کدام از جواب های جبهه پارتو، بر دیگری ارجحیت ندارند و بسته به شرایط، می توان هر کدام را به عنوان یک تصمیم بهینه در نظر گرفت .

مطلب مشابه :  دانلود پایان نامه ارشد با موضوع قانون آیین دادرسی کیفری و اقدامات تأمینی و تربیتی

3-11-2. گام های الگوریتم ژنتیک با مرتب سازی نامغلوب
به عبارتی دیگر، این الگوریتم با اضافه شدن دو عملگر ضروری به الگوریتم ژنتیک تک هدفه معمولی، به یک الگوریتم چند هدفه تبدیل شده است که به جای یافتن بهترین جواب، دسته ای از بهترین جوابها را می دهد که با نام پارتو فرانت شناخته می شوند. این دو عملگر عبارتند از:
1) عملگری که یک معیار برتری (رتبه) بر اساس مرتب سازی نا مغلوب به اعضای جمعیت اختصاص می دهد و 2) عملگری که تنوع جواب را در میان جوابهای با رتبه برابر حفظ نگه می دارد.
با توجه به توضیحات بالا ،فلوچارت و همچنین گام های این الگوریتم را می توان به صورت زیر بیان کرد :
نمودار 3-1 الگوریتم بهینه سازی ژنتیک با مرتب سازی نامغلوب (NSGA-II)
گام اول: تولید جمعیت اولیه در این روش همانند معمول بر مبنای مقیاس و قیود مسأله
گام دوم: ارزیابی جمعیت تولید شده از دید توابع هدف تعریف شده
گام سوم: اعمال روش مرتب سازی نامغلوب، اعضای جمعیت در داخل دسته هایی قرار گرفته به گونه ای که اعضای موجود در دسته اول، یک مجموعه کاملاً غیرمغلوب توسط دیگر اعضاء جمعیت فعلی می باشند. اعضای موجود در دسته دوم نیز بر همین مبنا تنها توسط اعضای دسته اول مغلوب شده و این روند به همین صورت در دسته های دیگر ادامه یافته تا به تمام اعضای موجود در هر دسته، یک رتبه بر مبنای شماره دسته اختصاص داده شود.
گام چهارم : محاسبه پارامتر کنترلی به نام فاصله جمعیت (Crowding Distance)، این پارامتر برای هر عضو در هر گروه محاسبه می شود و بیان گر اندازه ای از نزدیکی نمونه مورد نظر به دیگر اعضای جمعیت آن دسته و گروه می باشد. مقدار بزرگ این پارامتر منجر به واگرایی و گستره بهتری در مجموعه اعضای جمعیت خواهد شد.
گام پنجم : انتخاب جمعیت والدین برای تولید مثل، یکی از مکانیزم های انتخاب مبتنی بر تورنمنت دوتایی میان دو عضو منتخب به طور تصادفی از میان جمعیت می باشد.
گام ششم: انجام جهش و تقاطع
3-12. جمع بندی
در این فصل مدل ریاضی طراحی شبکه زنجیره تأمین مورد نظر به همراه ویژگی ها ، فرض ها ، محدودیت ها و … ارائه و در پایان نیز توضیحاتی جامع در مورد ساختار و نحوه عملکرد الگوریتم حل این مدل ارائه گردید که در فصل بعدی با مثال های عددی نحوه عملکرد مدل و الگوریتم آن را به طور کامل مورد بررسی قرار می دهیم.
فصل چهارم
نتایج محاسباتی
و