Algoritmo genético
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 para problemas de optimización y búsqueda basándose en operadores inspirados biológicamente, como mutación , cruce y selección . [1] Algunos ejemplos de aplicaciones de AG incluyen la optimización de árboles de decisiónpara un mejor rendimiento, resuelva automáticamente sudokus , [2] optimización de hiperparámetros , etc.
En un algoritmo genético, una población de soluciones candidatas (llamadas individuos, criaturas 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 se pueden mutar y alterar; tradicionalmente, las soluciones se representan en binario como cadenas de 0 y 1, pero también son posibles otras codificaciones. [3]
La evolución generalmente comienza a partir de una población de individuos generados aleatoriamente y es un proceso iterativo , con la población en cada iteración llamada 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 está resolviendo. 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 al azar) 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 ). [3] Los arreglos de otros tipos y estructuras se pueden usar 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 simples de cruce . También se pueden usar 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 .; se explora una combinación de cromosomas lineales y árboles en la programación de la expresión génica .
Una vez que se definen la representación genética y la función de aptitud, un AG procede a inicializar una población de soluciones y luego a 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, lo que permite toda la gama de posibles soluciones (el espacio de búsqueda ). Ocasionalmente, las soluciones pueden "sembrarse" en áreas donde es probable que se encuentren soluciones óptimas.
