Mutación (algoritmo genético)

Operación genética utilizada para añadir diversidad poblacional

La mutación es un operador genético que se utiliza para mantener la diversidad genética de los cromosomas de una población de un algoritmo genético o, más generalmente, evolutivo (AE). Es análogo a la mutación biológica .

El ejemplo clásico de un operador de mutación de un algoritmo genético (AG) codificado en binario implica una probabilidad de que un bit arbitrario en una secuencia genética se invierta de su estado original. Un método común para implementar el operador de mutación implica generar una variable aleatoria para cada bit en una secuencia. Esta variable aleatoria indica si un bit en particular se invertirá o no. Este procedimiento de mutación, basado en la mutación puntual biológica , se denomina mutación puntual única. Otros tipos de operadores de mutación se utilizan comúnmente para representaciones distintas a las binarias, como codificaciones de punto flotante o representaciones para problemas combinatorios.

El propósito de la mutación en los EA es introducir diversidad en la población muestreada . Los operadores de mutación se utilizan en un intento de evitar mínimos locales al impedir 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 EA a evitar solo tomar a los más aptos de la población para generar la próxima generación, sino que seleccionan un conjunto aleatorio (o semialeatorio) con una ponderación hacia aquellos que son más aptos. ^[1]

Los siguientes requisitos se aplican a todos los operadores de mutación utilizados en un EA: ^{[2] [3]}

1. Cada punto en el espacio de búsqueda debe ser alcanzable por una o más mutaciones.
2. No debe haber preferencia por partes o direcciones en el espacio de búsqueda (sin deriva).
3. Las mutaciones pequeñas deberían ser más probables que las grandes.

Para diferentes tipos de genoma, son adecuados diferentes tipos de mutación. Algunas mutaciones son gaussianas, uniformes, en zigzag, desordenadas, de inserción, de inversión, de intercambio, etc. ^{[4] [5] [6]} Se puede encontrar una descripción general y más operadores que los que se presentan a continuación en el libro introductorio de Eiben y Smith ^[7] o en ^{[8] .}

Mutación de cadena de bits

La mutación de cadenas de bits se produce mediante cambios de bits en posiciones aleatorias.

Ejemplo:

La probabilidad de mutación de un bit es , donde es la longitud del vector binario. Por lo tanto, se alcanza una tasa de mutación de por mutación e individuo seleccionado para la mutación. ${\displaystyle {\frac {1}{l}}}$ ${\displaystyle l}$ ${\displaystyle 1}$

Mutación de números reales

Muchos EA, como la estrategia de evolución ^{[9] [10] o los} algoritmos genéticos de codificación real ^[11] [ ^{12] [8],} trabajan con números reales en lugar de cadenas de bits. Esto se debe a las buenas experiencias que se han realizado con este tipo de codificación. ^{[8] [13]}

El valor de un gen con valor real puede modificarse o redeterminarse. Una mutación que implemente esto último solo debería utilizarse en conjunción con las mutaciones que modifican el valor y, en ese caso, solo con una probabilidad comparativamente baja, ya que puede provocar grandes cambios.

En la práctica, las variables de decisión que se deben modificar del problema de optimización que se desea resolver suelen ser limitadas. Por ello, los valores de los genes asociados se limitan a un intervalo . Las mutaciones pueden tener en cuenta o no estas restricciones. En este último caso, se requiere un postratamiento adecuado, como se describe a continuación. ${\displaystyle [x_{\min },x_{\max }]}$

Mutación sin consideración de restricciones

Ejemplo de una variable aleatoria con distribución normal. Nótese que las proporciones dadas de los subrangos suman 99,8 % y no 100 % debido al redondeo.

