مکانیزم چرخ رولت در الگوریتم ژنتیک (عملگر انتخاب)

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

اولین مکانزیم انتخاب که با نام چرخ رولت (roulette wheel) شناخته می شود که محبوب ترین و پرکاربردترین  مکانیز انتخاب است. که در این مطلب قصد داریم آن را بررسی کنیم. این روش با نام Fitness proportionate selection یا انتخاب بر اساس میزان مناسب بودن تابع برازش کروموزوم نیز نامیده می شود.

کارکرد این الگوریتم چگونه است؟
همانطور که در شکل مشخص است در گام دوم الگوریتم ما هر کروموزوم رو با استفاده از تابع برازش ارزیابی کردیم (اطلاعات کامل در مورد تابع برازش رو میتونید در این مطلب بخونید).
منطق مکانیزم چرخ رولت: در مکانیزم چرخ رولت هر یک از کروموزوم ها بسته به میزان مناسب بودنشون (بر اساس تابع برازش) احتمال انتخاب شدن رو دارن. به عبارت دیگر هر چه یک کروموزوم بهتر باشه احتمال انتخاب شدنش برای تولید نسل بعدی بیشتر هستش و برعکس هر چه کروموزوم  بدتر باشه، احتمال انتخاب شدن اون برای تولید نسل بعدی کمتر هستش.

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

Probability (chromosomes C) = Fitness(chromosomes C) / Sum Fitness(All chromosomes)

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

فرمول بالا رو به صورت ریاضی به شکل زیر نمایش میدن

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