Saltar al contenido
Volver a los resultados

Algoritmo Genético Estocástico — Búsqueda Evolutiva Aleatorizada para Optimización

Propuesto por
Holland, J. H.
Año
1975
Tipo
Stochastic evolutionary metaheuristic
Familia
Simulation / optimization

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?

El Algoritmo Genético Estocástico (SGA) es una metaheurística basada en poblaciones que imita la evolución biológica —selección, cruce y mutación— para buscar soluciones casi óptimas en espacios complejos, no lineales o combinatorios.

Sus operadores aleatorizados lo hacen robusto frente a óptimos locales y ampliamente aplicable en ingeniería, planificación, aprendizaje automático e investigación de operaciones.

La intuición detrás del método

Imagine una población de soluciones candidatas compitiendo por la supervivencia. Las mejores soluciones tienen mayor probabilidad de ser elegidas como progenitores; sus descendientes heredan y recombinan buenos rasgos, mientras que mutaciones aleatorias ocasionales introducen novedad. A lo largo de muchas generaciones, este proceso converge hacia regiones de alta calidad del espacio de búsqueda sin necesidad de información del gradiente. La etiqueta estocástica subraya que la selección, el cruce y la mutación implican sorteos probabilísticos, lo que distingue al AG canónico de raras variantes deterministas y le confiere capacidad de búsqueda global.

Historia

John Holland introdujo los fundamentos teóricos de los algoritmos genéticos en la Universidad de Michigan en 1975, basándose en trabajos anteriores de Fraser (1957) sobre sistemas genéticos simulados. El libro de texto de David Goldberg de 1989 popularizó los AG para la optimización en ingeniería. La naturaleza estocástica de la selección se formalizó a través del teorema de los esquemas, y el método se convirtió en una piedra angular de la computación evolutiva y la inteligencia computacional.

Cuándo usarlo

Utilice un Algoritmo Genético Estocástico cuando: (1) el espacio de búsqueda sea grande, multimodal o discontinuo y los métodos basados en gradientes fallen o sean inaplicables; (2) la función objetivo sea de caja negra, ruidosa o costosa de evaluar pero tratable para el muestreo a nivel de población; (3) los problemas combinatorios o de enteros mixtos carezcan de solucionadores exactos eficientes; (4) se acepte una solución casi óptima encontrada dentro de un número razonable de evaluaciones. NO utilice SGA cuando: el problema sea convexo o el gradiente esté disponible y sea barato — la optimización clásica converge más rápido; cuando las evaluaciones de la función sean extremadamente costosas (decenas o cientos), los métodos basados en poblaciones puedan agotar el presupuesto; o cuando se requiera una solución demostrablemente óptima, ya que los AG no ofrecen garantías de optimalidad.

Limitaciones y consideraciones

  • No hay garantía de encontrar el óptimo global; la calidad de la solución depende del tamaño de la población, las elecciones de operadores y el número de generaciones.
  • Computacionalmente costoso en comparación con los métodos basados en gradientes en problemas suaves y de baja dimensión — se requieren muchas evaluaciones de la función.
  • La sintonización de hiperparámetros (tamaño de la población, tasa de cruce, tasa de mutación) depende del problema y a menudo requiere experimentación.
  • La convergencia prematura puede ocurrir si la presión selectiva es demasiado alta o la tasa de mutación es demasiado baja, atrapando la búsqueda en regiones subóptimas.

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

Fortalezas

  • No requiere información del gradiente — aplicable a objetivos de caja negra, discontinuos o no diferenciables.
  • Maneja de forma natural espacios de búsqueda combinatorios, de enteros mixtos y de permutaciones con codificación apropiada.
  • Paralelizable por diseño: la población puede evaluarse en paralelo, reduciendo el tiempo de reloj.
  • Robusto frente a óptimos locales debido a la diversidad de la población y la exploración estocástica.
  • Altamente extensible: los operadores, codificaciones y esquemas de selección pueden personalizarse para restricciones específicas del dominio.

Aplicaciones

  • Planificación de talleres y líneas de producción en manufactura y logística
  • Selección de características y sintonización de hiperparámetros en flujos de trabajo de aprendizaje automático
  • Optimización estructural y de topología en ingeniería mecánica y civil
  • Problemas del viajante de comercio y de ruteo de vehículos en investigación de operaciones
  • Predicción de estructura de proteínas y descubrimiento de fármacos en bioinformática
  • Búsqueda de arquitectura de redes neuronales y optimización de pesos

Cómo funciona

Cómo funciona

1

Genere una población inicial de N soluciones candidatas (cromosomas) aleatoriamente o mediante siembra heurística. Cada cromosoma codifica un punto factible en el espacio de decisión —cadenas binarias, vectores reales, permutaciones o árboles, dependiendo de la representación del problema elegida.

2

Calcule la aptitud f(x_i) para cada individuo de la población utilizando la función objetivo (o un sustituto). La aptitud cuantifica la calidad de la solución; una mayor aptitud significa una mejor solución. Para problemas de minimización, la aptitud a menudo se define como la recíproca o una transformación de la función de coste.

