Un operador genético es un operador utilizado en algoritmos genéticos para guiar el algoritmo hacia una solución a un problema dado. Hay tres tipos principales de operadores ( mutación , cruce y selección ), que deben trabajar en conjunto entre sí para que el algoritmo tenga éxito. 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). [1] En su libro que analiza el uso de la programación genética para la optimización de problemas complejos, el científico informático John Koza también ha identificado un operador de "inversión" o "permutación"; sin embargo, la eficacia de este operador nunca se ha demostrado de manera concluyente y rara vez se habla de él. [2] [3]
Se dice que los operadores de mutación (o similares a mutaciones) son operadores unarios , ya que solo operan en un cromosoma a la vez. Por el contrario, se dice que los operadores de cruce son operadores binarios , ya que operan en dos cromosomas a la vez, combinando dos cromosomas existentes en un cromosoma nuevo. [4]
La variación genética es una necesidad para el proceso de evolución . Los operadores genéticos utilizados en los algoritmos genéticos son análogos a los del mundo natural: supervivencia del más apto o selección ; reproducción ( cruzamiento , también llamado recombinación); y mutación .
Los operadores de selección dan preferencia a las mejores soluciones (cromosomas), lo que les permite pasar sus "genes" a la siguiente generación del algoritmo. Las mejores soluciones se determinan utilizando algún tipo de función objetivo (también conocida como " función de aptitud " en algoritmos genéticos), antes de pasarlas 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 ; diferentes métodos pueden elegir diferentes soluciones como "mejores". El operador de selección también puede simplemente pasar las mejores soluciones de la generación actual directamente a la siguiente generación sin ser mutadas; esto se conoce como elitismo o selección elitista . [1] [5]
El cruce es el proceso de tomar más de una solución original (cromosomas) y producir una solución hija a partir de ellas. Al recombinar porciones de buenas soluciones, es más probable que el algoritmo genético cree una mejor solución. [1] Al igual que con la selección, existen varios métodos diferentes para combinar las soluciones originales, incluido el operador de recombinación de bordes (ERO) y los métodos de "cruce de corte y empalme" y "cruce uniforme". El método de cruce se elige a menudo para que coincida estrechamente con la representación de la solución del cromosoma; esto puede volverse particularmente importante cuando las variables se agrupan como bloques de construcción , lo que podría verse alterado por un operador de cruce no respetuoso. De manera similar, los métodos de cruce pueden ser particularmente adecuados para ciertos problemas; el ERO generalmente se considera una buena opción para resolver el problema del viajante de comercio . [6]
El operador de mutación fomenta la diversidad genética entre las soluciones e intenta evitar que el algoritmo genético converja a un mínimo local al impedir que las soluciones se acerquen demasiado entre sí. Al mutar el conjunto actual de soluciones, una solución dada puede cambiar por completo con respecto a la solución anterior. Al mutar las soluciones, un algoritmo genético puede alcanzar una solución mejorada únicamente mediante el operador de mutación. [1] Nuevamente, se pueden usar diferentes métodos de mutación; estos van desde una simple mutación de bits (invertir bits aleatorios en un cromosoma de cadena binaria con cierta probabilidad baja) hasta métodos de mutación más complejos, que pueden reemplazar genes en la solución con valores aleatorios elegidos de la distribución uniforme o la distribución gaussiana . 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.
Si bien cada operador actúa para mejorar las soluciones producidas por el algoritmo genético trabajando individualmente, los operadores deben trabajar en conjunto entre sí para que el algoritmo tenga éxito en encontrar una buena solución. 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 pero subóptima solución para el problema. El uso del operador de mutación por sí solo conduce a un paseo aleatorio a través del espacio de búsqueda. Solo utilizando los tres operadores juntos puede el algoritmo genético convertirse en un algoritmo de escalada de colinas tolerante al ruido, produciendo buenas soluciones para el problema. [1]
{{cite book}}: CS1 maint: nombres múltiples: lista de autores ( enlace ) CS1 maint: nombres numéricos: lista de autores ( enlace )