تقاطع (الگوریتم ژنتیک)
در الگوریتم‌های ژنتیک و رایانش فرگشتی، تقاطع (به انگلیسی: Crossover یا Recombination) نام یک عملگر ژنتیکی است که برای ترکیب اطلاعات ژنتیکی دو والد و ساختن فرزند آنها استفاده می‌شود. با استفاده از تقاطع می‌توان از یک جمعیت موجود به صورت تصادفی و با ترکیب اطلاعات والدین فرزند ساخت، همانند آنچه هنگام تولید مثل جنسی رخ می‌دهد. معمولاً پس از عملگر تقاطع فرزند به دست آمده دچار جهش می‌شود تا نتیجه نهایی حاصل شود.
الگوریتم‌های گوناگون در رایانش فرگشتی از ساختارهای داده مختلفی برای ذخیره اطلاعات ژنتیکی استفاده می‌کنند، و در هر کدام از این نمایش‌های ژنتیکی می‌توان با استفاده از انواع گوناگون عملگر تقاطع ترکیب‌های جدید ساخت. به‌طور معمول از عملگر تقاطع روی داده ساختارهای آرایه بیتی، بردارهای اعداد حقیقی و درخت‌ها استفاده می‌شود.
برخی انواع استاندارد عملگر تقاطع ویرایش
الگوریتم‌های قدیمی ژنتیک اطلاعات ژنتیکی را به صورت یک کروموزوم درون آرایه بیتی ذخیره می‌کردند. روش‌های تقاطع مورد استفاده با آرایه‌های بیتی بسیار متداول اند و مثال‌های خوبی برای درک تقاطع هستند.
تقاطع تک نقطه ای ویرایش
در این روش یک نقطه روی دو کروموزوم والد به صورت تصادفی انتخاب می‌شود و که نقطه تقاطع را نشان می‌دهد. بیت‌های سمت راست آن نقطه بین کروموزوم دو والد جابجا می‌شوند. به این صورت دو فرزند ایجاد می‌شوند که هرکدام بخشی از اطلاعات ژنتیکی هر کدام از دو والد خود را به همراه دارند.[۱]
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 نقطه ای را نیز انجام داد.
تقاطع یکنواخت ویرایش
در تقاطع یکنواخت، هر بیت با احتمال مساوی از یکی از والدها انتخاب می‌شود. گاهی اوقات این احتمال مساوی نیست که باعث می‌شود اطلاعات بیشتری از والد با احتمال بیشتر، در فرزند به ارث برسد.
تقاطع برای لیست‌های مرتب شده ویرایش
در برخی الگوریتم‌های ژنتیک همه کروموزم‌هایی که ممکن است پس از تقاطع به وجود آیند جواب‌های معتبری نیستند. در این حالات می‌توان از برخی عملگرهای تقاطع و جهش خاص استفاده کرد که طراحی شده‌اند تا از تولید جواب‌هایی که محدودیت‌های مورد نظر را رعایت نمی‌کنند جلوگیری کنند.
برای مثال یک الگوریتم ژنتیک که مسئله فروشنده دوره‌گرد را حل می‌کند[۲] ممکن است از یک لیست مرتب شده از شهرها برای نشان دادن مسیر پاسخ استفاده کند. چنین کروموزومی تنها در صورتی می‌تواند معتبر باشد که لیست شامل همه شهرهایی که فروشنده دوره‌گرد باید از آنها عبور کند باشد. استفاده از روش‌های عملگر تقاطع که در بالا به آنها اشاره شد باعث ایجاد کروموزوم‌هایی می‌شود که محدودیت مورد نظر ما را نقض می‌کنند؛ بنابراین الگوریتم ژنتیکی که به این صورت به دنبال مرتب‌سازی لیست‌ها هستند به انواعی از تقاطع نیاز دارند که که مانع تولید پاسخ‌های نامعتبر شوند. بسیار از این نوع عملگرهای تقاطع منتشر شده‌اند:[۳]
- تقاطع نگاشته شده جزئی
- تقاطع دوری
- عملگر تقاطع منظم
- عملگر تقاطع مبتنی بر ترتیب
- عملگر تقاطع مبتنی بر جایگاه
- عملگر تقاطع نوترکیبی
- عملگر تقاطع جایگاه متناوب
- عملگر تقاطع ساخت متوالی
برای حل مشکل بالا می‌توان علاوه بر این انواع عملگر تقاطع از عملگر ترکیب دوباره یال‌ها یا کروموزوم دوگانه نیز استفاده کرد.[۴]
برخی از انواع دودویی عملگر تقاطع[۵] ویرایش
تقاطع با ترتیب تصادفی ویرایش
ابتدا از روی دنباله دو والد یک بردار شباهت ساخته می‌شود. به این صورت که به ازای هر اندیس از دنباله کروموزومی والدها اگر مقدار آن عنصر دنباله در هر دو والد یکسال باشد، مقدار آن عنصر در بردار شباهت برابر مقدار مشترک والدها است و در غیر این صورت مقدار آن بیت پوچ است. سپس برای تولید فرزندان بردار شباهت عیناً رونوشت می‌شود اما در اندیس‌هایی که مقدار پوچ دارند با احتمال یکنواخت مقدار فرزند مشخص می‌شود.
تقاطع پوششی ویرایش
در این روش یک بردار پوششی مشخص می‌کند که کدام بیت‌ها از کدام والد به فرزند منتقل شوند. در ابتدا فرزند اول و دوم رونوشتی از دو والد خود هستند. در ادامه فرزندان در اندیس‌هایی که مقدار آن در بردار پوششی ۱ است بین‌های خود را با یکدیگر جابجا می‌کنند. بردار پوششی می‌تواند به صورت تصادفی یا براساس شکل مسئله کلی‌ترین به روش‌های گوناگون ساخته شود.
تقاطع چند متغیره ویرایش
در این روش همه رشته والدها به تعدادی قسمت مساوی و متناظر تقسیم می‌شوند و هر قسمت با احتمال یکنواخت بین والدها جابجا می‌شود تا فرزندان تولید شوند.
تفاوت اصلی این روش با بقیه روش‌های مشابه در این است که جابجایی قسمت‌های مختلف رشته‌های والدها برای تولید فرزندان مستقل از یکدیگر صورت می‌گیرد.
برای مطالعهٔ بیشتر ویرایش
- [۱]Stuart J. Russell. Artificial Intelligence: A Modern Approach. Prentice Hall.
جستارهای وابسته ویرایش
منابع ویرایش
- ↑ Poli, Riccardo, and William B. Langdon. "Genetic programming with one-point crossover." Soft Computing in Engineering Design and Manufacturing. Springer, London, 1998. 180-189.
- ↑ 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).