این روش به این صورت بوده که هر نوزاد بلافاصله پس از تولید جایگزین والد خود میشود. در این روش اگر Pop size اندازه جمعیت و off size اندازه نوزادان تولید شده در هر نسل باشد، اندازه فضای نمونهگیری Pop size خواهد بود که شامل همه نوزادان تولید شده میباشد. اشکال اساسی این است که هیچ تضمینی برای اینکه نوزادان تولید شده بهتر از والدین باشد وجود ندارد. محققین برای غلبه بر این ایراد چند روش پیشنهاد کردند که به جای این که نوزادان جایگزین والدین خود شوند، جایگزین یک کروموزوم که به طور تصادفی انتخاب میگردد، شوند.
ب) مکانیسم نمونهگیری
انتخاب چرخه رولت اولین بار توسط هالند[۳۲] پیشنهاد شد. یکی از مناسبترین انتخابهای تصادفی بوده که ایده آن بر مبنای احتمال انتخاب کروموزوم، بر اساس برازندگی آن محاسبه میشود. در روش انتخاب چرخ رولت به این صورت عمل میشود که برای انتخاب هر کروموزوم ابتدا یک عدد تصادفی بین یک و صفر تولید شده و سپس عدد مذکور در هر بازهای که قرار گرفت کروموزوم متناظر با آن انتخاب میشود. البته روش پیاده کردن چرخ رولت به این شکل است که یک دایره را در نظر گرفته و آن را به تعداد کروموزومها طوری تقسیم میکنیم که هر بخش متناظر با مقدار برازندگی کروموزوم مربوط باشد. حال چرخ را چرخانده و هر کجا که چرخ متوقف شد به شاخص چرخ نگاه کرده، کروموزوم مربوط به آن بخش انتخاب میگردد. احتمال بقاء کروموزوم k ام برابر است با:
(۳-۴)
در زیر مراحل کلی انتخاب بر مبنای چرخهی رولت به طور یکجا آورده شده است[۳۲].
ایده اصلی: ۱- کروموزومهای بهتر شانس انتخاب بیشتری دارند. ۲- شانس انتخاب هر کروموزوم متناسب با میزان برازندگی آن کروموزوم است.

  • برای هر کروموزوم از جمعیت مقدار برازش محاسبه میشود.(کروموزومهای با برازش بالاتر، شانس بیشتری برای انتخاب دارند.)
  • ابتدا برازش تجمعی را برای هر کروموزوم محاسبه میکنیم.
  • برازش تجمعی آخرین کروموزوم را Sum فرض میکنیم.
  • عدد تصادفی در فاصله را در بازه(۰,sum) تولید کنید.
  • عدد مربوط را با برازشهای تجمعی مقایسه کنید و کروموزومی که در فاصله مربوطه قرار گرفته را انتخاب کنید.

ج) احتمال انتخاب
این موضوع در مورد چگونگی تعیین احتمال انتخاب کروموزومها میباشد. در بعضی از تکنیکهای انتخاب احتمال یک کروموزوم متناسب آن بوده که دارای چند عیب میباشد. برای مثال در نسلهای اولیه گرایش برای تسلط تعدادی از کروموزومهای برتر فرآیند انتخاب وجود دارد، در حالیکه در نسلهای آخر وقتی جمعیت به صورت کامل همگرا میشود رقابت بین کروموزومها خیلی جدی نبوده و تقریباً به صورت جستجوی تصادفی در میآید. یعنی در نسلهای اولیه چون مقدار برازشها معمولاً با هم اختلاف زیادی دارند، لذا شانس حضور کروموزومی که برازش آن بیشتر است به مراتب بالاتر میباشد. در نسلهای پایانی چون مقدار برازش کروموزومها به هم نزدیک میشود بنابراین انتخابها تقریباً تصادفی بوده و شانس انتخاب برای اکثر کروموزومها برابر میشود.
۳-۸-۶٫ تابع برازش[۸۲]
همانطور که دیده شد در فرآیند انتخاب بارها از عبارت کروموزوم مناسبتر صحبت شد. بدیهی است که برای تشخیص کروموزوم مناسبتر باید یک شاخص جهت ارزیابی کروموزومها وجود داشته باشد. در مورد مسائل بهینه سازی توابع، معمولاً این تشخیص همان مقدار تابع هدف مسأله میباشد، یعنی هر کروموزوم تبدیل به جواب متناظر شده و در تابع هدف قرار میگیرد، آنگاه مقدار تابع هدف برای هر جوابی که بهتر باشد کروموزوم با آن جواب مناسبتر خواهد بود. اما در مورد بعضی مسائل پیچیدهتر باید اقدام به تعریف تابع برازش نمود.
در زیر مراحلی که باید در تابع برازش یک کروموزوم در نظر داشت آورده شده است.

  • تابع برازندگی، گاهی تابع ارزیابی[۸۳]نیز گفته میشود.
  • با این تابع هر کروموزوم رمزگشایی شده و به آن یک معیار و مقدار برازندگی نسبت داده میشود.
  • مثال: در مسأله فروشنده دورهگرد[۸۴]این تابع میتواند بیانگر کل فاصله تور باشد.
  • =مقدار برازندگی هر کروموزوم i ام
  • = متوسط برازندگی کروموزومهای یک نسل
  • = مقدار احتمال تخصیص یافته به هر کروموزوم iام

(۳-۵)

  • روشهای مختلف Min به Max

  1. (۳-۶)
  2. (۳-۷)
  3. (۳-۸)

۳-۸-۷ . استراتژی برخورد با محدودیت[۸۵]
بحث دیگری که در اجرای الگوریتم وجود دارد چگونگی برخورد با محدودیتهای مسأله میباشد زیرا عملگرهای ژنتیک مورد استفاده در الگوریتم باعث تولید کروموزومهای غیرموجه میشود. میکالویچ[۸۶] چند تکنیک معمول جهت مواجهه با محدودیت، تقسیمبندی نموده است که در ادامه به برخی از آنها اشاره می شود.

منبع فایل کامل این پایان نامه این سایت pipaf.ir است