موضوع مقاله: تقاطع (الگوریتم ژنتیک) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تقاطع (الگوریتم ژنتیک) | مقدمه: با استفاده از تقاطع می‌توان از یک جمعیت موجود به صورت تصادفی و با ترکیب اطلاعات والدین فرزند ساخت، همانند آنچه هنگام تولید مثل جنسی رخ می‌دهد. | ## بخش 1: تقاطع (الگوریتم ژنتیک) | معمولاً پس از عملگر تقاطع فرزند به دست آمده دچار جهش می‌شود تا نتیجه نهایی حاصل شود. الگوریتم‌های گوناگون در رایانش فرگشتی از ساختارهای داده مختلفی برای ذخیره اطلاعات ژنتیکی استفاده می‌کنند، و در هر کدام از این نمایش‌های ژنتیکی می‌توان با استفاده از انواع گوناگون عملگر تقاطع ترکیب‌های جدید ساخت. به‌طور معمول از عملگر تقاطع روی داده ساختار‌های آرایه بیتی، بردارهای اعداد حقیقی و درخت‌ها استفاده می‌شود. برخی انواع استاندارد عملگر تقاطع الگوریتم‌های قدیمی ژنتیک اطلاعات ژنتیکی را به صورت یک کروموزوم درون آرایه بیتی ذخیره می‌کردند. روش‌های تقاطع مورد استفاده با آرایه‌های بیتی بسیار متداول اند و مثال‌های خوبی برای درک تقاطع هستند. تقاطع دو نقطه ای در واقع با اجرای دو تقاطع تک نقطه ای با نقاط تقاطع متفاوت معادل است. تقاطع یکنواخت در تقاطع یکنواخت، هر بیت با احتمال مساوی از یکی از والدها انتخاب می‌شود. | ## بخش 2: تقاطع (الگوریتم ژنتیک) | گاهی اوقات این احتمال مساوی نیست که باعث می‌شود اطلاعات بیشتری از والد با احتمال بیشتر، در فرزند به ارث برسد. تقاطع برای لیست‌های مرتب شده در برخی الگوریتم‌های ژنتیک همه کروموزم‌هایی که ممکن است پس از تقاطع به وجود آیند جواب‌های معتبری نیستند. در این حالات می‌توان از برخی عملگرهای تقاطع و جهش خاص استفاده کرد که طراحی شده‌اند تا از تولید جواب‌هایی که محدودیت‌های مورد نظر را رعایت نمی‌کنند جلوگیری کنند. چنین کروموزومی تنها در صورتی می‌تواند معتبر باشد که لیست شامل همه شهرهایی که فروشنده دوره‌گرد باید از آنها عبور کند باشد. استفاده از روش‌های عملگر تقاطع که در بالا به آنها اشاره شد باعث ایجاد کروموزوم‌هایی می‌شود که محدودیت مورد نظر ما را نقض می‌کنند؛ بنابراین الگوریتم ژنتیکی که به این صورت به دنبال مرتب‌سازی لیست‌ها هستند به انواعی از تقاطع نیاز دارند که که مانع تولید پاسخ‌های نامعتبر شوند. 4, 1996 تقاطع نگاشته شده جزئی تقاطع دوری عملگر تقاطع منظم عملگر تقاطع مبتنی بر ترتیب عملگر تقاطع مبتنی بر جایگاه عملگر تقاطع نوترکیبی عملگر تقاطع جایگاه متناوب عملگر تقاطع ساخت متوالی برای حل مشکل بالا می‌توان علاوه بر این انواع عملگر تقاطع از عملگر ترکیب دوباره یال‌ها یا کروموزوم دوگانه نیز استفاده کرد.Riazi, Amin (14 October 2019). به این صورت که به ازای هر اندیس از دنباله کروموزومی والدها اگر مقدار آن عنصر دنباله در هر دو والد یکسال باشد، مقدار آن عنصر در بردار شباهت برابر مقدار مشترک والدها است و در غیر این صورت مقدار آن بیت پوچ است. | ## بخش 3: تقاطع (الگوریتم ژنتیک) | سپس برای تولید فرزندان بردار شباهت عیناً رونوشت می‌شود اما در اندیس‌هایی که مقدار پوچ دارند با احتمال یکنواخت مقدار فرزند مشخص می‌شود. تقاطع پوششی در این روش یک بردار پوششی مشخص می‌کند که کدام بیت‌ها از کدام والد به فرزند منتقل شوند. در ادامه فرزندان در اندیس‌هایی که مقدار آن در بردار پوششی ۱ است بین‌های خود را با یکدیگر جابجا می‌کنند. بردار پوششی می‌تواند به صورت تصادفی یا براساس شکل مسئله کلی‌ترین به روش‌های گوناگون ساخته شود. تقاطع چند متغیره در این روش همه رشته والدها به تعدادی قسمت مساوی و متناظر تقسیم می‌شوند و هر قسمت با احتمال یکنواخت بین والدها جابجا می‌شود تا فرزندان تولید شوند. | ## جمع‌بندی | تفاوت اصلی این روش با بقیه روش‌های مشابه در این است که جابجایی قسمت‌های مختلف رشته‌های والدها برای تولید فرزندان مستقل از یکدیگر صورت می‌گیرد.