Crossover (algoritmo genético)

Operador utilizado para variar la programación de los cromosomas de una generación a la siguiente.

En algoritmos genéticos y computación evolutiva , el cruce , también llamado recombinación , es un operador genético utilizado para combinar la información genética de dos progenitores para generar nuevos descendientes. Es una forma de generar nuevas soluciones de manera estocástica a partir de una población existente, y es análogo al cruce que ocurre durante la reproducción sexual en biología . Las soluciones también se pueden generar clonando una solución existente, lo que es análogo a la reproducción asexual . Las soluciones recién generadas pueden mutarse antes de agregarse a la población.

Diferentes algoritmos en computación evolutiva 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 con el cruce son las matrices de bits , los vectores de números reales o los árboles .

La lista de operadores que se presenta a continuación no es completa y sirve principalmente como ilustración ejemplar de este tipo de operador genético diádico . Se pueden encontrar más operadores y más detalles en la literatura. ^{[1] [2] [3] [4] [5]}

Cruce para matrices binarias

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

Cruce de un punto

Se elige al azar un punto en los cromosomas de ambos padres y se lo designa como "punto de cruce". Los fragmentos a la derecha de ese punto se intercambian entre los dos cromosomas progenitores. Esto da como resultado dos descendientes, cada uno de los cuales porta información genética de ambos padres.

Cruce de dos puntos y de k puntos

En el cruce de dos puntos, se eligen al azar dos puntos de cruce de los cromosomas parentales. Los bits entre los dos puntos se intercambian entre los organismos parentales.

El cruce de dos puntos es equivalente a realizar dos cruces de un solo punto con diferentes puntos de cruce. Esta estrategia se puede generalizar al cruce de k puntos para cualquier entero positivo k, eligiendo k puntos de cruce.

Cruce uniforme

En un cruce uniforme, por lo general, cada bit se elige de cada progenitor con la misma probabilidad. ^[6] A veces se utilizan otras proporciones de mezcla, lo que da como resultado descendientes que heredan más información genética de un progenitor que del otro. En un cruce uniforme, no dividimos el cromosoma en segmentos, sino que tratamos cada gen por separado. En esto, básicamente lanzamos una moneda para cada cromosoma para decidir si se incluirá o no en la descendencia.

Cruce para genomas de valores enteros o reales

Ejemplo de recombinación discreta en el caso tridimensional. Los dos posibles descendientes se encuentran en los vértices del cuboide marcados en azul.

En el caso de los operadores de cruce presentados anteriormente y de la mayoría de los demás operadores de cruce para cadenas de bits, se cumple que también se pueden aplicar en consecuencia a genomas de valores enteros o reales cuyos genes consisten cada uno de ellos en un número entero o real. En lugar de bits individuales, simplemente se copian números enteros o reales en el genoma hijo. Los descendientes se encuentran en las esquinas restantes del hipercuerpo abarcado por los dos padres y , como se ejemplifica en la imagen adjunta para el caso tridimensional. ${\displaystyle P_{1}=(1.5,6,8)}$ ${\displaystyle P_{2}=(7,2,1)}$

Recombinación discreta

Si las reglas del cruce uniforme para cadenas de bits se aplican durante la generación de la descendencia, esto también se denomina recombinación discreta . ^[7]

Recombinación intermedia

En el caso bidimensional, los dos descendientes de la recombinación discreta se encuentran en las esquinas marcadas en azul, mientras que toda el área gris está en cuestión para los descendientes de la recombinación intermedia.

En este operador de recombinación, los valores de los alelos del genoma hijo se generan mezclando los alelos de los dos genomas parentales y : ^[7] ${\displaystyle a_{i}}$ ${\displaystyle a_{i,P_{1}}}$ ${\displaystyle a_{i,P_{2}}}$

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

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

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

Cruce para permutaciones

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

