تقاطع (الگوریتم ژنتیک)

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

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

 برخی انواع استاندارد عملگر تقاطع 
الگوریتم‌های قدیمی ژنتیک اطلاعات ژنتیکی را به صورت یک کروموزوم درون آرایه بیتی ذخیره می‌کردند. روش‌های تقاطع مورد استفاده با آرایه‌های بیتی بسیار متداول اند و مثال‌های خوبی برای درک تقاطع هستند.

 تقاطع تک نقطه ای 
بندانگشتی
در این روش یک نقطه روی دو کروموزوم والد به صورت تصادفی انتخاب می‌شود و که نقطه تقاطع را نشان می‌دهد. بیت‌های سمت راست آن نقطه بین کروموزوم دو والد جابجا می‌شوند. به این صورت دو فرزند ایجاد می‌شوند که هرکدام بخشی از اطلاعات ژنتیکی هر کدام از دو والد خود را به همراه دارند.Poli, Riccardo, and William B. Langdon. "Genetic programming with one-point crossover." Soft Computing in Engineering Design and Manufacturing. Springer, London, 1998. 180-189.
import random

def single_point_crossover(parent_one, parent_two):
    string_length = len(parent_one)
    crossover_point = random.randint(0, string_length)

    child_one = parent_one[:crossover_point] + parent_two[crossover_point:]
    child_two = parent_two[:crossover_point] + parent_one[crossover_point:]

    return child_one, child_two

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

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

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

برای مثال یک الگوریتم ژنتیک که مسئله فروشنده دوره‌گرد را حل می‌کندAhmed, Zakir H. "Genetic algorithm for the traveling salesman problem using sequential constructive crossover operator." International Journal of Biometrics & Bioinformatics (IJBB) 3.6 (2010): 96. ممکن است از یک لیست مرتب شده از شهرها برای نشان دادن مسیر پاسخ استفاده کند. چنین کروموزومی تنها در صورتی می‌تواند معتبر باشد که لیست شامل همه شهرهایی که فروشنده دوره‌گرد باید از آنها عبور کند باشد. استفاده از روش‌های عملگر تقاطع که در بالا به آنها اشاره شد باعث ایجاد کروموزوم‌هایی می‌شود که محدودیت مورد نظر ما را نقض می‌کنند؛ بنابراین الگوریتم ژنتیکی که به این صورت به دنبال مرتب‌سازی لیست‌ها هستند به انواعی از تقاطع نیاز دارند که که مانع تولید پاسخ‌های نامعتبر شوند. بسیار از این نوع عملگرهای تقاطع منتشر شده‌اند:Pedro Larrañaga et al. , "Learning Bayesian Network Structures by searching for the best ordering with genetic algorithms", IEEE Transactions on systems, man and cybernetics, Vol 26, No. 4, 1996
 تقاطع نگاشته شده جزئی
 تقاطع دوری
 عملگر تقاطع منظم
 عملگر تقاطع مبتنی بر ترتیب
 عملگر تقاطع مبتنی بر جایگاه
 عملگر تقاطع نوترکیبی
 عملگر تقاطع جایگاه متناوب
 عملگر تقاطع ساخت متوالی

برای حل مشکل بالا می‌توان علاوه بر این انواع عملگر تقاطع از عملگر ترکیب دوباره یال‌ها یا کروموزوم دوگانه نیز استفاده کرد.Riazi, Amin (14 October 2019). "Genetic algorithm and a double-chromosome implementation to the traveling salesman problem". SN Applied Sciences. 1 (11)

 برخی از انواع دودویی عملگر تقاطعUmbarkar, A.J. and Sheth, P.D. , 2015. Crossover operators in genetic algorithms: a review. ICTACT journal on soft computing, 6(1). 
 تقاطع با ترتیب تصادفی 
ابتدا از روی دنباله دو والد یک بردار شباهت ساخته می‌شود. به این صورت که به ازای هر اندیس از دنباله کروموزومی والدها اگر مقدار آن عنصر دنباله در هر دو والد یکسال باشد، مقدار آن عنصر در بردار شباهت برابر مقدار مشترک والدها است و در غیر این صورت مقدار آن بیت پوچ است. سپس برای تولید فرزندان بردار شباهت عیناً رونوشت می‌شود اما در اندیس‌هایی که مقدار پوچ دارند با احتمال یکنواخت مقدار فرزند مشخص می‌شود.

 تقاطع پوششی 
در این روش یک بردار پوششی مشخص می‌کند که کدام بیت‌ها از کدام والد به فرزند منتقل شوند. در ابتدا فرزند اول و دوم رونوشتی از دو والد خود هستند. در ادامه فرزندان در اندیس‌هایی که مقدار آن در بردار پوششی ۱ است بین‌های خود را با یکدیگر جابجا می‌کنند. بردار پوششی می‌تواند به صورت تصادفی یا براساس شکل مسئله کلی‌ترین به روش‌های گوناگون ساخته شود.

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

تفاوت اصلی این روش با بقیه روش‌های مشابه در این است که جابجایی قسمت‌های مختلف رشته‌های والدها برای تولید فرزندان مستقل از یکدیگر صورت می‌گیرد.

 برای مطالعهٔ بیشتر 


 جستارهای وابسته 
 رایانش فرگشتی
 الگوریتم ژنتیک
 کروموزوم (الگوریتم ژنتیک)

 منابع 

رده:الگوریتم‌های ژنتیک