تقاطع (الگوریتم ژنتیک)
در الگوریتم‌های ژنتیک و رایانش فرگشتی، تقاطع (به انگلیسی: Crossover یا Recombination) نام یک عملگر ژنتیکی است که برای ترکیب اطلاعات ژنتیکی دو والد و ساختن فرزند آنها استفاده می‌شود. با استفاده از تقاطع می‌توان از یک جمعیت موجود به صورت تصادفی و با ترکیب اطلاعات والدین فرزند ساخت، همانند آنچه هنگام تولید مثل جنسی رخ می‌دهد. معمولاً پس از عملگر تقاطع فرزند به دست آمده دچار جهش می‌شود تا نتیجه نهایی حاصل شود.
الگوریتم‌های گوناگون در رایانش فرگشتی از ساختارهای داده مختلفی برای ذخیره اطلاعات ژنتیکی استفاده می‌کنند، و در هر کدام از این نمایش‌های ژنتیکی می‌توان با استفاده از انواع گوناگون عملگر تقاطع ترکیب‌های جدید ساخت. به‌طور معمول از عملگر تقاطع روی داده ساختار‌های آرایه بیتی، بردارهای اعداد حقیقی و درخت‌ها استفاده می‌شود.
الگوریتم‌های قدیمی ژنتیک اطلاعات ژنتیکی را به صورت یک کروموزوم درون آرایه بیتی ذخیره می‌کردند. روش‌های تقاطع مورد استفاده با آرایه‌های بیتی بسیار متداول اند و مثال‌های خوبی برای درک تقاطع هستند.
در این روش یک نقطه روی دو کروموزوم والد به صورت تصادفی انتخاب می‌شود و که نقطه تقاطع را نشان می‌دهد. بیت‌های سمت راست آن نقطه بین کروموزوم دو والد جابجا می‌شوند. به این صورت دو فرزند ایجاد می‌شوند که هرکدام بخشی از اطلاعات ژنتیکی هر کدام از دو والد خود را به همراه دارند.
import random
def single_point_crossover(parent_one, parent_two):
در روش تقاطع دو نقطه ای، دو نقطه به صورت تصادفی از کروموزوم‌ها والد انتخاب می‌شوند. بیت‌های بین بین دو نقطه بین دو والد جابجا می‌شوند و فرزندان تولید می‌شوند. تقاطع دو نقطه ای در واقع با اجرای دو تقاطع تک نقطه ای با نقاط تقاطع متفاوت معادل است. به همین صورت با تعمیم دادن همین ایده می‌توان تقاطع k نقطه ای را نیز انجام داد.
در تقاطع یکنواخت، هر بیت با احتمال مساوی از یکی از والدها انتخاب می‌شود. گاهی اوقات این احتمال مساوی نیست که باعث می‌شود اطلاعات بیشتری از والد با احتمال بیشتر، در فرزند به ارث برسد.
در برخی الگوریتم‌های ژنتیک همه کروموزم‌هایی که ممکن است پس از تقاطع به وجود آیند جواب‌های معتبری نیستند. در این حالات می‌توان از برخی عملگرهای تقاطع و جهش خاص استفاده کرد که طراحی شده‌اند تا از تولید جواب‌هایی که محدودیت‌های مورد نظر را رعایت نمی‌کنند جلوگیری کنند.
برای مثال یک الگوریتم ژنتیک که مسئله فروشنده دوره‌گرد را حل می‌کند ممکن است از یک لیست مرتب شده از شهرها برای نشان دادن مسیر پاسخ استفاده کند. چنین کروموزومی تنها در صورتی می‌تواند معتبر باشد که لیست شامل همه شهرهایی که فروشنده دوره‌گرد باید از آنها عبور کند باشد. استفاده از روش‌های عملگر تقاطع که در بالا به آنها اشاره شد باعث ایجاد کروموزوم‌هایی می‌شود که محدودیت مورد نظر ما را نقض می‌کنند؛ بنابراین الگوریتم ژنتیکی که به این صورت به دنبال مرتب‌سازی لیست‌ها هستند به انواعی از تقاطع نیاز دارند که که مانع تولید پاسخ‌های نامعتبر شوند. بسیار از این نوع عملگرهای تقاطع منتشر شده‌اند:
برای حل مشکل بالا می‌توان علاوه بر این انواع عملگر تقاطع از عملگر ترکیب دوباره یال‌ها یا کروموزوم دوگانه نیز استفاده کرد.
ابتدا از روی دنباله دو والد یک بردار شباهت ساخته می‌شود. به این صورت که به ازای هر اندیس از دنباله کروموزومی والدها اگر مقدار آن عنصر دنباله در هر دو والد یکسال باشد، مقدار آن عنصر در بردار شباهت برابر مقدار مشترک والدها است و در غیر این صورت مقدار آن بیت پوچ است. سپس برای تولید فرزندان بردار شباهت عیناً رونوشت می‌شود اما در اندیس‌هایی که مقدار پوچ دارند با احتمال یکنواخت مقدار فرزند مشخص می‌شود.
در این روش یک بردار پوششی مشخص می‌کند که کدام بیت‌ها از کدام والد به فرزند منتقل شوند. در ابتدا فرزند اول و دوم رونوشتی از دو والد خود هستند. در ادامه فرزندان در اندیس‌هایی که مقدار آن در بردار پوششی ۱ است بین‌های خود را با یکدیگر جابجا می‌کنند. بردار پوششی می‌تواند به صورت تصادفی یا براساس شکل مسئله کلی‌ترین به روش‌های گوناگون ساخته شود.
در این روش همه رشته والدها به تعدادی قسمت مساوی و متناظر تقسیم می‌شوند و هر قسمت با احتمال یکنواخت بین والدها جابجا می‌شود تا فرزندان تولید شوند.
تفاوت اصلی این روش با بقیه روش‌های مشابه در این است که جابجایی قسمت‌های مختلف رشته‌های والدها برای تولید فرزندان مستقل از یکدیگر صورت می‌گیرد.