Resumen Técnico: MO-ELA

Planteamiento del Problema

La Selección Automática de Algoritmos (AAS) es un campo maduro para la optimización de un solo objetivo (SO), donde los modelos de aprendizaje automático predicen el algoritmo con mejor desempeño para una instancia de problema específica basándose en características de "análisis del paisaje exploratorio" (ELA). Sin embargo, en el dominio de la optimización multiobjetivo (MO) continua, el panorama de las características disponibles es disperso. Los enfoques existentes suelen depender del cálculo de características de SO para cada objetivo de forma individual, lo que no logra capturar las complejas interacciones entre objetivos, o en características de MO restringidas que no son directamente aplicables a problemas continuos no restringidos (con restricciones de caja). Existe la necesidad de un conjunto de características riguroso y complementario diseñado específicamente para caracterizar el paisaje de los problemas de optimización multiobjetivo continua con restricciones de caja (MOPs) para mejorar el rendimiento de la AAS.

Metodología

Los autores proponen MO-ELA, un nuevo conjunto de 226 características para problemas bi-objetivo y 23 de 233 características para problemas tri-objetivo. Estas características se derivan de un muestreo aleatorio de puntos tanto en los espacios de decisión como de objetivos, utilizando relaciones de dominancia y diversos análisis estructurales. Las características se categorizan en cinco grupos distintos:

1. Características basadas en el Ordenamiento No Dominado (NDS):

   • Utiliza el procedimiento de ordenamiento no dominado (inspirado en NSGA-II) para particionar la muestra en capas ($L_1, L_2, \dots$).
   • Calcula métricas como el número de puntos no dominados, el número de capas y el promedio de puntos por capa.
   • Calcula la Hipervolumen (HV) y las medidas de Solow-Polasky (SP) para las primeras cinco capas.
   • Ajusta regresiones polinómicas (grados 1–4) a los valores de HV a través de las capas para capturar la no linealidad de la distribución del frente de Pareto, utilizando $R^2$ como característica.

2. Estadísticas Descriptivas de Puntos No Dominados:

   • Aplica medidas estadísticas (mínimo, máximo, promedio, desviación estándar) a los vectores de objetivos de la primera capa no dominada ($L_1$).
   • Incluye correlaciones de Spearman de pares entre objetivos y la diferencia absoluta en las desviaciones estándar para casos bi-objetivo.

3. Características Basadas en PCA:

   • Realiza un Análisis de Componentes Principales (PCA) en tres conjuntos: los puntos del espacio de decisión ($X$), los puntos del espacio de objetivos ($Y$) y el conjunto concatenado ($XY$) de la capa no dominada.
   • Extrae el mínimo, el máximo y el promedio de la varianza explicada de los componentes principales de estos conjuntos.

4. Características Basadas en Grafos:

   • Construye grafos basados en la capa no dominada $L_1$ tanto en el espacio de decisión como en el de objetivos.
   • Grafos MST y kNN: Construye Árboles de Expansión Mínima (MST) y grafos de k-Vecinos más Cercanos (kNN) ($k=1$) en el espacio de decisión ($G_D$) y en el espacio de objetivos ($G_O$).
   • Transferencia de Aristas: Transfiere la estructura de aristas de un grafo al otro (por ejemplo, las aristas del MST del espacio de decisión aplicadas a los puntos de los objetivos, denotado como $G_{D \to O}$).
   • Métricas: Calcula pesos de aristas (distancias), centralidad de cercanía de nodos, ángulos entre nodos conectados y propiedades de los componentes conectados (número de componentes, nodos por componente, camino más largo).
   • Incluye razones de características entre los grafos de los espacios de decisión y de objetivos para capturar la distorsión entre los espacios.

5. Características Basadas en Gradientes:

   • Calcula las pendientes absolutas por variable entre los nodos conectados en el MST del espacio de objetivos ($G^O_{ST}$).
   • Agrega estas pendientes a través de todos los objetivos y aristas para formar un vector de gradiente multiobjetivo, del cual se extraen los valores de mínimo, máximo, desviación estándar y promedio.

