Saltar al contenido
Volver a los resultados

Algoritmo Genético — Optimización Evolutiva

Propuesto por
John Henry Holland
Año
1975
Tipo
Population-based metaheuristic

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

Un algoritmo genético (AG) es un método de optimización metaheurístico basado en poblaciones, introducido por John Henry Holland (1975), que imita los principios de la selección natural. Mantiene una población de soluciones candidatas y las mejora iterativamente a través de operadores de selección, cruce y mutación, lo que lo hace especialmente potente en espacios de búsqueda discontinuos, no convexos y multimodales donde fallan los métodos clásicos basados en gradientes.

La intuición detrás del método

Imagine que tiene miles de posibles respuestas a un problema difícil y ninguna fórmula para encontrar la mejor. Un algoritmo genético trata cada respuesta candidata como un individuo en una población. En cada generación, conserva los individuos más aptos, los cruza para mezclar sus buenos rasgos y ocasionalmente muta a la descendencia para inyectar novedad. A lo largo de muchas generaciones, la población se desplaza hacia soluciones cada vez mejores, no siguiendo un gradiente, sino imitando la forma en que la evolución moldea los organismos a lo largo del tiempo.

Historia

El algoritmo genético fue introducido por John Henry Holland en su libro de 1975 Adaptation in Natural and Artificial Systems, que formalizó la noción de esquema (bloque de construcción) y proporcionó el análisis teórico fundamental de por qué el cruce y la selección impulsan la búsqueda hacia regiones más aptas. Los estudiantes de Holland —notablemente David Goldberg— popularizaron los AG a través de aplicaciones de ingeniería en la década de 1980. Kalyanmoy Deb amplió posteriormente el marco a entornos multiobjetivo, culminando en el ampliamente adoptado algoritmo NSGA-II (2002). Hoy en día, los AG siguen siendo una herramienta estándar en la computación evolutiva, con investigación activa en métodos híbridos que combinan la búsqueda evolutiva con el refinamiento local.

Cuándo usarlo

Los algoritmos genéticos son apropiados cuando el espacio de búsqueda es grande, discontinuo, no diferenciable o altamente multimodal —condiciones en las que los solucionadores basados en gradientes no pueden operar o quedan atrapados en óptimos locales. Se aplican a tipos de variables continuas, categóricas, binarias y ordinales e imponen ninguna suposición de normalidad o distribución. El único requisito es una función de aptitud computable. Para problemas donde existe una formulación analítica o convexa, los métodos clásicos (programación lineal, descenso de gradiente) son más rápidos y deben preferirse. Se requieren iteraciones suficientes (típicamente muy por encima de 1.000 generaciones) para una convergencia significativa; ejecutar muy pocas generaciones es el modo de fallo más común.

Limitaciones y consideraciones

  • No hay garantía de convergencia al óptimo global; los resultados pueden variar entre ejecuciones.
  • Computacionalmente costoso: cada generación requiere la evaluación de toda la población, lo que es prohibitivo cuando la función de aptitud es lenta.
  • El rendimiento es sensible a las elecciones de hiperparámetros —tamaño de la población, probabilidad de cruce y tasa de mutación— que a menudo requieren ajuste específico del problema.
  • Para problemas suaves, convexos o bien estructurados, los métodos clásicos basados en gradientes o lineales serán más rápidos y fiables.

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Funciona en paisajes objetivos discontinuos, no diferenciables y multimodales donde los métodos basados en gradientes fallan.
  • No impone suposiciones de distribución — el único requisito de entrada es una función de aptitud computable.
  • Maneja de forma natural una amplia gama de tipos de variables: continuas, binarias, categóricas y ordinales.
  • La diversidad de la población permite la exploración simultánea de múltiples regiones del espacio de búsqueda, reduciendo el riesgo de quedar atrapado prematuramente en un óptimo local.
  • Altamente extensible: operadores de cruce y mutación específicos del dominio, manejo de restricciones y variantes multiobjetivo (por ejemplo, NSGA-II) están bien establecidos en la literatura.

Aplicaciones

  • Optimización de diseño de ingeniería: encontrar configuraciones de parámetros óptimas para estructuras, circuitos o sistemas mecánicos.
  • Problemas de planificación y enrutamiento: planificación de talleres, enrutamiento de vehículos y elaboración de horarios donde el espacio de búsqueda combinatorio es demasiado grande para una búsqueda exhaustiva.
  • Aprendizaje automático: ajuste de hiperparámetros, búsqueda de arquitecturas neuronales y selección de características.
  • Investigación de operaciones: optimización de la cadena de suministro, asignación de carteras y asignación de recursos bajo restricciones complejas.
  • Bioinformática: alineación de secuencias, predicción de la estructura de proteínas e inferencia de redes regulatorias génicas.

Cómo funciona

Cómo funciona

1

Se crea una población de soluciones candidatas (individuos), típicamente de forma aleatoria dentro del espacio de búsqueda. Cada individuo codifica una solución potencial —por ejemplo, como una cadena binaria, un vector de valores reales o una permutación— y el tamaño de la población es un parámetro clave que determina cuán ampliamente se muestrea el espacio de búsqueda desde el principio.

