مقاله دانشگاهی – زمان بندی ماشین های موازی نامرتبط به همراه دوباره کاری با در …

۷

۱

۲

۸

۳-۶-۷٫ عمل تحول
عملگری که در این بخش معرفی میشود عملگر انتخاب بوده که وظیفه اصلی آن هدایت الگوریتم به نواحی امید بخش فضای جواب میباشد و دارای سه بخش اساسی فضای نمونه گیری[۱۵۶] ، مکانیسم نمونه گیری[۱۵۷] و احتمال انتخاب[۱۵۸] است که در زیر به تشریح هر کدام از آنها پرداخته میشود.
۳-۶-۷-۱٫ فضای نمونه گیری
عملگر انتخاب برای ایجاد نسل بعد یا از همه نوزادان و والدین استفاده میکند و یا بخشی از آن ها.
۳-۶-۷-۲٫ فضای نمونه گیری عادی[۱۵۹]
این روش به این صورت بوده که هر نوزاد بلافاصله پس از تولید جایگزین والد خود میشود. در این روش اگر Pop size اندازه جمعیت و off size اندازه نوزادان تولید شده در هر نسل باشد، اندازه فضای نمونه گیری برابر Pop size خواهد بود که شامل همه نوزادان تولید شده میباشد. اشکال اساسی این است که هیچ تضمینی برای اینکه نوزادان تولید شده بهتر از والدین باشد وجود ندارد. محققین برای غلبه بر این ایراد چند روش پیشنهاد کردند که به جای این که نوزادان جایگزین والدین خود شوند، جایگزین یک کروموزوم که به طور تصادفی انتخاب میگردد، شوند.
۳-۶-۷-۳٫ مکانیسم نمونه گیری
انتخاب چرخه رولت[۱۶۰] اولین بار توسط هالند[۶۸] پیشنهاد شد. یکی از مناسبترین انتخابهای تصادفی بوده که ایده آن بر مبنای احتمال انتخاب کروموزوم، بر اساس برازندگی آن محاسبه میشود. در روش انتخاب چرخ رولت به این صورت عمل میشود که برای انتخاب هر کروموزوم ابتدا یک عدد تصادفی بین یک و صفر تولید شده و سپس عدد مذکور در هر بازهای که قرار گرفت کروموزوم متناظر با آن انتخاب میشود. البته روش پیاده کردن چرخ رولت به این شکل است که یک ناحیه دایره شکل را در نظر گرفته و آن را به تعداد کروموزومها طوری تقسیم میکنیم که هر بخش متناظر با مقدار برازندگی کروموزوم مربوطه باشد. حال چرخ را چرخانده و هر کجا که چرخ متوقف شد به شاخص چرخ نگاه کرده، کروموزوم مربوط به آن بخش انتخاب میگردد. احتمال بقاء کروموزوم k ام برابر است با:
) (۳-۱
در زیر مراحل کلی انتخاب بر مبنای چرخه ی رولت به طور یکجا آورده شده است[۶۹].
ایده اصلی:
کروموزومهای بهتر شانس انتخاب بیشتری دارند.
شانس انتخاب هر کروموزوم متناسب با میزان برازندگی آن کروموزوم است.
برای هر کروموزوم از جمعیت مقدار برازش محاسبه میشود.(کروموزومهای با برازش بالاتر، شانس بیشتری برای انتخاب دارند.)
ابتدا برازش تجمعی را برای هر کروموزوم محاسبه میکنیم.
برازش تجمعی آخرین کروموزوم را Sum فرض میکنیم.
عدد تصادفی در فاصله را در بازه(۰,Sum) تولید میکنیم.
عدد مربوط را با برازشهای تجمعی مقایسه کنید و کروموزومی که در فاصله مربوطه قرار گرفته را انتخاب کنید.
۳-۶-۷-۴٫ احتمال انتخاب
این موضوع در مورد چگونگی تعیین احتمال انتخاب کروموزومها میباشد. در بعضی از تکنیکها، احتمال انتخاب یک کروموزوم متناسب آن بوده که دارای چند عیب میباشد. برای مثال در نسلهای اولیه گرایش برای تسلط تعدادی از کروموزومهای برتر فرآیند انتخاب وجود دارد، در حالی که در نسلهای آخر وقتی جمعیت به صورت کامل همگرا میشود رقابت بین کروموزومها خیلی جدی نبوده و تقریبا به صورت جستجوی تصادفی در میآید. یعنی در نسلهای اولیه چون مقدار برازشها معمولا با هم اختلاف زیادی دارند، لذا شانس حضور کروموزومی که برازش آن بیشتر است به مراتب بالاتر میباشد. در نسلهای پایانی چون مقدار برازش کروموزومها به هم نزدیک میشود بنابراین انتخابها تقریبا تصادفی بوده و شانس انتخاب برای اکثر کروموزومها برابر میشود.
۳-۶-۸٫ تابع برازش[۱۶۱]
همانطور که دیده شد در فرآیند انتخاب بارها از عبارت کروموزوم مناسبتر صحبت شد. بدیهی است که برای تشخیص کروموزوم مناسبتر باید یک شاخص جهت ارزیابی کروموزومها وجود داشته باشد.
در مورد مسائل بهینهسازی توابع، معمولا این تشخیص همان مقدار تابع هدف مسئله میباشد، یعنی هر کروموزوم تبدیل به جواب متناظر شده و در تابع هدف قرار میگیرد. آنگاه مقدار تابع هدف برای هر جوابی که بهتر باشد کروموزوم با آن جواب مناسبتر خواهد بود. اما در مورد بعضی مسائل پیچیدهتر باید اقدام به تعریف تابع برازش نمود.
در زیر مراحلی که باید در تابع برازش یک کروموزوم در نظر داشت آورده شده است[۱].
به تابع برازندگی، گاهی تابع ارزیابی[۱۶۲] نیز گفته میشود.
با این تابع هر کروموزوم رمز گشایی شده و به آن یک معیار و مقدار برازندگی نسبت داده میشود. برای مثال در مسئله فروشنده دوره گرد این تابع میتواند بیانگر کل فاصله تور باشد.
= مقدار برازندگی هر کروموزوم i ام
= متوسط برازندگی کروموزومهای یک نسل
= مقدار احتمال تخصیص یافته به هر کروموزوم i ام
(۳-۲)
۳-۶-۹ . استراتژی برخورد با محدودیت[۱۶۳]
بحث دیگری که در اجرای الگوریتم وجود دارد چگونگی برخورد با محدودیتهای مسئله میباشد زیرا عملگرهای ژنتیک مورد استفاده در الگوریتم باعث تولید کروموزومهای غیر موجه میشود. میکالویچ[۱۶۴] چند تکنیک معمول جهت مواجهه با محدودیت تقسیمبندی نموده است که در ادامه به چند مورد از آنها اشاره میشود.
۳-۶-۹-۱٫ استراتژی اصلاح عملگرهای ژنتیک[۱۶۵]
یک روش برای جلوگیری از تولید کروموزوم غیرموجه این است که عملگر ژنتیکی طوری تعریف گردد که پس از عمل بر روی کروموزومها، کروموزو

دانلود متن کامل پایان نامه در سایت jemo.ir موجود است

م تولید شده نیز موجه باشد. در این حالت یکسری مشکلات وجود دارد. مثلا پیدا کردن عملگری که دارای شرایط فوق باشد بسیار دشوار بوده و از مسئلهای به مسئله دیگر متفاوت میباشد.
۳-۶-۹-۲٫ استراتژی ردی[۱۶۶]