En informática e investigación de operaciones , un algoritmo genético ( GA ) es una metaheurística inspirada en el proceso de selección natural que pertenece a la clase más amplia de algoritmos evolutivos (EA). Los algoritmos genéticos se utilizan comúnmente para generar soluciones de alta calidad a problemas de optimización y búsqueda basándose en operadores de inspiración biológica como mutación , cruce y selección . [1] Algunos ejemplos de aplicaciones GA incluyen la optimización de árboles de decisión para un mejor rendimiento, la resolución de sudokus , [2] optimización de hiperparámetros , inferencia causal , [3] , etc.
En un algoritmo genético, una población de soluciones candidatas (llamadas individuos, criaturas, organismos o fenotipos ) a un problema de optimización evoluciona hacia mejores soluciones. Cada solución candidata tiene un conjunto de propiedades (sus cromosomas o genotipo ) que pueden mutarse y alterarse; Tradicionalmente, las soluciones se representan en binario como cadenas de 0 y 1, pero también son posibles otras codificaciones. [4]
La evolución generalmente comienza a partir de una población de individuos generados aleatoriamente, y es un proceso iterativo , donde la población en cada iteración se denomina generación . En cada generación se evalúa la aptitud de cada individuo de la población; la aptitud suele ser el valor de la función objetivo en el problema de optimización que se resuelve. Los individuos más aptos se seleccionan estocásticamente de la población actual y el genoma de cada individuo se modifica ( se recombina y posiblemente se muta aleatoriamente) para formar una nueva generación. La nueva generación de soluciones candidatas se utiliza luego en la siguiente iteración del algoritmo . Comúnmente, el algoritmo termina cuando se ha producido un número máximo de generaciones o se ha alcanzado un nivel de aptitud satisfactorio para la población.
Una representación estándar de cada solución candidata es como una matriz de bits (también llamada conjunto de bits o cadena de bits ). [4] Se pueden utilizar matrices de otros tipos y estructuras esencialmente de la misma manera. La principal propiedad que hace que estas representaciones genéticas sean convenientes es que sus partes se alinean fácilmente debido a su tamaño fijo, lo que facilita operaciones de cruce simples. También se pueden utilizar representaciones de longitud variable, pero la implementación cruzada es más compleja en este caso. Las representaciones en forma de árbol se exploran en la programación genética y las representaciones en forma de gráfico se exploran en la programación evolutiva ; En la programación de la expresión genética se explora una combinación de cromosomas lineales y árboles .
Una vez definidas la representación genética y la función de aptitud, un AG procede a inicializar una población de soluciones y luego mejorarla mediante la aplicación repetitiva de los operadores de mutación, cruce, inversión y selección.
El tamaño de la población depende de la naturaleza del problema, pero normalmente contiene varios cientos o miles de posibles soluciones. A menudo, la población inicial se genera aleatoriamente, permitiendo todo el rango de soluciones posibles (el espacio de búsqueda ). Ocasionalmente, las soluciones pueden "sembrarse" en áreas donde es probable que se encuentren soluciones óptimas o la distribución de la probabilidad de muestreo se puede ajustar para centrarse en aquellas áreas de mayor interés. [5]