صفحه قبلی – صفحه بعدی

انتخاب والد

انتخاب والدین فرایند انتخاب پدر و مادر برای بلوغ و ترکیب مجدد جهت ایجاد فرزندان نسل بعدی است. عملیات انتخاب والدین برای میزان همگرایی GA بسیار مهم است زیرا والدین خوب فرزندان را به یک راه حل بهتر و متناسب تر هدایت می کنند.
با این حال، باید از گسترش یک راه حل بسیار مناسب در طی چند نسل جلوگیری شود، زیرا این امر باعث می شود که راه حل های نزدیک به یکدیگر در فضای راه حل افزایش یافته و منجر به از دست دادن تنوع در میان راه حلها شود. حفظ تنوع بالا در میان جمعیت راه حلها در الگوریتم GA بسیار مهم است. مجذوب یا متاثر شدن کل جمعیت توسط یک راه حل بسیار مناسب، به عنوان یک همگرایی زود هنگام شناخته می شود که یک وضعیت نامطلوب در GA است.

انتخاب به نسبت مقدار تابع تطابق

این انتخاب یکی از محبوب ترین روش های انتخاب والدین است. در این روش هر فرد یا راه حل می تواند به اندازه میزان تابع تناسب احتمال انتخاب به عنوان والد را داشته باشد. بنابراین راه حلهای مناسب تر شانس بیشتری برای جفتگیری و تکثیر ویژگی های خود به نسل بعدی دارند. بدین ترتیب چنین استراتژی انتخابی، یک فشار انتخاب را به راه حلهای مناسب تر در جمعیت اعمال می کند و در طول زمان موجب بهبود آنها می شود.
یک چرخ دایره ای را در نظر بگیرید که به n قاچ تقسیم شده و n تعداد افراد در جمعیت است. هر راه حل متناسب با ارزش تناسب خود یک بخش از دایره را  در اختیار می گیرد.

دو پیاده سازی برای این نوع انتخاب ممکن است:

انتخاب چرخ رولت

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

 

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

  • محاسبه S مجموع تناسب راه حل ها
  • ایجاد یک عدد تصادفی بین 0 و S
  • با شروع از بالای جمعیت، تا زمانی که مجموع جزئی P کوچکتر از P باشد مقدار تابع تناسب راه حل ها را به مجموع جزئی اضافه می کنیم.
  • راه حلی که برای آن مقدار P بیش تر از S شود انتخاب می شود.

نمونه گیری تصادفی عمومی

نمونه برداري تصادفي عمومی کاملا مشابه انتخاب چرخ رولت است با اين تفاوت که به جاي داشتن يک نقطه ثابت، همانگونه که در شکل زير نشان داده شده، از چند نقطه ثابت استفاده می کنیم. بنابراین، تمام والدین تنها در یک چرخه از چرخ انتخاب می شوند. با چنین تنظیماتی راه حل  های بسیار مناسب حداقل یکبار انتخاب می شوند.

SUS

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

انتخاب رقابتی

در انتخاب رقابتی K حالته، K راه حل را به طور تصادفی انتخاب و از میان آنها بهترین را به عنوان والد انتخاب کنیم. همین روند برای انتخاب والدین بعدی تکرار می شود. انتخاب تورنمنت بسیار محبوب است، زیرا می تواند با مقادیر تناسب منفی هم کار کند.

Tournament Selection

انتخاب بر اساس رتبه

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

Rank Selection

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

انتخاب تصادفی

در این استراتژی ما به طور تصادفی والدین را از جمعیت موجود انتخاب می کنیم. هیچ فشاری برای انتخاب راه حل های مناسب وجود ندارد و بنابراین معمولا از انجام این استراتژی اجتناب می شود.

صفحه قبلی – صفحه بعدی

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *