عملگر ادغام

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

ادغام تک نقطه ای این روش نقطه ای از کرومزوم را به تصادف انتخاب کرده و سپس به روش زیر دو کروموزوم فرزند تولید می کند. نقطه انتخاب شده را pivot می نامیم:

ادغام دو نقطه ای

این روش دو نقطه متفاوت از کرومزوم را به تصادف انتخاب کرده و سپس به روش زیر دو کروموزوم فرزند تولید می کند. نقطه انتخاب شده را pivot1 و pivot2 می نامیم :

ادغام چند نقطه ای

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

ادغام با استفاده از ماسک

فرض کنید ماسکی به اندازه کروموزوم وجود دارد که مقادیر هر خانه از ماسک می تواند 1 یا 2 باشد. در این روش ابتدا ماسکی را به تصادف ایجاد کرده و سپس به روش زیر یک فرزند تولید می کنیم :

  • هر خانه از ماسک که مقدار 1 داشته باشد ، مقدار ژن کروموزوم فرزند در خانه متناظر با آن از پدر اول گرفته می شود
  • هر خانه از ماسک که مقدار 2 داشته باشد ، مقدار ژن کروموزوم فرزند در خانه متناظر با آن از پدر دوم گرفته می شود

ادغام با نگهداری اولویت

مراحل زیر نحوه اعمال این روش ادغام را نشان می دهد :

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

ادغام ترتیبی

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

  • فرزند 1 بخش های چپ و راست خود را از پدر 1 به ارث می برد.
  • بخش وسط فرزند 1 نیز از پدر 1 ارث برده خواهد شد. اما ترتیب ژن های بخش وسط که از پدر 1 به ارث می بریم ، با توجه به ترتیب آن ها در پدر 2 خواهد بود.
  • این عملیات را برای تولید فرزند2 و با استفاده از پدر 2 انجام می دهیم.