انتخاب والد در الگوریتم های ژنتیک

انتخاب والد :
انتخاب والد پروسه‌ای انتخاب والدینی است که قرار است با یکدیگر ترکیب شده و اولاد هایی را برای نسل بعدی ایجاد کنند. انتخاب والد برای نرخ همگرایی یک الگوریتم ژنتیک بسیار حیاتی است و  انتخاب خوب والدین الگوریتم ژنتیک را به  راه حل های بهتر و مناسبتر سوق می دهد.
انتخاب یک راه حل در جمعیتی با تعداد کمی از نسل ها می‌تواند میزان تنوع در راه حل‌ها را بکاهد.بنابراین حفظ تنوع خوب در جمعیت در موفقیت الگوریتم ژنتیک بسیار حیاتی است .در نظر گرفته شدن کل یک جمعیت بوسیله یک راه حل بسیار خوب تحت نام همگرایی نابهنگام (premature convergence) نامیده می‌شود که یک وضعیت نامطلوب در الگوریتم ژنتیک است.
انتخاب مناسب برازش (Fitness Proportionate Selection)
انتخاب برازش مناسب یکی از شیوه‌های مرسوم در انتخاب والد می باشد.در این روش هر شخصی می‌تواند با توجه به احتمال متناسب با برازش خود یک والد باشد.بنابراین اشخاص مناسبتر دارای شانس بالاتر برای زاد و ولد و انتشار ویژگی‌های خود به نسل های بعدی دارند.بنابراین این استراتژی در انتخاب موجب می‌شود که افرادی که درای شایستگی بیشتری در جمعیت هستند انتخاب شوند و ویژگی های این افراد در طول زمان رشد و نمود پیدا کند
یک چرخ دایره‌ای شکل را در نظر بگیرید.چرخ به n تکه تقیسیم شده است.در واقع n نشان دهنده شماره شخص در جمعیت می باشد.هر شخص یک قسمت از دایره را در اختیار دارد که فضایی که در اختیار شخص است نشان دهنده تناسب مقدار برازش آن شخص می باشد.دو شیوه برای انتخاب برازش مناسب امکان‌پذیر می‌باشد

انتخاب چرخ رولت.Roulette Wheel Selection

در انتخاب چرخ رولت ، چرخ دایره‌ای (مدور) به همان شکلی که قبلاً توضیح داده شد تقسیم شده است.همانگونه که در شکل نشان داده خواهد شد یک نقطه ثابت در پیرامون چرخ انتخاب می‌شود و سپس چرخ ، چرخانیده می‌شود .ناحیه ای از چرخ که در جلوی نقطه ثابت در نظر گرفته شده قرار گیرد به عنوان والد انتخاب می شود.برای انتخاب والد دوم رویه ای مشابهی تکرار می شود. در شکل زیر  استفاده از روش چرخ رولت نشان داده شده است

واضح است که فرد مناسبتر دارای سهم بزرگتری در چرخ است و بنابراین شانس بیشتری هم برای ایستادن در مقابل نقطه ثابت هنگامی که چرخ ، چرخانیده می‌شود دارد.شانس انتخاب یک فرد به طور مستقیم وابسته به مقدار برازش آن است.
در قسمت ذیل یک شبکه کد برای انتخاب توسط چرخ رولت آورده شده است :

for all members of population

     sum += fitness of this individual

end for

for all members of population

probability = sum of probabilities + (fitness / sum)

sum of probabilities += probability

end for

loop until new population is full

do this twice

number = Random between 0 and 1

for all members of population

if number > probability but less than next probability then you have been selected

end for

end

create offspring

end loop

نمونه برداری فراگیر تصادفی :Stochastic Universal Sampling (SUS)
.
نمونه برداری فراگیر تصادفی کاملاً مشابه روش انتخاب والد به شیوه چرخ رولت است ، هرچند بجای اینکه تنها یک نقطه ثابت بر روی چرخ داشته باشیم در این شیوه همانگونه که در شکل نشان داده شده است چندین نقطه ثابت بر روی چرخ داریم.بنابراین همه والد ها تنها در یک چرخش از چرخ(دایره) انتخاب می شوند.این شیوه از انتخاب والد اجازه می‌دهد که افراد که لیاقت بالایی دارند حد اقل یک بار شانس انتخاب شدن داشته باشند.

این نکته را باید بازگوکنم  که متدهای انتخاب برازش مناسب در مورادی که برازش می‌تواند مقدار منفی دریافت کند عمل نمی کنند.

انتخاب مسابقه‌ای (تورنومنتی)
در انتخاب K-Way تورنومنتی ، تعداد k شخص را از بین جمعیت به شکل تصادفی انتخاب می‌کنیم و بهترین آن‌ها را به عنوان والد بر می گزینیم.پروسه ای مشابه برای انتخاب والد بعدی به همین صورت تکرار می شود.شیوه انتخاب به صورت تورنومنتی برای موقعیت هایی که برازش مقدار منفی دارد نیز مناسب است.

انتخاب رتبه ای (Rank Selection)

انتخاب رتبه ای(رتبه بندی) هم مثل انتخاب مسابقه‌ای با مقادیر برازش منفی کار می‌کند و اغلب هنگامی که در جمعیت مقادیر برازش ها به هم خیلی نزدیک هستند ( اغلب در پایان اجرای الگوریتم رخ می دهد) مورد استفاده است.در این شیوه هر شخص یک تکه مساوی از دایره را به اشتراک می گیرد.همانگونه که در شکل زیر نشان داده شده است .بنابراین مقدار برازش هر شخص در انتخاب او به عنوان والد مهم نیست و همه در انتخاب از احتمال یکسانی برخوردار هستنددر .این شیوه انتخاب فشاری برای انتخاب شخص واجد شرایط تر وجود ندارد و انتخاب والد در الگوریتم ژنتیک را در برخی موقعیت ها با ضعف مواجه می‌کند . در این روش مفهوم مقدار برازش در انتخاب والد حدف می شود.هر چند برای در شخص در جمعیت یک رتبه بر اساس مقدار برازش آن در نظر گرفته می شود.انتخاب والدین بسته به مقدار رتبه هر فرد می‌باشد نه مقدار برازش آن.فرد با مقدار رتبه بالاتر بر فرد با رتبه پایینتر ارجحیت داده می شود