Cruce y Mutaciones

El operador de cruce

Se denomina operador de cruce a la forma de calcular el genoma del nuevo individuo en función del genoma del padre y de la madre. El operador de cruce es fuertemente responsable de las propiedades del algoritmo genético, y determinará en gran medida la evolución de la población.

Existen gran cantidad de técnicas de cruce. Las técnicas básicas son:

• Cruce básico: se selecciona un punto al azar de la cadena. La parte anterior del punto es copiada del genoma del padre y la posterior del de la madre.
• Cruce multipunto: igual que el cruce básico, sólo que estableciendo más de un punto de cruce.
• Cruce segmentado: existe una probabilidad de que un cromosoma sea punto de un cruce. Conforme se va formando la nueva cadena del descendiente, para cada gen, se verifica si ahí se va producir un cruce.
• Cruce uniforme: para cada gen de la cadena del descendiente existe una probabilidad de que el gen pertenezca al padre, y otra de que pertenezca a la madre.
• Cruces para permutación: Existe una familia de cruces específicas para los problemas de permutación, siendo algunos de ellos:
• 
  
• Cruce de mapeamiento parcial: toma una subsecuencia del genoma del padre y procura preservar el orden absoluto de los fenotipos -es decir, orden y posición en el genoma- del resto del genoma lo más parecido posible de la madre. Aparece también en la bibliografía como PMX.
• Cruce de orden: toma una subsecuencia del genoma del padre y procura preservar el orden relativo de los fenotipos del resto del genoma lo más parecido posible de la madre. Lo podemos encontrar en la bibliografía como OX.
• Cruce de ciclo: Tomamos el primer gen del genoma del padre, poniéndolo en la primera posición del hijo, y el primer gen del genoma de la madre, poniéndolo dentro del genoma del hijo en la posición que ocupe en el genoma del padre. El fenotipo que está en la posición que ocupa el gen del genoma del padre igual al primer gen del genoma de la madre se va a colocar en la posición que ocupe en el genoma del padre, y así hasta rellenar el genoma del hijo. Este método también es conocido en la bibliografía como CX.

El operador de mutación

Se define mutación como una variación de las informaciones contenidas en el código genético -habitualmente, un cambio de un gen a otro producido por algún factor exterior al algoritmo genético-. En Biología se definen dos tipos de mutaciones: las generativas, que se heredan y las somáticas, que no se heredan. En los algoritmos genéticos sólo nos serán interesantes las mutaciones generativas. Mas, ¿por qué puede interesar que incorporemos este mecanismo aleatorio?

Algunas de las razones que pueden motivar a incorporar son:

• Desbloqueo del algoritmo. Si el algoritmo se bloqueó en un mínimo parcial, una mutación puede sacarlo al incorporar nuevos fenotipos de otras zonas del espacio.
• Acabar con poblaciones degeneradas. Puede ocurrir que, bien por haber un cuasi-mínimo, bien porque en pasos iniciales apareció un individuo demasiado bueno que acabó con la diversidad genética, la población tenga los mismos fenotipos.  Si se ha llegado a una población degenerada, es preciso que las mutaciones introduzcan nuevos genomas.


• Incrementar el número de saltos evolutivos. Los saltos evolutivos -aparición de un fenotipo especialmente valioso, o, dicho de otra forma, salida de un mínimo local- son muy poco probables en un genético puro para un problema genérico. La mutación permite explorar nuevos subespacios de soluciones, por lo que, si el subespacio es bueno en términos de adaptación, se producirá un salto evolutivo después de la mutación que se expanderá de forma exponencial por la población.
• Enriquecer la diversidad genética. Es un caso más suave que el de una población degenerada -por ejemplo, que la población tenga una diversidad genética pobre-, la mutación es un mecanismo de prevención de las poblaciones degeneradas.

Sin embargo, si la tasa de mutación es excesivamente alta tendremos la ya conocida deriva genética. Una estrategia muy empleada es una tasa de mutación alta al inicio del algoritmo, para aumentar la diversidad genética, y una tasa de mutación baja al final del algoritmo, para conseguir que converga.

Existen varias técnicas distintas de mutación. Algunas de éstas son:

• Mutación de bit: existe una única probabilidad de que se produzca una mutación de algún bit. De producirse, el algoritmo toma aleatoriamente un bit, y lo invierte.
• Mutación multibit: cada bit tiene una probabilidad de mutarse o no, que es calculada en cada pasada del operador de mutación multibit.
• Mutación de gen: igual que la mutación de bit, solamente que, en vez de cambiar un bit, cambia un gen completo. Puede sumar un valor aleatorio, un valor constante, o introducir un gen aleatorio nuevo.
• Mutación multigen: igual que la mutación de multibit, solamente que, en vez de cambiar un conjunto de bits, cambia un conjunto de genes. Puede sumar un valor aleatorio, un valor constante, o introducir un gen aleatorio nuevo.
• Mutación de intercambio: existe una probabilidad de que se produzca una mutación. De producirse, toma dos bits/genes aleatoriamente y los intercambia.
• Mutación de barajado: existe una probabilidad de que se produzca una mutación. De producirse, toma dos bits o dos genes aleatoriamente y baraja de forma aleatoria los bits -o genes, según hubieramos escogido- comprendidos entre los dos.

En nuestro algoritmo genético hemos implementado el operador de mutación utilizando la técnica de mutación multigen.