XI. Cruce y mutacion

Introduccion

El cruce y la mutacion son los dos operadores basicos de un AG. El rendimiento de un AG depende en gran medida de ellos. El tipo y la implementacion de estos operadores dependen de la codificacion y del propio problema.

Hay muchas formas de realizar cruce y mutacion. Este capitulo ofrece solo algunos ejemplos y sugerencias para aplicarlos a varias codificaciones.

Codificacion binaria

Cruce

Cruce de un punto - se selecciona un punto de cruce. La cadena binaria desde el inicio del cromosoma hasta el punto de cruce se copia de un progenitor, y el resto se copia del segundo progenitor.

11001011+11011111 = 11001111

Cruce de dos puntos - se seleccionan dos puntos de cruce. La cadena binaria desde el inicio del cromosoma hasta el primer punto de cruce se copia de un progenitor, la parte desde el primer punto de cruce hasta el segundo se copia del segundo progenitor, y el resto se copia del primer progenitor.

11001011 + 11011111 = 11011111

Cruce uniforme - los bits se copian aleatoriamente del primer o del segundo progenitor.

11001011 + 11011101 = 11011111

Cruce aritmetico - se realiza alguna operacion aritmetica para crear nueva descendencia.

11001011 + 11011111 = 11001001 (AND)

Mutacion

Inversion de bits - los bits seleccionados se invierten.

11001001 =>  10001001

Codificacion de permutacion

Cruce

Cruce de un punto - se selecciona un punto de cruce. Hasta ese punto, la permutacion se copia del primer progenitor. Luego se recorre el segundo progenitor y se agrega cada numero que aun no este en la descendencia.
Nota: hay varias formas de producir el resto despues del punto de cruce.

(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)

Mutacion

Cambio de orden - se seleccionan dos numeros y se intercambian.

(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)

Codificacion de valores

Cruce

Pueden utilizarse todos los metodos de cruce de la codificacion binaria.

Mutacion

Suma de un numero pequeno (para codificacion con valores reales): se suma o se resta un numero pequeno a los valores seleccionados.

(1.29  5.68  2.86  4.11  5.55) => (1.29  5.68  2.73  4.22  5.55)

Codificacion en arbol

Cruce

Cruce en arbol - se selecciona un punto de cruce en cada progenitor. Los progenitores se dividen en ese punto e intercambian las partes que estan por debajo del punto de cruce para producir nueva descendencia.

Mutacion

Cambio de operador, numero - se modifican los nodos seleccionados.

·