Hispanopedia Wiki
Articulo de referencia

Mutación (algoritmo evolutivo)

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 evolutivo (AE), incluidos los algoritm...

Hispanopedia WikiContenido en espanolLectura gratuita

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 evolutivo (AE), incluidos los algoritmos genéticos en particular. Es análoga a la mutación biológica .

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

El propósito de la mutación en los algoritmos evolutivos (AE) es introducir diversidad en la población muestreada . Los operadores de mutación se utilizan para intentar evitar mínimos locales , impidiendo que la población de cromosomas se vuelva demasiado similar entre sí, lo que ralentiza o incluso detiene la convergencia hacia el óptimo global. Este razonamiento también lleva a la mayoría de los AE a evitar seleccionar únicamente a los individuos más aptos de la población para generar la siguiente generación, y en su lugar 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 del espacio de búsqueda debe ser alcanzable mediante una o más mutaciones.
  2. No debe existir preferencia por ninguna pieza o dirección en el espacio de búsqueda (sin desviación).
  3. Las mutaciones pequeñas deberían ser más probables que las grandes.

Para distintos tipos de genoma, son adecuados distintos tipos de mutación. Algunas mutaciones son gaussiana, uniforme, en zigzag, aleatoria, por inserción, por inversión, por intercambio, etc. [ 4 ] [ 5 ] [ 6 ] Una descripción general y más operadores que los presentados a continuación se pueden encontrar en el libro introductorio de Eiben y Smith [ 7 ] o en [ 3 ] [ 8 ] .

Mutación de cadena de bits

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

Ejemplo:

La probabilidad de mutación de un bit es1l{\displaystyle {\frac {1}{l}}}, dóndel{\displaystyle l}es la longitud del vector binario. [ 9 ] Por lo tanto, una tasa de mutación de1{\displaystyle 1}por mutación y se alcanza el individuo seleccionado para la mutación.

Mutación de los números reales

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

El valor de un gen de valor real puede modificarse o redeterminarse. Una mutación que implique esto último solo debe utilizarse junto con mutaciones que alteren el valor y, aun así, con una probabilidad relativamente baja, ya que puede provocar grandes cambios.

En aplicaciones prácticas, el rango de valores respectivos de las variables de decisión que se deben cambiar en el problema de optimización que se va a resolver suele ser limitado. En consecuencia, los valores de los genes asociados se restringen a un intervalo.[incógnitamin,incógnitamáximo]{\displaystyle [x_{\min },x_{\max }]}Las mutaciones pueden o no tener en cuenta estas restricciones. En este último caso, se requiere un tratamiento posterior adecuado, como se describe a continuación.

