Hispanopedia Wiki
Articulo de referencia

Operador genético

Un operador genético es un operador utilizado en algoritmos evolutivos (AE) para guiar al algoritmo hacia una solución a un problema dado. Existen tres tipos principales de oper...

Hispanopedia WikiContenido en espanolLectura gratuita

Un operador genético es un operador utilizado en algoritmos evolutivos (AE) para guiar al algoritmo hacia una solución a un problema dado. Existen tres tipos principales de operadores ( mutación , cruce y selección ), que deben funcionar conjuntamente para que el algoritmo tenga éxito. [ 1 ] Los operadores genéticos se utilizan para crear y mantener la diversidad genética (operador de mutación), combinar soluciones existentes (también conocidas como cromosomas ) en nuevas soluciones (cruce) y seleccionar entre soluciones (selección). [ 2 ] [ 3 ]

Los representantes clásicos de los algoritmos evolutivos incluyen algoritmos genéticos , estrategias evolutivas , programación genética y programación evolutiva . En su libro sobre el uso de la programación genética para la optimización de problemas complejos, el informático John Koza también identificó un operador de "inversión" o "permutación"; sin embargo, la efectividad de este operador nunca se ha demostrado de forma concluyente y rara vez se discute en el campo de la programación genética. [ 4 ] No obstante, para problemas combinatorios , estos y otros operadores adaptados a permutaciones son frecuentemente utilizados por otros EA. [ 5 ] [ 6 ]

Se dice que los operadores de mutación (o similares a la mutación) son operadores unarios , ya que solo operan sobre un cromosoma a la vez. En cambio, se dice que los operadores de cruce son operadores binarios , ya que operan sobre dos cromosomas a la vez, combinando dos cromosomas existentes en uno nuevo. [ 7 ] [ 8 ]

Operadores

La variación genética es necesaria para el proceso de evolución . Los operadores genéticos utilizados en los algoritmos evolutivos son análogos a los del mundo natural: la supervivencia del más apto o selección ; la reproducción ( cruce , también llamada recombinación); y la mutación .

Selección

Los operadores de selección dan preferencia a las mejores soluciones candidatas (cromosomas), permitiéndoles transmitir sus "genes" a la siguiente generación ( iteración ) del algoritmo. Las mejores soluciones se determinan mediante alguna función objetivo (también conocida como " función de aptitud " en algoritmos evolutivos), antes de ser pasadas al operador de cruce. Existen diferentes métodos para elegir las mejores soluciones, por ejemplo, la selección proporcional a la aptitud y la selección por torneo . [ 9 ] Se utiliza otro operador de selección, o el mismo, para determinar los individuos que serán seleccionados para formar la siguiente generación parental. El operador de selección también puede asegurar que la(s) mejor(es) solución(es) de la generación actual siempre se convierta(n) en miembro(s) de la siguiente generación sin ser alterada(s); [ 10 ] esto se conoce como elitismo o selección elitista . [ 2 ] [ 11 ] [ 12 ]

Crossover

El cruce es el proceso de tomar más de una solución parental (cromosomas) y producir una solución descendiente a partir de ellas. Al recombinar porciones de buenas soluciones, el algoritmo evolutivo tiene más probabilidades de crear una mejor solución. [ 2 ] Al igual que con la selección, existen varios métodos diferentes para combinar las soluciones parentales, incluyendo el operador de recombinación de aristas (ERO) y los métodos de cruce de "corte y empalme" y "cruce uniforme". El método de cruce se suele elegir para que coincida estrechamente con la representación de la solución en el cromosoma; esto puede ser particularmente importante cuando las variables se agrupan como bloques de construcción , lo que podría verse alterado por un operador de cruce inadecuado. De manera similar, los métodos de cruce pueden ser particularmente adecuados para ciertos problemas; el ERO se considera una buena opción para resolver el problema del viajante de comercio . [ 13 ]

Mutación