Para evitar la generación de descendientes no válidos, se han desarrollado operadores de cruce especiales para permutaciones ^[12] que cumplen los requisitos básicos de tales operadores para permutaciones, a saber, que todos los elementos de la permutación inicial también estén presentes en la nueva y solo se cambie el orden. Se puede distinguir entre tareas combinatorias, donde todas las secuencias son admisibles, y aquellas en las que hay restricciones en forma de secuencias parciales inadmisibles. Un representante bien conocido del primer tipo de tarea es el problema del viajante de comercio (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 un hilo hasta que se haya perforado el orificio correspondiente en una pieza de trabajo. Tales problemas también se denominan permutaciones basadas en el orden .

A continuación se presentan dos operadores de cruce como ejemplos: el cruce parcialmente mapeado (PMX) motivado por el TSP y el cruce de orden (OX1) diseñado para permutaciones basadas en orden. En cada caso, se puede producir una segunda descendencia intercambiando los cromosomas parentales.

Crossover parcialmente mapeado (PMX)

El operador PMX fue diseñado como un operador de recombinación para problemas tipo TSP. ^{[13] [14]} La explicación del procedimiento se ilustra con un ejemplo:

Orden de cruce (OX1)

El cruce de órdenes se remonta a Davis ^[1] en su forma original y se presenta aquí en una versión ligeramente generalizada con más de dos puntos de cruce. Transfiere información sobre el orden relativo del segundo progenitor a la descendencia. Primero, se determina aleatoriamente el número y la posición de los puntos de cruce. A continuación, las secuencias genéticas resultantes se procesan como se describe a continuación:

Entre otras cosas, el cruce de órdenes es muy adecuado para programar múltiples flujos de trabajo, cuando se utiliza junto con el cruce de 1 y n puntos. ^[15]

Otros operadores de cruce para permutaciones

A lo largo del tiempo se han propuesto una gran cantidad de operadores de cruce para permutaciones, por lo que la siguiente lista es solo una pequeña selección. Para obtener más información, se remite al lector a la literatura. ^{[1] [5] [14] [12]}

1. cruce de ciclos (CX) ^{[16] [14]}
2. cruce basado en órdenes (OX2) ^{[5] [17]}
3. cruce basado en posición (POS) ^{[5] [17]}
4. recombinación de bordes ^{[18] [14]}
5. recombinación de votación (VR) ^[12]
6. cruce de posiciones alternas (PA) ^[12]
7. cruce máximo de conservantes (MPX) ^{[5] [19]}
8. cruce de fusión (MX) ^{[5] [20]}
9. operador de cruce constructivo secuencial (SCX) ^[21]

El enfoque habitual para resolver problemas similares a TSP mediante algoritmos genéticos o, más generalmente, evolutivos, presentados anteriormente, consiste en reparar los descendientes ilegales o ajustar los operadores de manera apropiada para que no surjan descendientes ilegales en primer lugar. Como alternativa, Riazi sugiere el uso de una representación cromosómica doble, que evita la descendencia ilegal. ^[22]

Véase también

• Algoritmo evolutivo
• Representación genética
• Función de fitness
• Selección (algoritmo genético)

Bibliografía

• 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 del óptimo. 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-8.OCLC 23081440  .
• Eiben, AE; Smith, JE (2015). Introducción a la computación evolutiva. Serie Natural Computing. Berlín, Heidelberg: Springer. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. Número de identificación del sujeto  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-9.OCLC 45730387  .

Referencias

1. Davis, Lawrence (1991). Manual de algoritmos genéticos . Nueva York: Van Nostrand Reinhold. ISBN 0-442-00173-8.OCLC 23081440  .
2. Eiben, AE; Smith, JE (2015). "Representación, mutación y recombinación". Introducción a la computación evolutiva. Serie de computación natural (2.ª ed.). Berlín, Heidelberg: Springer. págs. 49–78. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. Número de identificación del sujeto  20912932.
3. Yu, Xinjie; Gen, Mitsuo (2010). "Codificación y operadores". Introducción a los algoritmos evolutivos. Ingeniería de decisiones. Londres: Springer. pp. 40–63. doi :10.1007/978-1-84996-129-5. ISBN 978-1-84996-129-5.OCLC 654380156  .
4. Yu, Xinjie; Gen, Mitsuo (2010). "Operadores de variación para códigos de permutación". Introducción a los algoritmos evolutivos. Ingeniería de decisiones. Londres: Springer. pp. 285–299. doi :10.1007/978-1-84996-129-5. ISBN 978-1-84996-128-8.
5. Booker, Lashon B.; Fogel, David B.; Whitley, Darrell; Angeline, Peter J.; Eiben, AE (2000). "Recombinación". En Bäck, Thomas; Fogel, David B.; Michalewicz, Zbigniew (eds.). Computación evolutiva. Vol. 1, Algoritmos y operadores básicos. Bristol: Institute of Physics Pub. págs. 256–307. ISBN 0-585-30560-9.OCLC 45730387  .
6. Syswerda, Gilbert (1989), Schaffer, JD (ed.), "Cruce uniforme en algoritmos genéticos", Actas de la 3.ª Conferencia internacional sobre algoritmos genéticos (ICGA) , San Francisco: Morgan Kaufmann, págs. 2-9, ISBN 1558600663
7. Eiben, AE; Smith, JE (2015). "Operadores de recombinación para la representación de valores reales". Introducción a la computación evolutiva. Serie de computación natural (2.ª ed.). Berlín, Heidelberg: Springer. págs. 65–67. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. Número de identificación del sujeto  20912932.
8. Mühlenbein, Heinz; Schlierkamp-Voosen, Dirk (1993). "Modelos predictivos para el algoritmo genético de criadores I. Optimización continua de parámetros". Computación evolutiva . 1 (1): 25–49. doi :10.1162/evco.1993.1.1.25. ISSN  1063-6560. S2CID  16085506.
9. Goldberg, David E. (1991). "Algoritmos genéticos de código real, alfabetos virtuales y bloqueo". Complex Syst . 5 (2): 139–167.
10. Stender, J.; Hillebrand, E.; Kingdon, J. (1994). Algoritmos genéticos en optimización, simulación y modelado . Ámsterdam: IOS Press. ISBN 90-5199-180-0.OCLC 47216370  .
11. Schwefel, Hans-Paul (1995). Evolución y búsqueda óptima. Nueva York: Wiley. ISBN 0-471-57148-2.OCLC 30701094  .
12. Larrañaga, P.; Kuijpers, CMH; Murga, RH; Inza, I.; Dizdarevic, S. (1999). "Algoritmos genéticos para el problema del viajante: una revisión de representaciones y operadores". Revisión de Inteligencia Artificial . 13 (2): 129–170. doi :10.1023/A:1006529012972. S2CID  10284682.
13. Goldberg, David E.; Lingle, R. (1985), Grefenstette, John J. (ed.), "Alelos, loci y el problema del viajante de comercio", Actas de la Primera Conferencia Internacional sobre Algoritmos Genéticos y sus Aplicaciones (ICGA) , Hillsdale, NJ: Lawrence Erlbaum Associates, págs. 154-159, ISBN 0-8058-0426-9, OCLC  19702892
14. Eiben, AE; Smith, JE (2015). "Recombinación para la representación de permutaciones". Introducción a la computación evolutiva. Serie de computación natural (2.ª ed.). Berlín, Heidelberg: Springer. págs. 70–74. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. Número de identificación del sujeto  20912932.
15. Jakob, Wilfried; Quinte, Alexander; Stucky, Karl-Uwe; Süß, Wolfgang (2008), Rudolph, Günter; Jansen, Thomas; Beume, Nicola; Lucas, Simon (eds.), "Programación rápida de tareas con múltiples objetivos para recursos restringidos utilizando un algoritmo evolutivo híbrido", Parallel Problem Solving from Nature – PPSN X , vol. LNCS 5199, Berlín, Heidelberg: Springer, págs. 1031–1040, doi :10.1007/978-3-540-87700-4_102, ISBN 978-3-540-87699-1, consultado el 14 de enero de 2023
16. Oliver, IM; Smith, DJ; Holland, J. (1987), Grefenstette, John J. (ed.), "Un estudio de operadores de cruce de permutación en el problema del viajante", Actas de la Segunda Conferencia Internacional sobre Algoritmos Genéticos y sus Aplicaciones (ICGA) , Hillsdale, NJ: Lawrence Erlbaum Associates, págs. 224-230, ISBN 978-0-8058-0158-3
17. Syswerda, Gilbert (1991). "Optimización de la programación mediante algoritmos genéticos". En Davis, Lawrence (ed.). Manual de algoritmos genéticos . Nueva York: Van Nostrand Reinhold. págs. 332–349. ISBN 0-442-00173-8.OCLC 23081440  .
18. Whitley, Darrell; Starkweather, Timothy; Fuquay, D'Ann (1989), Schaffer, JD (ed.), "Problemas de programación y vendedores ambulantes: el operador de recombinación de borde genético", Actas de la 3.ª Conferencia internacional sobre algoritmos genéticos (ICGA) , San Francisco: Morgan Kaufmann, págs. 133-140, ISBN 1558600663
19. Dzubera, John; Whitley, Darrell (1994), Davidor, Yuval; Schwefel, Hans-Paul; Männer, Reinhard (eds.), "Análisis de correlación avanzado de operadores para el problema del viajante de comercio", Parallel Problem Solving from Nature — PPSN III , vol. 866, Berlín, Heidelberg: Springer, pp. 68–77, doi :10.1007/3-540-58484-6_251, ISBN 978-3-540-58484-1, consultado el 15 de enero de 2023
20. Blanton, Joe L.; Wainwright, Roger L. (1993), Forrest, Stephanie (ed.), "Enrutamiento de múltiples vehículos con restricciones de tiempo y capacidad utilizando algoritmos genéticos", Actas de la 5.ª Conferencia internacional sobre algoritmos genéticos (ICGA) , San Francisco: Morgan Kaufmann, págs. 452-459, ISBN 978-1-55860-299-1
21. Ahmed, Zakir Hussain (2000). Muestreo constructivo secuencial y enfoques relacionados con la optimización combinatoria (PhD). Universidad de Tezpur, India.
22. Riazi, Amin (14 de octubre de 2019). "Algoritmo genético y una implementación de doble cromosoma para el problema del viajante de comercio". SN Applied Sciences . 1 (11). doi : 10.1007/s42452-019-1469-1 .

Enlaces externos

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