Crossover (algoritmo genético) - Crossover (genetic algorithm)
En los algoritmos genéticos y la computación evolutiva , el cruce , también llamado recombinación , es un operador genético que se utiliza para combinar la información genética de dos padres para generar una nueva descendencia. Es una forma de generar estocásticamente nuevas soluciones a partir de una población existente, y es análoga al cruce que ocurre durante la reproducción sexual en biología . Las soluciones también se pueden generar clonando una solución existente, que es análoga a la reproducción asexual . Las soluciones recién generadas generalmente se modifican antes de agregarse a la población.
Diferentes algoritmos en la computación evolutiva pueden usar diferentes estructuras de datos para almacenar información genética, y cada representación genética puede recombinarse con diferentes operadores cruzados. Las estructuras de datos típicas que se pueden recombinar con el cruce son matrices de bits , vectores de números reales o árboles .
Ejemplos de
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 .
Cruce de un punto
Un punto en los cromosomas de ambos padres se elige al azar y se designa como "punto de cruce". Los bits a la derecha de ese punto se intercambian entre los dos cromosomas principales. Esto da como resultado dos descendientes, cada uno con información genética de ambos padres.
Cruce de dos puntos y punto k
En el cruce de dos puntos, se seleccionan al azar dos puntos de cruce de los cromosomas parentales. Los bits entre los dos puntos se intercambian entre los organismos padres.
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 el cruce uniforme, por lo general, cada bit se elige de cualquiera de los padres con la misma probabilidad. A veces se utilizan otras proporciones de mezcla, lo que da como resultado una descendencia que hereda más información genética de uno de los padres que del otro.
Cruce para listas ordenadas
En algunos algoritmos genéticos, no todos los cromosomas posibles representan soluciones válidas. En algunos casos, es posible utilizar operadores de cambio y mutación especializados que están diseñados para evitar violar las limitaciones del problema.
Por ejemplo, un algoritmo genético que resuelve el problema del viajante de comercio puede usar una lista ordenada de ciudades para representar una ruta de solución. Tal cromosoma solo representa una solución válida si la lista contiene todas las ciudades que el vendedor debe visitar. El uso de los cruces anteriores a menudo dará como resultado cromosomas que violan esa restricción. Los algoritmos genéticos que optimizan el orden de una lista determinada requieren, por tanto, diferentes operadores cruzados que evitarán generar soluciones no válidas. Se han publicado muchos de estos cruces:
- crossover parcialmente mapeado (PMX)
- cruce de ciclo (CX)
- orden de operador cruzado (OX1)
- operador de cruce basado en pedidos (OX2)
- operador de cruce basado en la posición (POS)
- operador de cruce de recombinación de votación (VR)
- operador de cruce de posición alterna (AP)
- operador de cruce constructivo secuencial (SCX)
- operador de cruce binario simulado (SBX)
Otros métodos posibles incluyen el operador de recombinación de bordes . Alternativamente, para superar el problema mencionado, se pueden usar cromosomas dobles.
Ver también
- Computación evolutiva
- Algoritmo genético
- Cromosoma (algoritmo genético)
- Mutación (algoritmo genético)
- Aproximación de aptitud
- Función fitness
- Selección (algoritmo genético)
Referencias
- John Holland, Adaptación en sistemas naturales y artificiales , University of Michigan Press , Ann Arbor, Michigan. 1975. ISBN 0-262-58111-6 .
- Larry J. Eshelman, El algoritmo de búsqueda adaptativa de CHC: Cómo tener una búsqueda segura al participar en la recombinación genética no tradicional , en el editor de Gregory JE Rawlins, Actas del primer taller sobre fundamentos de algoritmos genéticos. páginas 265-283. Morgan Kaufmann, 1991. ISBN 1-55860-170-8 .
- Tomasz D. Gwiazda, Genetic Algorithms Reference Vol.1 Crossover para problemas de optimización numérica de un solo objetivo , Tomasz Gwiazda, Lomianki, 2006. ISBN 83-923958-3-2 .
enlaces externos
- Newsgroup: comp.ai.genetic FAQ - ver sección sobre crossover (también conocido como recombinación).