Glosario · method
Algoritmo Genético
Metaheurística basada en población que imita la selección natural y la transmisión genética, evolucionando iterativamente una población de soluciones candidatas mediante operadores de selección, cruce y mutación.
Genetic AlgorithmGAAlgoritmo EvolutivoMetaheurística Basada en PoblaciónNSGA-II
El algoritmo genético fue introducido por Holland (1975) y popularizado por Goldberg (1989). El algoritmo mantiene varias soluciones candidatas (individuos) simultáneamente; cada individuo se codifica como cromosoma (binario, entero, permutación o real). Cada iteración aplica tres operadores básicos: selección (ruleta, torneo, basada en rango), cruce (un punto, multipunto, uniforme o PMX/OX para permutaciones) y mutación (bit-flip, swap, inversión). La función de aptitud deriva del objetivo y guía la presión de selección. El elitismo conserva a los mejores individuos; los mecanismos de diversidad (niching, crowding) previenen la convergencia prematura. La teoría de convergencia se apoya en el teorema de esquemas (Holland 1975); el teorema No Free Lunch (Wolpert y Macready 1997) muestra que ninguna metaheurística domina universalmente. La extensión multiobjetivo NSGA-II (Deb Pratap Agarwal Meyarivan 2002) es estándar de la industria para aproximar frentes de Pareto. Los problemas de permutación (TSP, scheduling) requieren operadores especializados. Los algoritmos genéticos no garantizan óptimo global, pero entregan buenas soluciones en tiempo razonable y son preferidos para problemas combinatorios, enteros mixtos y de caja negra. Referencias: Goldberg (1989), Eiben y Smith (2015).
Örnek
Un taller de muebles con 30 trabajos en 6 máquinas busca una secuencia que minimice el makespan. La programación entera exacta tarda horas en instancias grandes; un algoritmo genético con población 80, codificación por permutación, cruce OX y mutación swap alcanza un makespan un 22 por ciento por debajo de la heurística inicial en 200 generaciones y 14 minutos. La solución no es probadamente óptima, pero es suficientemente buena para la planificación diaria y aplicable por el planificador del taller.