Algoritmos genéticos - Crossover
En este capítulo, analizaremos qué es un operador de cruce junto con sus otros módulos, sus usos y beneficios.
Introducción a Crossover
El operador de cruce es análogo a la reproducción y el cruce biológico. En este se selecciona más de un progenitor y uno o más descendientes se producen utilizando el material genético de los progenitores. El cruce generalmente se aplica en un GA con una alta probabilidad:pc .
Operadores cruzados
En esta sección analizaremos algunos de los operadores de cruce más utilizados. Cabe señalar que estos operadores cruzados son muy genéricos y el GA Designer podría optar por implementar también un operador cruzado específico del problema.
Cruce de un punto
En este cruce de un punto, se selecciona un punto de cruce aleatorio y las colas de sus dos padres se intercambian para obtener nuevos resortes.
Cruce multipunto
El cruce de múltiples puntos es una generalización del cruce de un punto en el que los segmentos alternos se intercambian para obtener nuevos resortes.
Cruce uniforme
En un cruce uniforme, no dividimos el cromosoma en segmentos, sino que tratamos cada gen por separado. En esto, básicamente lanzamos una moneda por cada cromosoma para decidir si se incluirá o no en la descendencia. También podemos sesgar la moneda a uno de los padres, para tener más material genético en el hijo de ese padre.
Recombinación aritmética completa
Esto se usa comúnmente para representaciones de números enteros y funciona tomando el promedio ponderado de los dos padres usando las siguientes fórmulas:
- Niño1 = α.x + (1-α) .y
- Niño2 = α.x + (1-α) .y
Obviamente, si α = 0.5, entonces ambos hijos serán idénticos como se muestra en la siguiente imagen.
Cruce de órdenes de Davis (OX1)
OX1 se utiliza para cruces basados en permutación con la intención de transmitir información sobre el orden relativo a los resortes. Funciona de la siguiente manera:
Cree dos puntos de cruce aleatorios en el padre y copie el segmento entre ellos desde el primer padre hasta la primera descendencia.
Ahora, a partir del segundo punto de cruce en el segundo padre, copie los números restantes no utilizados del segundo padre al primer hijo, ajustando la lista.
Repita para el segundo hijo con el papel de los padres invertido.
Existen muchos otros crossovers como Crossover parcialmente mapeado (PMX), Crossover basado en órdenes (OX2), Crossover aleatorio, Crossover de anillo, etc.