Speeding Up the NSGA-II via Dynamic Population Sizes

Resumen Técnico: Aceleración de NSGA-II mediante Tamaños de Población Dinámicos

Planteamiento del Problema
Los algoritmos evolutivos multiobjetivo (MOEA), particularmente el Algoritmo Genético de Clasificación No Dominada II (NSGA-II), se utilizan ampliamente para resolver problemas de optimización multiobjetivo. Un desafío central en su aplicación es la gestión del tamaño de la población ($N$). Para representar eficazmente el frente de Pareto (el conjunto de compensaciones óptimas), la población debe ser suficientemente grande. Sin embargo, una población grande ralentiza el algoritmo porque el NSGA-II evalúa $N$ soluciones por iteración. Esto crea un dilema de diseño: una población demasiado pequeña no logra cubrir el frente de Pareto de manera eficiente, mientras que una población demasiado grande incurre en costos computacionales innecesarios. Análisis matemáticos recientes han demostrado que el NSGA-II estático con un tamaño de población fijo óptimo tiene un tiempo de ejecución de $\Theta(n^2 \log n)$ en el benchmark OneMinMax (OMM), lo cual se considera subóptimo en comparación con los límites inferiores teóricos para ciertas clases de algoritmos.

Metodología
Los autores proponen el NSGA-II Dinámico, una variante del algoritmo clásico que aborda el dilema del tamaño de la población comenzando con una población inicial pequeña y aumentándola a lo largo del tiempo.

• Estructura del Algoritmo: El algoritmo comienza con un tamaño de población de $N=4$. Realiza un número fijo de evaluaciones de función, denotado por un parámetro $\tau$ especificado por el usuario, antes de intentar duplicar el tamaño de la población. Este duplicado continúa hasta que se alcanza un tamaño de población máxima definido por el usuario, $N_{max}$. Crucialmente, el duplicado es activado por el número de evaluaciones de función en lugar de las iteraciones, asegurando que cada "fase" del algoritmo reciba un presupuesto computacional aproximadamente igual independientemente del tamaño de la población actual.
• Mecanismo de Selección: Los autores utilizan una variante específica de NSGA-II que emplea la distancia de crowding actual para la resolución de empates. Este mecanismo, que previamente se ha demostrado que mejora la distribución de las soluciones, elimina iterativamente a los individuos con la menor distancia de crowding y recalcula las distancias, lo que conduce a una dispersión de soluciones más equidistante.
• Variantes:
  1. NSGA-II Dinámico Estándar: Duplica la población cada $\tau$ evaluaciones.
  2. NSGA-II Dinámico con Fase Inicial más Larga: Extiende la duración de la fase inicial (donde $N=4$) para que coincida con el presupuesto computacional total de todas las fases subsiguientes combinadas. Esto permite que el algoritmo pase más tiempo en la etapa inicial altamente eficiente sin aumentar el orden del tiempo de ejecución asintótico.
  3. Estrategia Libre de Parámetros (Algoritmo 3): Para eliminar la necesidad de ajustar manualmente $\tau$, los autores proponen una estrategia de ejecución concurrente. Este marco lanza múltiples instancias del NSGA-II dinámico con diferentes valores de $\tau$ (potencias de dos) y asigna dinámicamente recursos a la instancia que ha gastado el menor esfuerzo computacional total hasta el momento.

Contribuciones Clave y Resultados
El artículo proporciona análisis rigurosos del tiempo de ejecución de los algoritmos propuestos en dos benchmarks estándar: OneMinMax (OMM) y OneJumpZeroJump (OJZJ$_k$).

1. Benchmark OMM:

   • El NSGA-II Dinámico estándar con $\tau$ óptimo logra un tiempo de ejecución de $O(n \log^2 n)$ evaluaciones de función con alta probabilidad. Esto es una mejora significativa respecto al tiempo de ejecución de $\Theta(n^2 \log n)$ del NSGA-II estático.
   • La variante con la Fase Inicial más Larga logra un tiempo de ejecución de $O(n \log n)$. Esto es asintóticamente óptimo para una gran clase de algoritmos de caja negra no sesgados, igualando el límite inferior teórico para encontrar la cadena de todos los unos (all-ones string).
   • La estrategia concurrente libre de parámetros (Algoritmo 3) logra tiempos de ejecución de $O(n \log^3 n)$ (estándar) y $O(n \log(N_{max}) \log(n \log N_{max}))$ (fase inicial más larga), incurriendo solo en una penalización de un factor logarítmico en comparación con las versiones ajustadas óptimamente.

2. Benchmark OJZJ$_k$ (con tamaño de brecha $k$):

   • El NSGA-II Dinámico estándar logra un tiempo de ejecución de $O(nk \log^2 n)$, mejorando el tiempo de ejecución conocido de $\Theta(nk+1)$ del NSGA-II estático.
   • La variante con la Fase Inicial más Larga logra $O(nk \log n)$.
   • La estrategia libre de parámetros produce tiempos de ejecución de $O(kn^k \log^3 n)$ y $O(kn^k \log(N_{max}) \log(nk \log N_{max}))$, respectivamente.

3. Robustez e Independencia de Parámetros:

   • Las garantías de tiempo de ejecución para las variantes dinámicas son mayormente independientes del tamaño de población máxima $N_{max}$, siempre que $N_{max}$ sea ligeramente mayor que el tamaño del frente de Pareto (por ejemplo, $N_{max} \ge n+4$).
   • Si $\tau$ se elige de forma subóptima (demasiado pequeño), el algoritmo revierte al rendimiento del NSGA-II estático con un tamaño de población $N_{max}$, asegurando que una mala elección de parámetro no sea catastrófica.
   • La estrategia de ejecución concurrente elimina efectivamente la necesidad de que el usuario seleccione $\tau$, creando un algoritmo "libre de parámetros" respecto a la dinámica del tamaño de la población.

Significancia y Reivindicaciones
Los autores afirman que este trabajo es el primero en analizar matemáticamente un MOEA con parámetros dinámicos, demostrando que la naturaleza multiobjetivo de los problemas permite mejoras significativas de velocidad mediante estrategias de crecimiento de población.

• Avance Teórico: El artículo establece que el dimensionamiento dinámico de la población puede romper la barrera de $\Theta(n^2 \log n)$ para NSGA-II en OMM, logrando tiempos de ejecución que son casi óptimos ($O(n \log n)$) cuando se extiende la fase inicial.
• Implicaciones Prácticas: Al demostrar que una estrategia de ejecución concurrente simple puede lograr un rendimiento cercano al óptimo sin el ajuste manual de parámetros, los autores sugieren un camino hacia MOEAs más robustos y "libres de parámetros".
• Comparación con Archivos: Los autores señalan que, si bien otros trabajos han propuesto el uso de archivos para almacenar soluciones y permitir poblaciones más pequeñas, su enfoque dinámico es teóricamente preferible en ciertos contextos (específicamente respecto a la mutación bit a bit sin cruce) porque evita el riesgo de que la población sea insuficiente para generar nuevas soluciones en el frente de Pareto.

El artículo concluye que el NSGA-II dinámico ofrece una aceleración demostrable de $\tilde{\Omega}(n)$ sobre el NSGA-II estático y que extender la fase inicial mejora aún más el rendimiento hacia los límites teóricos de la optimización de caja negra no sesgada. Se sugiere como trabajo futuro investigar si estas ventajas se mantienen para otros escenarios populares, como el benchmark LOTZ.