Configuración Experimental:

• Benchmarks: Un conjunto exhaustivo de 1,165 instancias de problemas derivadas de BiObjBBOB, ZDT, DTLZ y MPM2, que cubren 2 y 3 objetivos y dimensiones $d \in \{2, 5, 10, 20\}$.
• Algoritmos: Se ejecutaron tres solvers (NSGA-II, SMS-EMOA, MOEA/D) 20 veces por instancia.
• Framework de AAS: Se entrenaron modelos de aprendizaje automático (SVM, XGBoost, Random Forest) para predecir el mejor solver. La selección de características se realizó mediante una búsqueda exhaustiva hacia adelante-atrás para identificar el subconjunto más influyente.
• Métricas: El rendimiento se evaluó utilizando el Hipervolumen Normalizado (HVN) y la Mejora Relativa (RI) en el cierre de la brecha entre el Mejor Solver Único (SBS) y el Mejor Solver Virtual (VBS).

Resultados Clave

• Desempeño de la Selección de Algoritmos: Las características propuestas mejoraron significamente el desempeño de la AAS. Para problemas bi-objetivo, el mejor selector (XGBoost con selección de características) logró una RI de 0.963, cerrando efectivamente la brecha con el VBS. Para problemas tri-objetivo, se logró una RI de 0.272.
• Contribución de las Características: Tras la selección de características, las nuevas características propuestas de MO-ELA estuvieron frecuentemente entre los principales contribuyentes.
  • Para problemas bi-objetivo, 14 de las 32 características seleccionadas eran nuevas (dominadas por características de NDS).
  • Para problemas tri-objetivo, 17 de las 36 características seleccionadas eran nuevas (dominadas por características de grafos kNN).
• Estabilidad de las Características: Las características demostraron una alta estabilidad a través de diferentes muestras aleatorias y tamaños de muestra, con correlaciones de pares promedio de ~0.8 para todas las características y casi 1.0 para el subconjunto seleccionado.
• Expresividad de las Características: Las características seleccionadas mostraron una baja correlación mutua (promedio ~0.30 para bi, ~0.23 para tri), lo que indica que capturan aspectos distintos del paisaje del problema.
• Sensibilidad al Tamaño de la Muestra: Un tamaño de muestra de 500 produjo los mejores resultados para las dimensiones 5, 10 y 20. Para la dimensión 2, un tamaño de muestra de 200 fue óptimo. Notablemente, los tamaños de muestra más grandes mejoraron el desempeño incluso cuando el presupuesto restante para las ejecuciones del solver se redujo, lo que sugiere que la expresividad de las características es crítica.

Significancia y Reivindicaciones

El artículo afirma que MO-EDA proporciona una expansión rigurosa de las características de paisaje exploratorio para la optimización multiobjetivo continua. Su principal significancia radica en:

1. Cerrar la Brecha: Aborda la escasez de características para problemas MO introduciendo un conjunto exhaustivo que captura las interacciones entre objetivos y la geometría de ambos espacios (decisión y objetivos).
2. Utilidad Probada: Las características no son meramente teóricas; permiten empíricamente a los modelos de aprendizaje automático distinguir entre instancias de problemas y seleccionar algoritmos con una precisión casi óptima (acercándose al VBS para casos bi-objetivo).
3. Complementariedad: Las nuevas características complementan las características de MO-ELA existentes (de Liefooghe et al., 2021), ya que la selección de características consistentemente retiene una mezcla de ambas, lo que sugiere que diferentes grupos de características capturan distintas propiedades necesarias del paisaje.
4. Practicidad: Las características son estables y efectivas incluso con tamaños de muestra relativamente pequeños (por ejemplo, 200–500 puntos), lo que las hace factibles para aplicaciones prácticas donde los presupuestos computacionales son limitados.

Los autores concluyen que, si bien la investigación está en sus etapas iniciales, estas características proporcionan información significativa sobre la estructura del problema y mejoran significativamente el estado del arte en la selección automática de algoritmos para la optimización multiobjetivo continua.