Un número real se puede mutar utilizando una distribución normal agregando el valor aleatorio generado al valor anterior del gen, lo que da como resultado el valor mutado : ${\displaystyle x}$ ${\displaystyle {\mathcal {N}}(0,\sigma )}$ ${\displaystyle x'}$

${\displaystyle x'=x+{\mathcal {N}}(0,\sigma )}$

En el caso de genes con un rango restringido de valores, es una buena idea elegir el tamaño del paso de la mutación de modo que se ajuste razonablemente al rango del gen que se va a cambiar, por ejemplo: ${\displaystyle \sigma }$ ${\displaystyle [x_{\min },x_{\max }]}$

${\displaystyle \sigma ={\frac {x_{\text{max}}-x_{\text{min}}}{6}}}$

El tamaño del paso también se puede ajustar al rango de cambio permisible más pequeño en función del valor actual. Sin embargo, en cualquier caso, es probable que el nuevo valor del gen esté fuera del rango de valores permisibles. Un caso así debe considerarse una mutación letal, ya que la reparación obvia mediante el uso del respectivo límite violado como el nuevo valor del gen conduciría a una deriva. Esto se debe a que el valor límite se seleccionaría entonces con toda la probabilidad de los valores fuera del límite del rango de valores. ${\displaystyle x'}$

La estrategia de evolución funciona con números reales y mutaciones basadas en una distribución normal. Los tamaños de los pasos son parte del cromosoma y están sujetos a la evolución junto con las variables de decisión reales.

Mutación teniendo en cuenta restricciones

Una forma posible de cambiar el valor de un gen teniendo en cuenta su rango de valores es el cambio de parámetro relativo de mutación del algoritmo evolutivo GLEAM (General Learning Evolutionary Algorithm and Method), ^[14] en el que, al igual que con la mutación presentada anteriormente, es más probable que se produzcan cambios pequeños que grandes. ${\displaystyle [x_{\min },x_{\max }]}$

Distribución de probabilidades para k=10 subáreas del intervalo de cambio total. Cada subáreas cubre 1/k del ancho del intervalo de cambio total.

En primer lugar, se toma una decisión uniformemente distribuida sobre si el valor actual debe aumentarse o disminuirse y luego se determina el intervalo de cambio total correspondiente. Sin pérdida de generalidad , se supone un aumento para la explicación y el intervalo de cambio total es entonces . Se divide en subáreas de igual tamaño con el ancho , a partir de las cuales se forman subintervalos de cambio de diferente tamaño: ${\displaystyle x}$ ${\displaystyle [x,x_{\max }]}$ ${\displaystyle k}$ ${\displaystyle \delta }$ ${\displaystyle k}$

${\displaystyle i}$-ésimo intervalo de subcambio: con ${\displaystyle [x,x+\delta \cdot i]}$

${\displaystyle \delta ={\frac {(x_{\text{max}}-x)}{k}}}$y ${\displaystyle i=1,\dots ,k}$

A continuación, se selecciona uno de los intervalos de subcambio con una distribución uniforme y se extrae de él un número aleatorio, también con una distribución uniforme, como nuevo valor del gen. Las probabilidades sumadas resultantes de los intervalos de subcambio dan como resultado la distribución de probabilidad de las subáreas para el caso ejemplar de que se muestra en la figura adyacente. Esta no es una distribución normal como antes, pero esta distribución también favorece claramente los cambios pequeños sobre los grandes. ${\displaystyle k}$ ${\displaystyle x'}$ ${\displaystyle k}$ ${\displaystyle k=10}$

Esta mutación para valores mayores de , como 10, es menos adecuada para tareas en las que el valor óptimo se encuentra en uno de los límites del rango de valores. Esto se puede remediar reduciendo significativamente cuando un valor genético se acerca mucho a sus límites. ${\displaystyle k}$ ${\displaystyle k}$

Mutación de permutaciones

Las mutaciones de permutaciones están especialmente diseñadas para genomas que son en sí mismos permutaciones de un conjunto . Estas se utilizan a menudo para resolver tareas combinatorias. ^{[8] [15] [16]} En las dos mutaciones presentadas, partes del genoma están rotadas o invertidas.

Rotación hacia la derecha

La presentación del procedimiento ^[16] se ilustra con un ejemplo a la derecha:

Inversión

La presentación del procedimiento ^[15] se ilustra con un ejemplo a la derecha:

Variantes con preferencia por cambios más pequeños

La exigencia planteada al principio para las mutaciones, según la cual los cambios pequeños deberían ser más probables que los grandes, sólo se cumple de forma insuficiente con las dos mutaciones de permutación presentadas, ya que las longitudes de las listas parciales y el número de posiciones de desplazamiento se determinan de forma uniforme. Sin embargo, cuanto más largas sean la lista parcial y el desplazamiento, mayor será el cambio en el orden de los genes.

Esto se puede solucionar con las siguientes modificaciones. El índice final de las listas parciales se determina como la distancia al índice inicial : ${\displaystyle j}$ ${\displaystyle d}$ ${\displaystyle i}$

${\displaystyle j=(i+d){\bmod {\left|P_{0}\right|}}}$

donde se determina aleatoriamente según uno de los dos procedimientos para la mutación de números reales del intervalo y redondeado. ${\displaystyle d}$ ${\displaystyle \left[0,\left|P_{0}\right|-1\right]}$

Para la rotación , se determina de manera similar a la distancia , pero el valor está prohibido. ${\displaystyle k}$ ${\displaystyle d}$ ${\displaystyle 0}$

Para la inversión , tenga en cuenta que debe cumplirse, por lo que el valor debe excluirse. ${\displaystyle i\neq j}$ ${\displaystyle d}$ ${\displaystyle 0}$

Véase también

• Algoritmos evolutivos
• Algoritmos genéticos

Referencias

1. "XI. Crossover y mutación". Marek Obitko . Consultado el 7 de abril de 2011 .
2. Eiben, AE; Smith, JE (2015). "Operadores de variación (mutación y recombinación)". Introducción a la computación evolutiva. Serie de computación natural. Berlín, Heidelberg: Springer. págs. 31-32. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. Número de identificación del sujeto  20912932.
3. Bäck, Thomas; Fogel, David B.; Whitley, Darrell; Angeline, Peter J. (1999). "Operadores de mutación". En Bäck, Thomas; Fogel, David B.; Michalewicz, Zbigniew (eds.). Computación evolutiva. Vol. 1, Algoritmos y operadores básicos. Boca Racon: CRC Press. págs. 237–255. ISBN 0-585-30560-9.OCLC 45730387  .
4. Mirjalili, Seyedali (2019), Mirjalili, Seyedali (ed.), "Algoritmo genético", Algoritmos evolutivos y redes neuronales: teoría y aplicaciones , Estudios en inteligencia computacional, vol. 780, Cham: Springer International Publishing, págs. 43–55, doi :10.1007/978-3-319-93025-1_4, ISBN 978-3-319-93025-1, S2CID  242047607 , consultado el 26 de mayo de 2023
5. Harifi, Sasan; Mohamaddoust, Reza (1 de mayo de 2023). "Mutación en zigzag: un nuevo operador de mutación para mejorar el algoritmo genético". Herramientas y aplicaciones multimedia . doi :10.1007/s11042-023-15518-3. ISSN  1573-7721. S2CID  258446829.
6. Katoch, Sourabh; Chauhan, Sumit Singh; Kumar, Vijay (1 de febrero de 2021). "Una revisión sobre algoritmos genéticos: pasado, presente y futuro". Herramientas y aplicaciones multimedia . 80 (5): 8091–8126. doi :10.1007/s11042-020-10139-6. ISSN  1573-7721. PMC 7599983 . PMID  33162782. 
7. Eiben, AE; Smith, JE (2015). "Representación, mutación y recombinación". Introducción a la computación evolutiva. Serie de computación natural. Berlín, Heidelberg: Springer. págs. 49–78. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. Número de identificación del sujeto  20912932.
8. Michalewicz, Zbigniew (1992). Algoritmos genéticos + estructuras de datos = programas evolutivos. Inteligencia artificial. Berlín, Heidelberg: Springer Berlin Heidelberg. doi :10.1007/978-3-662-02830-8. ISBN 978-3-662-02832-2. Número de identificación del sujeto  33272042.
9. Rechenberg, Ingo (1973). Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (tesis doctoral) (en alemán). Frommann-Holzboog. ISBN 3-7728-0373-3.
10. Schwefel, Hans-Paul (1977). Numerische Optimierung von Computermodellen (tesis doctoral) (en alemán). Basilea: Birkhäuser Verlag. Traducción: Optimización numérica de modelos informáticos, Wiley, Chichester, 1981. ISBN 0-471-09988-0.OCLC 8011455  .
11. Wright, Alden H. (1991), Rawlins, Gregory JE (ed.), Algoritmos genéticos para optimización de parámetros reales, Fundamentos de algoritmos genéticos, vol. 1, Elsevier, págs. 205-218, doi :10.1016/b978-0-08-050684-5.50016-1, ISBN 9780080506845, consultado el 2 de enero de 2023
12. Eshelman, Larry J.; Schaffer, J. David (1993), "Algoritmos genéticos codificados de forma real y esquemas de intervalo", Fundamentos de algoritmos genéticos , vol. 2, Elsevier, págs. 187-202, doi :10.1016/b978-0-08-094832-4.50018-0, ISBN 978-0-08-094832-4, consultado el 1 de enero de 2023
13. Herrera, F.; Lozano, M.; Verdegay, JL (1998). "Abordando algoritmos genéticos con código real: operadores y herramientas para el análisis del comportamiento". Revisión de inteligencia artificial . 12 (4): 265–319. doi :10.1023/A:1006504901164. S2CID  6798965.
14. Blume, Christian; Jakob, Wilfried (2002), "GLEAM - Un algoritmo evolutivo para la planificación y el control basado en la estrategia evolutiva", Conf. Proc. of Genetic and Evolutionary Computation Conference (GECCO 2002) , vol. Late Breaking Papers, págs. 31–38 , consultado el 1 de enero de 2023
15. Eiben, AE; Smith, JE (2015). "Mutación para la representación de permutaciones". Introducción a la computación evolutiva. Serie de computación natural. Berlín, Heidelberg: Springer. págs. 69-70. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. Número de identificación del sujeto  20912932.
16. Yu, Xinjie; Gen, Mitsuo (2010). "Operadores de mutación". Introducción a los algoritmos evolutivos. Ingeniería de decisiones. Londres: Springer. págs. 286-288. doi :10.1007/978-1-84996-129-5. ISBN 978-1-84996-128-8.

Bibliografía

• John Holland (1975). Adaptación en sistemas naturales y artificiales , tesis doctoral, University of Michigan Press , Ann Arbor, Michigan. ISBN 0-262-58111-6 . 
• Schwefel, Hans-Paul (1995). Evolución y búsqueda del óptimo. Nueva York: John Wiley & Sons. ISBN 0-471-57148-2.
• Davis, Lawrence (1991). Manual de algoritmos genéticos . Nueva York: Van Nostrand Reinhold. ISBN 0-442-00173-8.OCLC 23081440  .
• Eiben, AE; Smith, JE (2015). Introducción a la computación evolutiva. Serie Natural Computing. Berlín, Heidelberg: Springer. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. Número de identificación del sujeto  20912932.
• Yu, Xinjie; Gen, Mitsuo (2010). Introducción a los algoritmos evolutivos. Ingeniería de decisiones. Londres: Springer. doi :10.1007/978-1-84996-129-5. ISBN 978-1-84996-128-8.
• De Jong, Kenneth A. (2006). Computación evolutiva: un enfoque unificado . Cambridge, Mass.: MIT Press. ISBN 978-0-262-25598-1.OCLC 69652176  .
• Fogel, David B.; Bäck, Thomas; Michalewicz, Zbigniew, eds. (1999). Computación evolutiva. Vol. 1, Algoritmos y operadores básicos. Bristol: Institute of Physics Pub. ISBN 0-585-30560-9.OCLC 45730387  .