عملگر انتخاب

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

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

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

  • انتخاب تصادفی
  • انتخاب رقابتی
  • انتخاب مبتنی بر چرخ رولت

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

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

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

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

انتخاب مبتنی بر چرخ

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

احتمال نسبی

تابع توزیع احتمال نسبی بر اساس میزان بهینگی هر کروموزوم و با توجه به مجموع بهینگی همه کروموزوم ها ، احتمالی را به هریک از آن ها سبت می دهد :

Prof(chi) =Fitness(chi) / Sumof(Fitness(ch))

احتمال رتبه ای

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

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

احتمال نسبی ( توزیع یکنواخت )

احتمال رتبه ای

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

روش چرخ رولت

در این روش پس از آنکه احتمال انتخاب کرموزوم ها تعیین گردید، یک عدد تصادفی بین 0 و 1 تولید می شود. سپس کرموزوم ها ( که به شکل صعودی مرتب شده اند ) از اول بررسی شده و اولین کروموزوم که توزیع تجمعی آن بیشتر یا مساوی عدد تولید شده باشد، انتخاب می گردد.

روش بولتزمن

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

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