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

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

الگوریتم ژنتیک دارای سه گام می باشد:

گام اول جمعیت اولیه : جمعیت اولیه در واقع شامل تعدادی کروموزوم (همان جواب های احتمالی مسئله) می باشد. اطلاعات کامل در مورد جمعیت اولیه رو می تونید در این مطلب مطالعه کنید.

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

گام بعدی  و گام سوم بحث انتخاب کروموزوم است. برای این منظور ما ابتدا فرایند انتخاب را در محیط واقعی بررسی میکنیم.

با توجه به نظریه های حوزه ژنتیک (که ما زیاد بهشون کار نداریم) برای تولید نسل جدید از جمعیت فعلی ، باید کروموزوم هایی از این جمعیت را برای ادغام و تکثیر انتخاب کنیم که از بهینگی بیشتری برخوردارند (بهینگی هر کروموزوم با استفاده از تابع برازش محاسبه می شود). هر چه یک کروموزوم بهتر باشد شانس بیشتری برای انتخاب خواهند داشت.

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

قبل از ادامه بحث مسئله “انتخاب” در بین موجودات رو بررسی می کنیم. قصد داریم ببینیم منشائ این گام الگوریتم ژنتیک کجاست.

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

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

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

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

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

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

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

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

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

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

احتمال انتخاب کروموزوم i برابر است با نسبت تابع برازش کروموزوم i به مجموع تابع برازش همه کروموزوم ها.

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

Fitness_Function (Chromosome1) = 1
Fitness_Function (Chromosome2) = 4
Fitness_Function (Chromosome3) = 3
Fitness_Function (Chromosome4) = 2

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

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

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

خوب مجموعه مقادیر Fitness برای ۴ کروموزوم بالا میشه ۱+۴+۳+۲ = ۱۰
حالا باید احتمال هر کروموزوم رو حساب کنیم

Probability (chromosomes C1) = Fitness(chromosomes C1) / Sum Fitness(All chromosomes) = 1/10 = 0.1
Probability (chromosomes C2) = 4/10 = 0.4
Probability (chromosomes C3) = 3/10 = 0.3
Probability (chromosomes C4) = 2/10 = 0.2

گام آخر الگوریتم چرخ رولت این است که با توجه به محاسبات بالا کروموزوم ها را برای تولید نسل بعدی انتخاب کنیم. این کار به صورت زیر انجام می شود. با توجه به اینکه مجموعه احتمالات کروموزوم ها برابر ۱ است در نتیجه می آییم و احتمال انتخاب کروموزوم ها رو روی یک بردارد به اندازه یک نگاشت می دهیم این کار برای مثال بالا به صورت زیر انجام می شود.

• از انجایی احتمال انتخاب کروموزوم اول برابر ۰٫۱ است. در نتیجه بازه ۰ تا ۰٫۱ را به کروموزوم یک نسبت می دهیم.
• از انجایی احتمال انتخاب کروموزوم دوم برابر ۰٫۴ است. در نتیجه بازه ۰٫۱ تا ۰٫۵ را به کروموزوم یک نسبت می دهیم.
• از انجایی احتمال انتخاب کروموزوم سوم برابر ۰٫۳ است. در نتیجه بازه ۰٫۵ تا ۰٫۸ را به کروموزوم یک نسبت می دهیم.
• از انجایی احتمال انتخاب کروموزوم چهارم برابر ۰٫۲ است. در نتیجه بازه ۰٫۸ تا ۱ را به کروموزوم یک نسبت می دهیم.

خوب تا اینجا ما عمل نگاشت رو انجام دادیم. و در گام آخر ما میاییم و یک عدد تصادفی بین ۰ تا ۱ تولید میکنیم. این عدد در هر بازه ای قرار بگیرید یعنی آن کروموزوم انتخاب شده است. مثلا اگر عدد تصادفی ۰٫۲۵ باشد، چون بین ۰٫۱ تا ۰٫۵ است در نتیجه کروموزوم شماه دو انتخاب می شود. و یا مثلا اگر ۰٫۸۹ انتخاب شد چون بین ۰٫۸ تا ۱ است کروموزوم شماره ۴ انتخاب می شود.