2

Cada individuo de la población es evaluado por una función de aptitud (fitness function) que cuantifica cuán buena es esa solución en relación con el objetivo del problema. La función de aptitud es el único componente específico del dominio que el usuario debe proporcionar; puede ser cualquier medida computable —la salida de una simulación, una fórmula de coste o una métrica de error de un modelo.

3

Los individuos con mayor aptitud se eligen preferentemente para convertirse en padres de la siguiente generación. Los mecanismos de selección comunes incluyen la selección por torneo, la selección por rueda de casino (proporcional a la aptitud) y la selección basada en rangos. La presión de selección controla el equilibrio entre la explotación de soluciones de alta calidad y el mantenimiento de la diversidad de la población.

4

Los padres seleccionados producen descendencia a través del cruce (recombinación), donde segmentos de las codificaciones de dos padres se combinan para formar un nuevo individuo, y a través de la mutación, donde se aplican pequeños cambios aleatorios a genes individuales. La probabilidad de cruce y la tasa de mutación son parámetros críticos de ajuste: muy poca mutación provoca una convergencia prematura, demasiada convierte la búsqueda en un paseo aleatorio.

5

El bucle de evaluar → seleccionar → reproducir continúa durante un número determinado de generaciones o hasta que se cumple un criterio de convergencia (por ejemplo, ninguna mejora durante una ventana de generaciones). Se devuelve el mejor individuo encontrado en todas las generaciones como solución. Dado que no se garantiza la convergencia al óptimo global, se recomiendan múltiples ejecuciones independientes para problemas de alto riesgo.

Errores comunes

  • Ejecutar muy pocas generaciones es el error más común: con generaciones insuficientes el algoritmo no converge, por lo que se deben preferir métodos analíticos o basados en gradientes cuando solo se dispone de un presupuesto de iteración pequeño.
  • La convergencia prematura —la pérdida de diversidad de la población demasiado pronto— produce un resultado localmente óptimo pero globalmente subóptimo; mantenga un tamaño de población y una tasa de mutación adecuados para contrarrestar esto.
  • El uso de una función de aptitud mal definida o especificada incorrectamente produce resultados engañosos independientemente de la corrección algorítmica; valide la función de aptitud de forma independiente antes de ejecutar el AG.
  • Aplicar un AG a un problema suave y convexo donde el descenso de gradiente o la programación lineal serían suficientes desperdicia recursos computacionales e introduce estocasticidad innecesaria.
  • Informar de una única ejecución como solución sin verificar la reproducibilidad; para aplicaciones de alto riesgo, ejecute el algoritmo varias veces e informe de la distribución de los resultados.

Preguntas frecuentes

¿Cómo se diferencia un algoritmo genético del descenso de gradiente?

El descenso de gradiente requiere un objetivo diferenciable y sigue el gradiente local hacia abajo. Un algoritmo genético solo requiere que la aptitud pueda calcularse para cualquier solución candidata; busca evolucionando una población en lugar de seguir un gradiente, por lo que puede manejar paisajes discontinuos, no diferenciables y multimodales donde el descenso de gradiente falla o se atasca.

¿Cuántas generaciones y qué tamaño de población necesito?

No hay reglas universales; ambos dependen de la complejidad del espacio de búsqueda. Una población demasiado pequeña o una ejecución demasiado corta corre el riesgo de convergencia prematura. Como punto de partida práctico, los tamaños de población de 50-200 y los recuentos de generaciones de 100-1.000 son comunes en la literatura, pero los problemas desafiantes requieren rutinariamente más. Siempre inspeccione las curvas de convergencia en lugar de fijar criterios de parada arbitrarios.

¿Está garantizado que un algoritmo genético encuentre el óptimo global?

No. Los AG son heurísticas y no ofrecen garantía de convergencia al óptimo global en tiempo finito. Para garantías deterministas, necesita métodos exactos como los solucionadores de programación entera. Para decisiones de alto riesgo, ejecute el AG varias veces, informe de la distribución de los resultados y compare la mejor solución con cualquier cota conocida.

¿Cuándo debería elegir un AG en lugar de recocido simulado o optimización por enjambre de partículas?

Los AG tienden a preferirse cuando la solución se codifica de forma natural como una estructura combinatoria (permutaciones, cadenas binarias) o cuando se necesitan extensiones multiobjetivo. La optimización por enjambre de partículas suele ser más rápida en problemas continuos unimodales. El recocido simulado es más simple de implementar para problemas combinatorios con un vecindario bien definido. En la práctica, es aconsejable comparar dos o tres métodos en una instancia de problema pequeña antes de comprometerse con uno.

Métodos relacionados

Fuentes

  1. Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.

    Abrir referencia de la publicación
    Copiado.
  2. Deb, K. (2001). Multi-Objective Optimization using Evolutionary Algorithms. Wiley.

    ISBN: 9780471873396
    Copiado.