Mutación sin tener en cuenta las 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 realincógnita{\displaystyle x}puede mutarse utilizando la distribución normalnorte(0,σ){\displaystyle {\mathcal {N}}(0,\sigma )}al sumar el valor aleatorio generado al valor antiguo del gen, se obtiene el valor mutado.incógnita′{\displaystyle x'}:

incógnita′=incógnita+norte(0,σ){\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.σ{\displaystyle \sigma }para que se ajuste razonablemente al rango[incógnitamin,incógnitamáximo]{\displaystyle [x_{\min },x_{\max }]}del gen que se va a modificar, por ejemplo:

σ=incógnitamáximo−incógnitamin6{\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 dependiendo del valor actual. En cualquier caso, sin embargo, es probable que el nuevo valorincógnita′{\displaystyle x'}El gen estará fuera del rango de valores permitidos. Este caso debe considerarse una mutación letal, ya que la reparación obvia mediante el uso del límite violado como nuevo valor del gen provocaría una deriva genética. Esto se debe a que el valor límite se seleccionaría entonces con la probabilidad total de que los valores se encuentren fuera del rango.

La estrategia evolutiva funciona con números reales y mutación basada en la distribución normal. Los tamaños de los pasos forman parte del cromosoma y están sujetos a evolución junto con las variables de decisión reales. [ 15 ] [ 16 ]

Mutación teniendo en cuenta las restricciones

Una posible forma de cambiar el valor de un gen mientras se toma su rango de valores[incógnitamin,incógnitamáximo]{\displaystyle [x_{\min },x_{\max }]}Se tiene en cuenta el cambio de parámetro relativo de mutación del algoritmo evolutivo GLEAM (General Learning Evolutionary Algorithm and Method), [ 17 ] en el que, como con la mutación presentada anteriormente, los cambios pequeños son más probables que los grandes.

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

Primero, se toma una decisión distribuida equitativamente sobre si el valor actualincógnita{\displaystyle x}debe aumentarse o disminuirse y luego se determina el intervalo de cambio total correspondiente. Sin pérdida de generalidad , se asume un aumento para la explicación y el intervalo de cambio total es entonces[incógnita,incógnitamáximo]{\displaystyle [x,x_{\max }]}Está dividido enk{\displaystyle k}subáreas de igual tamaño con el anchoδ{\displaystyle \delta }, de la cualk{\displaystyle k}Se forman intervalos de subcambio de diferente tamaño:

i{\displaystyle i}-intervalo de subcambio:[incógnita,incógnita+δ⋅i]{\displaystyle [x,x+\delta \cdot i]}con
δ=(incógnitamáximo−incógnita)k{\displaystyle \delta ={\frac {(x_{\text{max}}-x)}{k}}}yi=1,…,k{\displaystyle i=1,\dots ,k}

Posteriormente, uno de losk{\displaystyle k}Los intervalos de subcambio se seleccionan de manera uniforme y se extrae un número aleatorio, también distribuido de manera uniforme, como el nuevo valor.incógnita′{\displaystyle x'}del gen. Las probabilidades sumadas resultantes de los intervalos de subcambio dan como resultado la distribución de probabilidad de lak{\displaystyle k}subáreas que se muestran en la figura adyacente para el caso ejemplar dek=10{\displaystyle k=10}Esta no es una distribución normal como antes, pero esta distribución también favorece claramente los cambios pequeños sobre los grandes.

Esta mutación para valores mayores dek{\displaystyle k}, como por ejemplo 10, es menos adecuado para tareas donde el óptimo se encuentra en uno de los límites del rango de valores. Esto se puede remediar reduciendo significativamentek{\displaystyle k}cuando un valor genético se aproxima mucho a sus límites.

Propiedades comunes

Para ambos operadores de mutación aplicados a números reales, la probabilidad de aumento o disminución es independiente del valor actual y es del 50 % en ambos casos. Además, los cambios pequeños son considerablemente más probables que los grandes. En problemas de optimización con variables mixtas , se suele utilizar el redondeo.

Mutación de permutaciones

Las mutaciones de permutaciones están especialmente diseñadas para genomas que son, a su vez, permutaciones de un conjunto . Estas se utilizan a menudo para resolver tareas combinatorias. [ 8 ] [ 18 ] [ 19 ] En las dos mutaciones presentadas, partes del genoma se rotan o invierten.

Rotación hacia la derecha

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

Inversión

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

Variantes con preferencia por cambios más pequeños

El requisito planteado inicialmente para las mutaciones, según el cual los cambios pequeños deberían ser más probables que los grandes, no se cumple del todo con las dos mutaciones de permutación presentadas, ya que la longitud de las listas parciales y el número de posiciones de desplazamiento se determinan de forma equitativa. Sin embargo, cuanto más larga sea la lista parcial y el desplazamiento, mayor será el cambio en el orden de los genes.

Esto se puede remediar con las siguientes modificaciones. El índice finalj{\displaystyle j}de las listas parciales se determina como la distanciad{\displaystyle d}volver al índice de inicioi{\displaystyle i}:

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

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

Para la rotación ,k{\displaystyle k}se determina de manera similar a la distanciad{\displaystyle d}pero el valor0{\displaystyle 0}Está prohibido.

Para la inversión , tenga en cuenta quei≠j{\displaystyle i\neq j}debe sostenerse, así que parad{\displaystyle d}el valor0{\displaystyle 0}debe ser excluido.

Véase también

Referencias

  1. ↑ "XI. Cruce 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. pp. 31–32 . doi : 10.1007/978-3-662-44874-8 . ISBN  978-3-662-44873-1. S2CID 20912932 . 
  3. 1 2 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 Racón: CRC Press. pp. 237–255 . ISBN  0-585-30560-9OCLC 45730387​​ 
  4. ↑ Mirjalili, Seyedali (2019), "Algoritmo genético", en Mirjalili, Seyedali (ed.), Algoritmos evolutivos y redes neuronales: teoría y aplicaciones , Estudios en inteligencia computacional, vol. 780, Cham: Springer International Publishing, pp. 43–55 , doi : 10.1007/978-3-319-93025-1_4 , ISBN   978-3-319-93025-1, S2CID 242047607 , consultado el 26-05-2023 
  5. ↑ Harifi, Sasan; Mohamaddoust, Reza (2023-05-01). "Mutación en zigzag: un nuevo operador de mutación para mejorar el algoritmo genético" . Multimedia Tools and Applications . 82 (29): 45411– 45432. doi : 10.1007/s11042-023-15518-3 . ISSN 1573-7721 . S2CID 258446829 .  
  6. ↑ Katoch, Sourabh; Chauhan, Sumit Singh; Kumar, Vijay (2021-02-01). "Una revisión sobre algoritmos genéticos: pasado, presente y futuro" . Multimedia Tools and Applications . 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. S2CID 20912932 . 
  8. 1 2 3 4 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. S2CID 33272042 . 
  9. ↑ Eshelman, Larry J. (1999). «Mutación y cruce». En Bäck, Thomas; Fogel, David B.; Michalewicz, Zbigniew (eds.). Computación evolutiva. Vol. 1, Algoritmos y operadores básicos . Boca Racón: CRC Press. pág. 68. ISBN  0-585-30560-9OCLC 45730387​​ 
  10. ^ Rechenberg, Ingo (1973). Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (tesis doctoral) (en alemán). Frommann-Holzboog. ISBN 3-7728-0373-3.
  11. ^ 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-0OCLC 8011455​​ 
  12. ↑ Wright, Alden H. (1991), Rawlins, Gregory JE (ed.), Algoritmos genéticos para la optimización de parámetros reales , Fundamentos de algoritmos genéticos, vol. 1, Elsevier, pp. 205–218 , doi : 10.1016/b978-0-08-050684-5.50016-1 , ISBN   9780080506845, consultado el 2 de enero de 2023
  13. ↑ Eshelman, Larry J.; Schaffer, J. David (1993), "Algoritmos genéticos de codificación real y esquemas de intervalos", Fundamentos de algoritmos genéticos , vol. 2, Elsevier, pp. 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
  14. ↑ Herrera, F.; Lozano, M.; Verdegay, JL (1998). "Abordando los algoritmos genéticos de codificación real: operadores y herramientas para el análisis del comportamiento" . Artificial Intelligence Review . 12 (4): 265– 319. doi : 10.1023/A:1006504901164 . S2CID 6798965 . 
  15. ↑ Schwefel, Hans-Paul (1995). «Estrategias evolutivas para la optimización numérica». Evolución y búsqueda de óptimos . Serie de tecnología informática de sexta generación. Nueva York: Wiley. págs. 105–151 . ISBN  978-0-471-57148-3.
  16. ↑ Schwefel, Hans-Paul; Rudolph, Günter (1995), "Estrategias de evolución contemporáneas", en Morán, F.; Moreno, A.; Merelo, JJ; Chacón, P. (eds.), Actas de la Tercera Conferencia Europea sobre Vida Artificial (ECAL'95) , Berlín, Nueva York: Springer, pp. 893–907 , ISBN  978-3-540-59496-3
  17. ↑ Blume, Christian; Jakob, Wilfried (2002), "GLEAM - Un algoritmo evolutivo para planificación y control basado en estrategia evolutiva", Actas de la Conferencia de Computación Genética y Evolutiva (GECCO 2002) , vol. Artículos de última hora, págs. 31–38 , consultado el 1 de enero de 2023 .  
  18. 1 2 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. pp. 69–70 . doi : 10.1007/978-3-662-44874-8 . ISBN  978-3-662-44873-1. S2CID 20912932 . 
  19. 1 2 Yu, Xinjie; Gen, Mitsuo (2010). "Operadores de mutación". Introducción a los algoritmos evolutivos . Ingeniería de decisiones. Londres: Springer. pp. 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 óptima . 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-8OCLC 23081440​​ 
  • Eiben, AE; Smith, JE (2015). Introducción a la computación evolutiva . Serie de computación natural. Berlín, Heidelberg: Springer. doi : 10.1007/978-3-662-44874-8 . ISBN 978-3-662-44873-1. S2CID 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-1OCLC 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-9OCLC 45730387​​