NSGA-II — Algoritmo Genético de Clasificación No Dominada II
- Año
- 2002
- Tipo
- Evolutionary multi-objective optimisation algorithm
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
NSGA-II (Algoritmo Genético de Clasificación No Dominada II) es el algoritmo de referencia estándar para la optimización evolutiva multiobjetivo, introducido por Deb, Pratap, Agarwal y Meyarivan en 2002.
En lugar de colapsar múltiples objetivos conflictivos en una única puntuación, evoluciona una población de soluciones candidatas a través de generaciones y devuelve un conjunto de soluciones de compromiso Pareto-óptimas — el frente de Pareto — utilizando una clasificación rápida no dominada y una métrica de distancia de aglomeración para preservar la diversidad.
La intuición detrás del método
Imagine que desea diseñar un producto que sea simultáneamente lo más barato y lo más duradero posible. Más barato suele significar menos duradero, por lo que no hay una única respuesta perfecta: hay una familia de compromisos sensatos. NSGA-II funciona como una población de diseños en competencia: cada generación, se eliminan los diseños más débiles que son dominados por otros en todos los objetivos, y los supervivientes se distribuyen para cubrir toda la gama de compensaciones en lugar de agruparse en una esquina. Después de suficientes generaciones, le queda un rico menú de opciones — el frente de Pareto — del cual elige el equilibrio que se ajusta a sus prioridades.
Historia
NSGA-II fue publicado por Kalyanmoy Deb y colegas del Instituto Indio de Tecnología de Kanpur en 2002 como un sucesor corregido y sustancialmente mejorado del NSGA original (Srinivas & Deb, 1994). Las innovaciones clave fueron un procedimiento rápido de clasificación no dominada de complejidad O(MN²), un operador explícito de distancia de aglomeración para mantener la diversidad de soluciones sin un parámetro de compartición, y un mecanismo de selección elitista. El artículo de 2002 en IEEE Transactions on Evolutionary Computation se ha convertido en uno de los trabajos más citados en computación evolutiva y estableció NSGA-II como el punto de referencia de facto para algoritmos evolutivos multiobjetivo. Variantes posteriores — NSGA-III (2014) y otras — extienden el marco a problemas con muchos objetivos.
Cuándo usarlo
NSGA-II se aplica siempre que un problema tenga dos o más funciones objetivo conflictivas que no se puedan fusionar en un único criterio sin pérdida de información. Las variables de decisión pueden ser continuas, binarias o categóricas, y no se requiere ninguna suposición de distribución sobre el paisaje objetivo. El algoritmo se adapta al diseño de ingeniería, asignación de recursos, programación y problemas de cartera donde un espectro de soluciones de compromiso es más útil que un único óptimo. Se necesita un número suficiente de generaciones (típicamente varios cientos o más) para lograr una buena cobertura del frente; ejecutar muy pocas generaciones es el principal modo de fallo.
Limitaciones y consideraciones
- El rendimiento se degrada a medida que el número de objetivos crece más allá de tres o cuatro: la distancia de aglomeración se convierte en una medida de diversidad deficiente en altas dimensiones.
- Requiere una cuidadosa sintonización del tamaño de la población y el número de generaciones; muy pocas generaciones impiden una cobertura adecuada del frente.
- La evaluación de funciones objetivo que implican simulaciones costosas hace que el algoritmo sea computacionalmente costoso.
- Los resultados son estocásticos: diferentes semillas aleatorias pueden producir diferentes frentes de Pareto, por lo que se recomiendan múltiples ejecuciones y comparaciones estadísticas (por ejemplo, hipervolumen).
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Produce un conjunto diverso de soluciones de compromiso Pareto-óptimas en una sola ejecución, evitando la necesidad de repetir la optimización con diferentes pesos.
- La clasificación rápida no dominada se ejecuta en tiempo O(MN²) (M objetivos, N tamaño de población), lo que la hace tratable para tamaños de problema moderados.
- La selección elitista garantiza que las buenas soluciones encontradas al principio nunca se descarten.
- Aplicable a variables de decisión continuas, binarias y categóricas sin suposiciones de distribución.
- Ampliamente validado en dominios de ingeniería, investigación de operaciones y ciencias computacionales.
Aplicaciones
- Diseño de ingeniería: minimización simultánea del peso y maximización de la resistencia estructural en componentes mecánicos.
- Sistemas ambientales y energéticos: equilibrio entre coste, emisiones y fiabilidad en la planificación de redes eléctricas o energías renovables.
- Atención sanitaria e investigación de operaciones: programación que optimiza el tiempo de espera del paciente, la utilización de recursos y el coste simultáneamente.
- Optimización de carteras en finanzas y selección de proyectos en negocios: compensando el rendimiento, el riesgo y la liquidez.
- Ajuste de hiperparámetros en aprendizaje automático: optimización de la precisión frente a la complejidad del modelo o el tiempo de inferencia.
Cómo funciona
Cómo funciona
Se crea una población de soluciones candidatas muestreando variables de decisión aleatoriamente (o por diseño) dentro de sus límites. El tamaño de la población se establece lo suficientemente grande como para garantizar la diversidad en el espacio de objetivos desde el principio.
Cada solución candidata se decodifica en valores de variables de decisión y se evalúa cada función objetivo. El resultado es un vector de puntuaciones de objetivos por individuo. Este paso suele ser el cuello de botella computacional cuando los objetivos implican simulaciones o modelos costosos.
Las soluciones se clasifican mediante clasificación no dominada: el primer frente contiene todas las soluciones que ninguna otra solución domina en todos los objetivos; el segundo frente contiene las soluciones dominadas solo por las del primer frente; y así sucesivamente. Dentro de cada frente, se calcula una puntuación de distancia de aglomeración para medir cuán aislada está una solución de sus vecinas: una mayor distancia de aglomeración significa que la solución ocupa una región menos concurrida del frente.
Una estrategia de selección elitista fusiona la población actual con la descendencia y retiene los mejores N individuos, llenando los frentes en orden y utilizando la distancia de aglomeración para romper empates dentro del último frente admisible. Esto garantiza que las buenas soluciones encontradas en generaciones anteriores nunca se pierdan.
Los individuos seleccionados se reproducen a través de operadores genéticos — selección por torneo binario, cruce binario simulado (SBX) y mutación polinomial — produciendo una nueva población de descendencia. Estos operadores preservan una variación significativa mientras exploran el vecindario de soluciones prometedoras.
Los pasos se evalúan a través de la evolución repetida durante un número especificado de generaciones. La convergencia se juzga por inspección visual del frente de Pareto o por el seguimiento del indicador de hipervolumen. La salida final es el conjunto de soluciones no dominadas que se aproxima al frente de Pareto verdadero.
Errores comunes
- Ejecutar menos de varios cientos de generaciones típicamente produce un frente de Pareto incompleto; si el presupuesto computacional es limitado, considere la optimización mono-objetivo ponderada en su lugar.
- Tratar un problema con un solo objetivo como multiobjetivo es innecesario: utilice un optimizador mono-objetivo.
- No establecer límites de variables sensatos conduce a poblaciones que nunca alcanzan regiones factibles o significativas del espacio de búsqueda.
- Reportar solo una solución del frente de Pareto sin revelar el frente completo oculta la estructura de compromiso que NSGA-II está diseñado para revelar.
Preguntas frecuentes
¿Cuántas generaciones necesita NSGA-II?
No existe una regla universal, pero ejecutar menos de unos pocos cientos de generaciones típicamente produce un frente de Pareto incompleto. Un enfoque práctico es trazar el indicador de hipervolumen a través de las generaciones y detenerse cuando se estabiliza. Si el presupuesto computacional lo impide, un optimizador mono-objetivo ponderado es una alternativa más segura.
¿Qué es el frente de Pareto?
El frente de Pareto es el conjunto de soluciones donde no es posible ninguna mejora en un objetivo sin empeorar al menos otro. NSGA-II aproxima este frente, dándole el menú completo de compromisos equilibrados en lugar de una única respuesta.
¿Puede NSGA-II manejar más de dos objetivos?
Sí, pero la distancia de aglomeración — el mecanismo de diversidad — se vuelve menos efectiva a medida que el número de objetivos excede tres o cuatro (el régimen de 'muchos objetivos'). Para problemas con cinco o más objetivos, generalmente se prefieren NSGA-III o algoritmos basados en descomposición como MOEA/D.
¿Es NSGA-II determinista?
No. Los operadores genéticos y la población inicial implican aleatoriedad, por lo que diferentes ejecuciones con diferentes semillas aleatorias pueden producir diferentes aproximaciones del frente de Pareto. La mejor práctica es ejecutar el algoritmo varias veces y comparar la calidad del frente utilizando el indicador de hipervolumen.
Métodos relacionados
Fuentes
Deb, K., Pratap, A., Agarwal, S. & Meyarivan, T. (2002). A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
Abrir referencia DOICopiado.Zitzler, E., Deb, K. & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173-195.
Abrir referencia DOICopiado.