Recombinación (computación evolutiva)

La recombinación (en inglés, crossover) es un operador genético utilizado en los algoritmos genéticos para generar variación en la programación de un cromosoma o cromosomas de una generación a la siguiente. Es análogo a la recombinación de la reproducción sexual biológica, en la que los algoritmos genéticos se inspiran.

Técnicas de recombinación

Existen muchas técnicas de recombinación para organismos que utilizan diferentes estructuras para almacenar los datos.

Recombinación en un punto

Se selecciona un punto en el vector del primer parental. Todos los datos más allá de este punto en el vector del organismo se intercambiarán entre los dos organismos parentales. Los organismos resultantes son los hijos:

Recombinación en dos puntos

La recombinación en dos puntos requiere seleccionar dos puntos en los vectores de los organismos parentales. Todos los datos entre los dos puntos se intercambian entre los organismos parentales, creando dos organismos hijos:

Corte y empalme

Otra variante de recombinación, el enfoque "cortar y empalmar", ocasiona un cambio de la longitud de los vectores de los hijos. la razón para esta diferencia es que se selecciona un punto de corte diferente para cada vector parental:

Recombinación uniforme y uniforme media

En ambos de estos esquemas los dos padres se combinan para producir los descendientes.

En el esquema de recombinación uniforme (UX por el inglés Uniform Crossover), los bits del vector se comparan individualmente entre ambos padres. Los bits se intercambian con una probabilidad fijada, usualmente 0.5.

En el esquema de recombinación uniforme media (HUX del inglés Half Uniform Crossover), exactamente la mitad de los bits que son diferentes se intercambian. Por esto se necesario calcular la distancia de Hamming (número de bits diferentes). Este número se divide entre dos, y el número resultante es la cantidad de bits diferentes que tiene que ser intercambiada entre los parentales.

Recombinación de cromosomas ordenados

Dependiendo de cómo representa la solución el cromosoma, un cambio directo puede no ser posible.

Un caso de ello se da cuando el cromosoma es una lista ordenada, como la lista ordenada de las ciudades visitadas en el problema del viajero. Un punto de recombinación se selecciona en los padres. Puesto que el cromosoma es una lista ordenada, un cambio directo introduciría duplicados y extraería candidatos necesarios de la lista. En cambio, el cromosoma hasta el punto de cruzamiento se retiene para cada padre. La información después del punto de cruzamiento se ordena como está ordenada en el otro padre. Por ejemplo, si nuestros dos padres son ABCDEFGHI e IGAHFDBEC y nuestro punto de cruzamiento se establece después del cuarto carácter, entonces los hijos que resultan serían ABCDIGHFE e IGAHBCDEF.

Otra variante del mismo procedimiento considera también el orden en el otro padre, pero empezando en el punto de cruzamiento. En el mismo ejemplo, los hijos que resultan serían ABCDFEIGH e IGAHEFBCD.

Tendencias de la recombinación

Para operadores de recombinación que intercambian secciones contiguas de los cromosomas (p. ej. k-point) la ordenación de las variables se puede tornar importante. Esto es especialmente cierto cuando las buenas soluciones contienen bloques de construcción que podrían ser interrumpidas por un operador de recombinación no respetuoso (no complementario).

Véase también

Datos: Q628906