Cruce (algoritmo evolutivo)

El cruce genético en algoritmos y computación evolutiva , también llamado recombinación , es un operador genético que se utiliza para combinar la información genética de dos progenitores y generar nueva descendencia. Es una forma de generar estocásticamente nuevas soluciones a partir de una población existente y es análogo al cruce genético que ocurre durante la reproducción sexual en biología . También se pueden generar nuevas soluciones clonando una solución existente, lo cual es análogo a la reproducción asexual . Las soluciones recién generadas pueden mutar antes de incorporarse a la población. El objetivo de la recombinación es transferir características deseables de dos progenitores diferentes a un solo descendiente.

En la computación evolutiva, los distintos algoritmos pueden utilizar diferentes estructuras de datos para almacenar información genética, y cada representación genética puede recombinarse con diferentes operadores de cruce. Las estructuras de datos típicas que pueden recombinarse mediante cruce son matrices de bits , vectores de números reales o árboles .

La lista de operadores que se presenta a continuación no es exhaustiva y sirve principalmente como ejemplo ilustrativo de este tipo de operador genético diádico . En la bibliografía se pueden encontrar más operadores y detalles. ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ]}

Los algoritmos genéticos tradicionales almacenan información genética en un cromosoma representado por una matriz de bits . Los métodos de cruce para matrices de bits son populares y constituyen un ejemplo ilustrativo de recombinación genética .

Para los operadores de cruce presentados anteriormente y para la mayoría de los demás operadores de cruce para cadenas de bits, se cumple que también pueden aplicarse de forma similar a genomas enteros o reales cuyos genes consisten cada uno en un número entero o real. En lugar de bits individuales, los números enteros o reales se copian simplemente en el genoma hijo. La descendencia se sitúa en las esquinas restantes del hipercuerpo formado por los dos progenitores.${\ Displaystyle P_ {1} = (1,5,6,8)}$y${\displaystyle P_{2}=(7,2,1)}$, como se ejemplifica en la imagen adjunta para el caso tridimensional.

Recombinación intermedia

En este operador de recombinación, los valores alélicos del genoma del niño${\displaystyle a_{i}}$se generan mezclando los alelos de los dos genomas parentales.${\displaystyle a_{i,P_{1}}}$y${\displaystyle a_{i,P_{2}}}$: ^{[ 7 ] [ 8 ]}

${\displaystyle \alpha _{i}=\alpha _{i,P_{1}}\cdot \beta _{i}+\alpha _{i,P_{2}}\cdot \left(1-\beta _{i}\right)\quad {\mathsf {con}}\quad \beta _{i}\in \left[-d,1+d\right]}$distribuidos aleatoriamente de manera igual por gen${\displaystyle i}$

La elección del intervalo${\displaystyle [-d,1+d]}$causas que además del interior del hipercuerpo abarcado por los valores alélicos de los genes parentales, también está en cuestión un cierto entorno para el rango de valores de la descendencia. Un valor de${\displaystyle 0.25}$Se recomienda para${\displaystyle d}$para contrarrestar la tendencia a reducir los valores alélicos que de otro modo existen en${\displaystyle d=0}$. ^{[ 9 ]}

La figura adjunta muestra, para el caso bidimensional, el rango de posibles nuevos alelos de los dos progenitores ejemplares.${\displaystyle P_{1}=(3,6)}$y${\displaystyle P_{2}=(9,2)}$en la recombinación intermedia. La descendencia de la recombinación discreta.${\displaystyle C_{1}}$y${\displaystyle C_{2}}$También se grafican. La recombinación intermedia satisface el cálculo aritmético de los valores alélicos del genoma hijo requerido por la teoría del alfabeto virtual. ^{[ 10 ] [ 11 ]} La recombinación discreta e intermedia se utiliza como estándar en la estrategia evolutiva . ^{[ 12 ]}

Para tareas combinatorias , se suelen utilizar permutaciones diseñadas específicamente para genomas que son a su vez permutaciones de un conjunto . El conjunto subyacente suele ser un subconjunto de${\displaystyle \mathbb {N} }$o${\displaystyle \mathbb {N} _ {0}}$Si se utiliza el cruce de 1 o n puntos, o el cruce uniforme para genomas enteros, un genoma hijo puede contener algunos valores duplicados y otros pueden estar ausentes. Esto se puede remediar mediante reparación genética , por ejemplo, reemplazando los genes redundantes con fidelidad posicional por los genes ausentes del otro genoma hijo.

Para evitar la generación de descendencia inválida, se han desarrollado operadores de cruce especiales para permutaciones ^{[ 13 ]} que cumplen con los requisitos básicos de dichos operadores, a saber, que todos los elementos de la permutación inicial también estén presentes en la nueva y que solo cambie el orden. Se puede distinguir entre tareas combinatorias, donde todas las secuencias son admisibles, y aquellas donde existen restricciones en forma de secuencias parciales inadmisibles. Un ejemplo bien conocido del primer tipo de tarea es el problema del viajante (TSP), donde el objetivo es visitar un conjunto de ciudades exactamente una vez en el recorrido más corto. Un ejemplo del tipo de tarea restringida es la programación de múltiples flujos de trabajo . Los flujos de trabajo implican restricciones de secuencia en algunos de los pasos de trabajo individuales. Por ejemplo, no se puede cortar una rosca hasta que se haya perforado el orificio correspondiente en una pieza de trabajo. Estos problemas también se denominan permutaciones restringidas . ^{[ 14 ]}

A continuación, se presentan dos operadores de cruce como ejemplos: el cruce parcialmente mapeado (PMX), inspirado en el problema del viajante, y el cruce ordenado (OX1), diseñado para permutaciones basadas en el orden. En ambos casos, se puede generar un segundo descendiente intercambiando los cromosomas parentales.

• Algoritmo evolutivo
• Representación genética
• Función de aptitud física
• Selección (algoritmo genético)

• John Holland (1975). Adaptación en sistemas naturales y artificiales , tesis doctoral, University of Michigan Press , Ann Arbor, Michigan. ISBN 0-262-58111-6.
• Schwefel, Hans-Paul (1995). Evolución y búsqueda óptima . Nueva York: John Wiley & Sons. ISBN 0-471-57148-2.
• Davis, Lawrence (1991). Manual de algoritmos genéticos . Nueva York: Van Nostrand Reinhold. ISBN 0-442-00173-8OCLC 23081440​​ 
• Eiben, AE; Smith, JE (2015). Introducción a la computación evolutiva . Serie de computación natural. Berlín, Heidelberg: Springer. doi : 10.1007/978-3-662-44874-8 . ISBN 978-3-662-44873-1. S2CID 20912932 . 
• Yu, Xinjie; Gen, Mitsuo (2010). Introducción a los algoritmos evolutivos . Ingeniería de decisiones. Londres: Springer. doi : 10.1007/978-1-84996-129-5 . ISBN 978-1-84996-128-8.
• Bäck, Thomas; Fogel, David B.; Michalewicz, Zbigniew, eds. (1999). Computación evolutiva. Vol. 1, Algoritmos y operadores básicos . Bristol: Institute of Physics Pub. ISBN 0-585-30560-9OCLC 45730387​​ 

• Grupo de noticias: Preguntas frecuentes de comp.ai.genetic - consulte la sección sobre entrecruzamiento (también conocido como recombinación).