مقاله با موضوع معیارهای ارزیابی، نخبه گرایی، محدودیت ها

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

ن آنها در جبهههای مختلف از نظر درجه نامغلوب بودن، با استفاده از روش مرتبسازی نامغلوبی که قبلاً شرح داده شد میرسد. سپس فاصله تراکمی نیز طبق رویه گفته شده در قبل، برای جوابها محاسبه میگردد.
۴-۲-۴- مکانیزم انتخاب۷۶
برای تولید جمعیت فرزندان از والدین، نیاز هست که طبق مکانیزم خاصی از بین والدین، تعدادی جهت اعمال عملگرهای تقاطع و جهش انتخاب شوند. روش انتخابی که در این الگوریتم بکار گرفته میشود، مسابقه دودویی۷۷ مبتنی بر عملگر مقایسه تراکمی است که قبلاً تشریح شده است.
در واقع این روش مکانیزمی برای پیاده سازی دو مفهوم مرتب سازی غیر مغلوب وفاصله ازدحام است. این روش به صورت زیر بیان می شود:
ابتدا دو کروموزوم را به طور تصادفی انتخاب کنید.
برنده بین این دو کروموزوم که به صورت زیر تعیین می شود، به عنوان خروجی انتخاب می شود.
آنکه شماره جبهه پایین تری دارد
در صورت برابری شماره جبهه ها، آنکه فاصله ازدحام بزرگتری دارد.
نحوه جبهه بندی و تعریف دقیقی از فاصله ازدحامی به صورت مبسوط در قسمت ۳-۵ توضیح داده شده است.
۴-۲-۵-عملگرهای ژنتیک
ایجاد جمعیت فرزندان از والدین که در راستای تولید جوابهای با کیفیت بهتر از نسل قبل انجام میگیرد و در واقع روندی تکاملی محسوب میشود، در الگوریتمهای ژنتیک تکامل جمعیت از طریق عملگرهای ژنتیکی همچون تقاطع وجهش و نخبه سالاری صورت می گیرد. اما هر کدام از این عملگرها، برای مسائل مختلف، انواع متنوعی دارند که کارایی هر کدام از آنها در پیشرفت الگوریتم میتواند متفاوت باشد. در ادامه عملگرهای تقاطعی و جهشی که در این پایاننامه بکار گرفته شدهاند، معرفی میگردند.
۴-۲-۵-۱- عملگرهای تقاطعی۷۸
عملگر تقاطع به منظور انتقال ویژگی های مشابه از والدین به فرزندان نسل بعد انجام می شود. در واقع باید هر فرزند بخشی از ویژگی های خود را از یک والد وباقیمانده را از والد دیگر به ارث ببرد. اگر عملگری چنین شرایطی را تضمین نکند دیگر عملگر تقاطع نامیده نخواهد شد، بلکه به آن عملگر جهش می گویند. معمولاً عملگر تقاطع دو والد را دریافت وحداکثر دو فرزند تولید می کند. پس بنابراین جهت انجام تقاطع ابتدا باید والدین(کروموزوم هایی که عملگر تقاطع روی آنها اعمال می گردد) انتخاب شوند.نحوه ی انتخاب والدین نیز در این تحقیق همانطور که اشاره شد روش تورنومنت است.نحوه اعمال عملگر تقاطع بر روی والدین انتخاب شده بدین صورت می باشد که برای هر بخش از کروموزوم یک ماتریس راهنما با ابعاد همان بخش ایجاد می گردد که درایه های آن ازاعداد باینری تشکیل شده اند.نحوه تولید فرزندان از طریق ماتریس راهنما به صورت شکل زیر می باشد.
۰.۴۷
۰.۲۵
۰.۳۱
۰.۹۱
۰.۳۶
۰.۲۵
۰.۵۲
۰.۹۱

این مطلب مشابه را هم بخوانید :   منبع مقاله با موضوعزمین لرزه، هیدرولوژی، استان تهران، تغییرات اقلیمی

۰
۱
۰
۱

۰.۴۷
۰.۴۳
۰.۳۱
۰.۷۳
۰.۳۶
۰.۴۳
۰.۵۲
۰.۷۳
شکل ۴-۶- عملگر تقاطع
در صورتی که فرزند های تولید شده محدودیت های مسئله را نقض نمایند، کنار گذاشته شده واین عملگر مجدداً اعمال می گردد.

۴-۲-۵-۲- عملگر جهش۷۹
عملگر جهش برای ایجاد پراکندگی در جوابها وجستجوی هرچه بیشتر جواب استفاده می شود. از آنجا که هیچگونه هدفمندی در عملگر جهش وجود ندارد، لذا نحوه اجرای آن به گونه ای است که کروموزوم را به طور کاملا تصادفی تغییر می دهد.برای عملگر جهش در الگوریتم ارائه شده از تولید کروموزوم جدید وجایگزین کردن آن با کروموزوم قبلی استفاده نموده ایم. به عبارت دیگر کروموزوم جدید تولید می گردد ودرصورت شدنی بودن جایگزین کروموزوم قبلی می شود.
۴-۲-۵-۳- نخبه سالاری
در الگوریتم پیشنهادی بخشی از جمعیت بدون تغییر مستقیماً از هر نسل به نسل بعد انتقال می یابند. این تعداد از بهترین جواب های هر نسل انتخاب می گردد.

شکل۳-۸- نخبه گرایی
۴-۲-۶- تکرار۸۰ الگوریتم
بعد از تولید جمعیت اولیه والدین بصورت تصادفی و ارزیابی آنها، مطابق با روش انتخاب و عملگرهای ژنتیکی که تشریح شد، جمعیت فرزندان به اندازه والدین ایجاد میشود. از ترکیب این دو مجموعه، نسل بعدی طبق ساختاری که قبلاً ارائه شد، ایجاد میگردد. به این ترتیب یک تکرار از الگوریتم انجام میگیرد و به همین ترتیب این روند تکرار میشود تا زمانی که شرط پایان الگوریتم برقرار شود. نهایتاً جبهه اول نسل آخر که در واقع جوابهای نامغلوب مجموعه هستند، بعنوان خروجی الگوریتم برگردانده میشود.
۴-۲-۷- شرط توقف۸۱ الگوریتم
شرط توقف الگوریتم در واقع معیاریست که مشخص میکند، حلقه تکرار الگوریتم تا کجا ادامه یابد و بسته به نظر طراح میتواند متمایز باشد. معمولترین شرط، تعداد دفعات تکرار الگوریتم است که مثلاً بعد از K تکرار، الگوریتم متوقف شود.در این پایان نامه نیز شرط توقف را تعداد تکرار معین انتخاب کردیم.
۴-۳- تشریح ساختار الگوریتم (۸۲NRGA) بکار رفته در این تحقیق
الگوریتم NRGA از نظر ساختار شبیه الگوریتم NSGAII می باشد، تنها تفاوت این الگوریتم
با NSGAIIدر بخش استراتژی انتخاب و بخش مرتب کردن جمعیت و انتخاب برای نسل بعد می باشد.به عبارت دیگر در الگوریتم NRGA والدین به جای روش ازدحام دودویی از روش چرخه رولت که در فصل قبل به تفصیل توضیح داده شد، انتخاب می شوند.
۴-۴-ارزیابی الگوریتم فراابتکاری دوهدفه
در این بخش به منظور ارزیابی کارایی الگوریتم های دو هدفه پیشنهادی، از معیارهای ارزیابی کارایی مسأل

دیدگاهتان را بنویسید