عملگر جهش و جایگزینی

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

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

سیاست جایگزینی

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

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

الگوریتم ژنتیکی که از سیاست جایگزینی اول استفاده کند ، GGA و الگوریتم ژنتیکی که از روش دوم استفاده ند SSGA گوییم.