El operador de mutación fomenta la diversidad genética entre las soluciones e intenta evitar que el algoritmo evolutivo converja a un mínimo local, impidiendo que las soluciones se acerquen demasiado entre sí. Al mutar el conjunto actual de soluciones, una solución dada puede cambiar entre ligeramente y completamente con respecto a la solución anterior. [ 14 ] Al mutar las soluciones, un algoritmo evolutivo puede alcanzar una solución mejorada únicamente mediante el operador de mutación. [ 2 ] Nuevamente, se pueden utilizar diferentes métodos de mutación; estos van desde una mutación de bits simple (invertir bits aleatorios en un cromosoma de cadena binaria con una probabilidad baja) hasta métodos de mutación más complejos en los que se modifican genes en la solución, por ejemplo, agregando un valor aleatorio de la distribución gaussiana al valor genético actual. Al igual que con el operador de cruce, el método de mutación generalmente se elige para que coincida con la representación de la solución dentro del cromosoma. [ 14 ] [ 3 ]

Operadores combinados

Si bien cada operador actúa para mejorar las soluciones producidas por el algoritmo evolutivo trabajando individualmente, los operadores deben trabajar en conjunto para que el algoritmo tenga éxito en encontrar una buena solución. [ 3 ] El uso del operador de selección por sí solo tenderá a llenar la población de soluciones con copias de la mejor solución de la población. Si los operadores de selección y cruce se utilizan sin el operador de mutación, el algoritmo tenderá a converger a un mínimo local , es decir, una buena solución pero subóptima para el problema. El uso del operador de mutación por sí solo conduce a un paseo aleatorio por el espacio de búsqueda. Solo mediante el uso de los tres operadores en conjunto el algoritmo evolutivo puede convertirse en un algoritmo de búsqueda global tolerante al ruido, que produce buenas soluciones para el problema en cuestión. [ 2 ]

Referencias

  1. ↑ Jiang, Dazhi; Tian, ​​Zhihang; He, Zhihui; Tu, Geng; Huang, Ruixiang (1 de septiembre de 2021). "Un marco para el diseño automático de operadores genéticos basado en programación de expresión genética y evolución diferencial" . Natural Computing . 20 (3): 395– 411. doi : 10.1007/s11047-020-09830-2 . ISSN 1572-9796 . 
  2. 1 2 3 4 5 "Introducción a los algoritmos genéticos" . Archivado del original el 11 de agosto de 2015. Recuperado el 20 de agosto de 2015 .
  3. 1 2 3 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 . 
  4. ↑ Koza, John R. (1996). Programación genética : sobre la programación de computadoras mediante selección natural (6.ª ed.). Cambridge, Mass.: MIT Press. ISBN   0-262-11170-5.
  5. ↑ 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 (2.ª ed.). Berlín, Heidelberg: Springer. pp. 69–70 . doi : 10.1007/978-3-662-44874-8 . ISBN   978-3-662-44873-1.
  6. ↑ 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.
  7. ↑ "Operadores genéticos" . Archivado del original el 30 de diciembre de 2017. Consultado el 20 de agosto de 2015 .
  8. ↑ 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 (2.ª ed.). Berlín, Heidelberg: Springer. pp. 31–33 . doi : 10.1007/978-3-662-44874-8 . ISBN   978-3-662-44873-1.
  9. ↑ Eiben, AE; Smith, JE (2015). «Parent Selection». Introduction to Evolutionary Computing . Natural Computing Series (2.ª ed.). Berlín, Heidelberg: Springer. pp. 80–87 . doi : 10.1007/978-3-662-44874-8 . ISBN   978-3-662-44873-1.
  10. ↑ Eiben, AE; Smith, JE (2015). «Selección de supervivientes». Introducción a la computación evolutiva . Serie de computación natural (2.ª ed.). Berlín, Heidelberg: Springer. pp. 87–90 . doi : 10.1007/978-3-662-44874-8 . ISBN   978-3-662-44873-1.
  11. ↑ "Introducción al algoritmo genético" . Consultado el 20 de agosto de 2015 .
  12. ↑ Eiben, AE; Smith, JE (2015). Introducción a la computación evolutiva . Serie de computación natural (2.ª ed.). Berlín, Heidelberg: Springer. p. 89. doi : 10.1007/978-3-662-44874-8 . ISBN   978-3-662-44873-1.
  13. ↑ Whitley, Darrell; Starkweather, Timothy; Fuquay, D'Ann (1989), "Problemas de programación y viajante de comercio: el operador de recombinación de bordes genéticos", en Schaffer, JD (ed.), Actas de la 3.ª Conferencia Internacional sobre Algoritmos Genéticos (ICGA) , San Francisco: Morgan Kaufmann, pp. 133–140 , ISBN  1558600663
  14. 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​​