Fórmula
f(x_i), \quad i = 1, \ldots, N
3

Aplique un operador de selección estocástico para elegir progenitores. La selección por rueda de casino (proporcional a la aptitud) asigna a cada individuo una probabilidad proporcional a su aptitud. La selección por torneo, la selección por rango y el elitismo son variantes comunes que controlan la presión selectiva.

Fórmula
P(\text{select } x_i) = \frac{f(x_i)}{\sum_{j=1}^{N} f(x_j)}
4

Con una probabilidad p_c (típicamente 0.6–0.9), recombine pares de progenitores seleccionados para producir descendencia. El cruce de un solo punto, de dos puntos o uniforme intercambia material genético entre los cromosomas progenitores, creando descendientes que heredan rasgos de ambos. Este operador impulsa la explotación de buenos bloques de construcción.

5

Con una baja probabilidad p_m (típicamente 0.001–0.05 por gen), altere aleatoriamente genes individuales en cada cromosoma descendiente. La mutación mantiene la diversidad genética, previene la convergencia prematura y asegura que el algoritmo pueda escapar de óptimos locales. La tasa de mutación es un parámetro crítico ajustado al problema.

6

Reemplace la población actual con la descendencia (reemplazo generacional) o utilice actualizaciones de estado estable. Evalúe nuevamente la aptitud y repita desde el paso de selección hasta que se cumpla un criterio de parada —número máximo de generaciones, un umbral de aptitud o ninguna mejora durante un número determinado de generaciones.

Errores comunes

  • El uso de una tasa de mutación demasiado alta reduce efectivamente el algoritmo a una búsqueda aleatoria y destruye las ganancias de aptitud acumuladas.
  • Ignorar el elitismo en la estrategia de reemplazo puede hacer que la mejor solución encontrada se pierda entre generaciones.
  • Aplicar operadores de cruce de valor real a problemas codificados binariamente (o viceversa) rompe la codificación y produce descendencia infactible.
  • Detenerse demasiado pronto — número insuficiente de generaciones — es la razón más común de mala calidad de la solución en la práctica.
  • Ignorar el manejo de restricciones: el cruce y la mutación sin restricciones violan frecuentemente las restricciones del problema; se deben incorporar explícitamente funciones de penalización u operadores de reparación.

Preguntas frecuentes

¿Cómo se diferencia un Algoritmo Genético Estocástico de un Algoritmo Genético estándar?

La etiqueta 'estocástico' enfatiza que todos los operadores centrales —selección, cruce y mutación— implican sorteos probabilísticos. El AG canónico introducido por Holland es inherentemente estocástico. La etiqueta se utiliza en la literatura de simulación/optimización para distinguirlo de raras variantes deterministas (p. ej., agrupamiento determinista) y para aclarar que el comportamiento del algoritmo varía entre ejecuciones debido a la aleatoriedad.

¿Qué tan grande debe ser la población?

Un punto de partida común es de 50 a 200 individuos para problemas de dimensionalidad moderada. Poblaciones más grandes mejoran la diversidad y reducen la convergencia prematura, pero aumentan el coste computacional por generación. Existen reglas generales basadas en la longitud del cromosoma (p. ej., 10 veces el número de genes), pero a menudo es necesaria la sintonización empírica o la metaoptimización.

¿Cuándo debería preferir la Optimización por Enjambre de Partículas o el Recocido Simulado sobre un Algoritmo Genético?

La Optimización por Enjambre de Partículas (PSO) suele ser más rápida en problemas continuos de valor real porque explota la información de velocidad. El Recocido Simulado (SA) es más simple de implementar y puede ser eficaz para la búsqueda de trayectorias de solución única. Los AG se prefieren cuando el espacio de búsqueda es combinatorio, cuando el cruce recombina significativamente las estructuras de solución, o cuando la diversidad de la población es valiosa para paisajes multimodales.

¿El Algoritmo Genético Estocástico escala a problemas de alta dimensionalidad?

El rendimiento se degrada en dimensiones muy altas (cientos a miles de variables) porque la población debe ser lo suficientemente grande como para muestrear el espacio adecuadamente. Variantes especializadas —como los AG de aprendizaje de ligamiento, algoritmos de estimación de distribución o modelos de islas con migración— abordan la escalabilidad pero añaden complejidad.

¿Cómo manejo las restricciones en un Algoritmo Genético?

Se utilizan tres estrategias principales: (1) funciones de penalización que reducen la aptitud por violaciones de restricciones; (2) operadores de reparación que proyectan la descendencia infactible de vuelta a la región factible; (3) codificaciones y operadores especializados que solo producen soluciones factibles por construcción. Los métodos basados en penalizaciones son los más fáciles de implementar, pero requieren una calibración cuidadosa de los coeficientes de penalización.

Métodos relacionados

Fuentes

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

    ISBN: 978-0262581110
    Copiado.
  2. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA.

    ISBN: 978-0201157673
    Copiado.