Mutación (algoritmo genético) - Mutation (genetic algorithm)
La mutación es un operador genético que se utiliza para mantener la diversidad genética de una generación de una población de cromosomas de algoritmo genético a la siguiente. Es análogo a la mutación biológica . La mutación altera uno o más valores de genes en un cromosoma desde su estado inicial. En la mutación, la solución puede cambiar completamente de la solución anterior. Por lo tanto, GA puede llegar a una mejor solución mediante la mutación. La mutación ocurre durante la evolución de acuerdo con una probabilidad de mutación definida por el usuario. Esta probabilidad debe establecerse baja. Si se establece demasiado alto, la búsqueda se convertirá en una búsqueda aleatoria primitiva.
El ejemplo clásico de un operador de mutación implica una probabilidad de que un bit arbitrario en una secuencia genética se voltee de su estado original. Un método común de implementar el operador de mutación implica generar una variable aleatoria para cada bit en una secuencia. Esta variable aleatoria indica si se invertirá o no un bit en particular. Este procedimiento de mutación, basado en la mutación puntual biológica , se denomina mutación puntual única. Otros tipos son la inversión y la mutación de punto flotante. Cuando la codificación del gen es restrictiva como en los problemas de permutación, las mutaciones son intercambios, inversiones y codificaciones.
El propósito de la mutación en GA es introducir diversidad en la población muestreada. Los operadores de mutación se utilizan en un intento de evitar los mínimos locales evitando que la población de cromosomas se vuelva demasiado similar entre sí, lo que ralentiza o incluso detiene la convergencia al óptimo global. Este razonamiento también lleva a la mayoría de los sistemas de GA a evitar tomar solo a los más aptos de la población para generar la próxima generación, sino seleccionar un conjunto aleatorio (o semialeatorio) con una ponderación hacia aquellos que están más en forma.
Para diferentes tipos de genomas, son adecuados diferentes tipos de mutación:
- Mutación de cadena de bits
- La mutación de las cadenas de bits se produce mediante cambios de bits en posiciones aleatorias.
- Ejemplo:
1 0 1 0 0 1 0 ↓ 1 0 1 0 1 1 0
- La probabilidad de una mutación de un bit es , donde es la longitud del vector binario. Por tanto, se alcanza una tasa de mutación de por mutación e individuo seleccionado para la mutación.
- Bit de volteo
Este operador de mutación toma el genoma elegido e invierte los bits (es decir, si el bit del genoma es 1, se cambia a 0 y viceversa).
- Perímetro
Este operador de mutación reemplaza el genoma con un límite superior o inferior al azar. Esto se puede utilizar para genes enteros y flotantes.
- No uniforme
La probabilidad de que la cantidad de mutación pase a 0 con la próxima generación aumenta mediante el uso de un operador de mutación no uniforme. Evita que la población se estanque en las primeras etapas de la evolución. Sintoniza la solución en etapas posteriores de la evolución. Este operador de mutación solo se puede utilizar para genes enteros y flotantes.
- Uniforme
Este operador reemplaza el valor del gen elegido con un valor aleatorio uniforme seleccionado entre los límites superior e inferior especificados por el usuario para ese gen. Este operador de mutación solo se puede utilizar para genes enteros y flotantes.
- Gaussiano
Este operador agrega una unidad de valor aleatorio distribuido de Gauss al gen elegido. Si cae fuera de los límites inferiores o superiores especificados por el usuario para ese gen, el nuevo valor del gen se recorta. Este operador de mutación solo se puede utilizar para genes enteros y flotantes.
- Encogerse
Este operador agrega un número aleatorio tomado de una distribución gaussiana con una media igual al valor original de cada variable de decisión que caracteriza al vector padre de entrada.
Ver también
Referencias
Bibliografía
- John Holland, Adaptación en sistemas naturales y artificiales, University of Michigan Press , Ann Arbor, Michigan. 1975. ISBN 0-262-58111-6 .