Los algoritmos evolutivos (AE) son una clase de técnicas metaheurísticas de optimización basadas en poblaciones, inspiradas en los mecanismos de la evolución biológica, como la reproducción, la mutación, la recombinación y la selección. Se utilizan para encontrar soluciones aproximadas a problemas de optimización difíciles donde se desconocen métodos exactos o satisfactorios. Como parte de la computación evolutiva y la inteligencia computacional, los AE operan sobre una población de soluciones candidatas, evaluando su calidad mediante una función de aptitud y aplicando iterativamente operadores evolutivos para mejorar la población a lo largo de las generaciones. Su principal ventaja es que hacen pocas suposiciones sobre el panorama de aptitud subyacente, lo que les permite abordar una amplia variedad de problemas, aunque su complejidad computacional a menudo se deriva de los costos de evaluación de la aptitud.
Algoritmo Genérico
El algoritmo evolutivo típico sigue un proceso iterativo:
- Generar aleatoriamente una población inicial de individuos (la primera generación).
- Evaluar la aptitud de cada individuo en la población.
- Comprobar si se alcanza el objetivo; si es así, terminar.
- Seleccionar individuos como progenitores, preferiblemente aquellos con mayor aptitud.
- Producir descendencia mediante cruce (que imita la reproducción) y, opcionalmente, mutación.
- Aplicar operaciones de mutación a la descendencia.
- Seleccionar individuos para el reemplazo, preferiblemente aquellos con menor aptitud, para formar la siguiente generación.
- Volver al paso 2 y repetir hasta la terminación.
Este marco genérico se adapta en varios tipos de AE, cada uno con representaciones y operadores específicos.
Tipos de Algoritmos Evolutivos
Existen varias variantes de AE, que difieren en la representación genética y los detalles de implementación:
- Algoritmo Genético (AG): El tipo más popular, donde las soluciones se representan como cadenas de números (a menudo binarios). Se aplican operadores como la recombinación y la mutación. Los AG se utilizan ampliamente en problemas de optimización.
- Programación Genética (PG): Las soluciones son programas informáticos, y la aptitud se determina por su capacidad para resolver problemas computacionales. Las variantes incluyen la programación genética cartesiana, la expresión génica, la evolución gramatical, la programación genética lineal y la programación de múltiples expresiones.
- Estrategia Evolutiva (EE): Desarrollada en las décadas de 1960 y 1970 por Ingo Rechenberg, Hans-Paul Schwefel y sus colegas, la EE se centra en la optimización numérica y de ingeniería. Opera sobre vectores de valores reales, utilizando mutación, recombinación y selección determinista. Una característica distintiva es la autoadaptación de la distribución de mutación, con formas como (1+1)-EE, (μ, λ)-EE y (μ+λ)-EE. Desarrollos posteriores incluyen la adaptación de la matriz de covarianza (CMA-ES) y las estrategias evolutivas naturales.
- Evolución Diferencial (ED): Basada en diferencias de vectores, principalmente adecuada para la optimización numérica.
- Optimización Evolutiva Multiobjetivo: Extiende los AE a problemas con múltiples objetivos en conflicto, manteniendo una población que aproxima las soluciones de compromiso en el frente de Pareto.
- Algoritmo Coevolutivo: Las soluciones se evalúan en función de las interacciones con otras soluciones, que pueden competir o cooperar. Útil para paisajes de aptitud dinámicos o competitivos.
- Neuroevolución: Los genomas representan redes neuronales artificiales, codificando la estructura y los pesos de las conexiones, ya sea directa o indirectamente.
- Sistema Clasificador de Aprendizaje (LCS): Las soluciones son conjuntos de clasificadores (reglas). Michigan-LCS evoluciona clasificadores individuales, mientras que Pittsburgh-LCS evoluciona poblaciones de conjuntos de clasificadores. La aptitud se determina mediante aprendizaje por refuerzo o aprendizaje supervisado.
- Algoritmos de Calidad-Diversidad (QD): Apuntan simultáneamente a soluciones de alta calidad y diversas, explorando una amplia variedad de soluciones en el espacio del problema.
Antecedentes Teóricos
Teorema de No Free Lunch
El teorema de no free lunch de la optimización establece que, al considerar todos los problemas de optimización posibles, todas las estrategias de optimización son igualmente efectivas. Esto implica que ningún algoritmo evolutivo es fundamentalmente superior a otro en todos los problemas. Sin embargo, en la práctica, el conjunto de problemas está restringido, y los AE pueden mejorarse explotando el conocimiento específico del problema, como elegir representaciones y operadores apropiados.
Complejidad Computacional
En la mayoría de las aplicaciones reales, la complejidad computacional de los AE es un factor significativo, principalmente debido al costo de la evaluación de la función de aptitud. Las técnicas de aproximación de la aptitud pueden mitigar este problema. Curiosamente, los AE simples a menudo pueden resolver problemas complejos, lo que sugiere que no hay un vínculo directo entre la complejidad del algoritmo y la complejidad del problema.
Aplicaciones y Limitaciones
Los algoritmos evolutivos se aplican en diversos dominios, incluidos el diseño de ingeniería, la programación, el aprendizaje automático (por ejemplo, la neuroevolución) y la optimización multiobjetivo. Son particularmente valiosos cuando el espacio de búsqueda es grande, no lineal o poco comprendido. Sin embargo, su rendimiento depende del ajuste de parámetros y de la representación del problema. Las técnicas de los AE también se utilizan para modelar la microevolución biológica y los procesos celulares, aunque con limitaciones.