Evaluating Real-World Generalizability of Algorithm Selection Models

Resumen Técnico: Evaluación de la Generalizabilidad en el Mundo Real de los Modelos de Selección de Algoritmos

Planteamiento del Problema
La Selección de Algoritmos (AS, por sus siglas en inglés) tiene como objetivo identificar automáticamente el algoritmo de optimización más adecuado para una instancia de problema específica, aprovechando características medibles del problema (rasgos del paisaje) y datos de rendimiento históricos. Aunque los modelos de AS se han desarrollado y evaluado extensamente en conjuntos de pruebas sintéticos controlados (como BBOB y CEC), su capacidad para generalizarse a paisajes de optimización del mundo real permanece en gran medida sin verificar. La literatura existente sugiere que los benchmarks sintéticos a menudo carecen de la complejidad estructural, los patrones de ruido y las restricciones específicas de dominio inherentes a los problemas prácticos. En consecuencia, los modelos entrenados con datos sintéticos pueden sobreajustarse a distribuciones de paisajes específicas y fallar cuando se aplican a tareas realistas y específicas de un dominio. Este estudio aborda la brecha crítica en la comprensión de qué tan bien se transfieren los modelos de AS entre benchmarks sintéticos académicos y conjuntos de problemas del mundo real.

Metodología
El estudio emplea un marco de evaluación sistemática de cross-benchmark que involucra cuatro fuentes de problemas distintas:

1. Benchmarks Sintéticos: El conjunto Black-Box Optimization Benchmarking (BBOB) y la serie de benchmarks de parámetros reales de un solo objetivo de la IEEE CEC.
2. Benchmarks del Mundo Real: Un conjunto de problemas de optimización de trayectoria robótica (ROB) y problemas de planificación de rutas para Vehículos Aéreos No Tripulados (UAV).

La configuración experimental incluye un portafolio de algoritmos de ocho métodos de optimización de un solo objetivo basados en población (incluyendo AGSK, DE, PSO, LSHADE y otros). Los autores evalúan el rendimiento a través de las dimensiones 6, 12, 18, 24 y 30.

Extracción de Características y Preprocesamiento:
El estudio utiliza características de Análisis de Paisaje Exploratorio (ELA) derivadas del paquete flacco (62 características por instancia). Para investigar el impacto de la representación de datos en la generalización, los autores prueban varias estrategias de preprocesamiento:

• Escalamiento: Ninguno, escalamiento de y (solo función objetivo), y escalamiento de x-y (variables de decisión y función objetivo).
• Muestreo: Muestra completa (10,000 puntos) frente a submuestreo (50d puntos).

Modelado y Evaluación:
Se entrena un regresor de Bosque Aleatorio (RF) para predecir la puntuación de precisión normalizada de cada algoritmo para una instancia de problema dada. El rendimiento de la AS se mide mediante la diferencia entre la puntuación del mejor algoritmo predicho y la puntuación del mejor algoritmo real, comparada contra una línea base "dummy" que predice el rendimiento medio del mejor solver observado en el conjunto de entrenamiento. La evaluación sigue un protocolo estricto de cross-benchmark: los modelos se entrenan en un benchmark y se prueban en los cuatro, así como en un entorno de benchmark fusionado. Además, se emplea una prueba de crossmatch para cuantificar la similitud estadística de las distribuciones de características ELA entre pares de benchmarks.

Resultos Clave

• Generalización Limitada: En la mayoría de los escenarios de cross-benchmark, particularmente en dimensiones bajas (6d), los modelos de AS entrenados en benchmarks sintéticos (BBOB/CEC) no logran superar a la línea base dummy cuando se prueban en problemas del mundo real (ROB/UAV), y viceversa.
• Efectos de la Dimensionalidad: Aunque se observó cierta transferencia positiva esporádica (por ejemplo, de CEC a UAV sin escalamiento en 6d, o de CEC a UAV en 12d), la generalización fue inconsistente. En dimensiones más altas (24d, 30d), las mejoras sobre la línea base fueron modestas (0.1–0.2) y altamente dependientes de los pares fuente-objetivo específicos y de las elecciones de preprocesamiento.
• El Fenómeno de Sobreajuste al "Único Mejor Solver": El análisis de las frecuencias de predicción reveló una causa significativa de la pobre generalización. Cuando un benchmark de entrenamiento está dominado por un único algoritmo con mejor desempeño (por ejemplo, EBOwithCMAR en BBOB o APGSK_IMMODE en UAV), el modelo de AS tiende a sobreajustarse prediciendo consistentemente ese mismo algoritmo. Este comportamiento imita efectivamente a la línea base dummy, lo que resulta en ninguna ganancia medible en la precisión de la selección.
• Disparidad en el Espacio de Características: Las estadísticas de la prueba crossmatch confirmaron que los benchmarks sintéticos y del mundo real ocupan regiones mayormente distintas en el espacio de características ELA. Mientras que BBOB y CEC mostraron un solapamiento sustancial, los benchmarks que involucran problemas de robótica y UAV exhibieron una similitud mínima con los suites sintéticas, especialmente en dimensiones altas. Los pasos de preprocesamiento como el escalamiento y el submuestreo aumentaron el solapamiento del espacio de características, pero no se tradujeron consistentemente en una mejora del rendimiento de la AS.

Significancia y Reivindicaciones
El artículo sostiene que un fuerte desempeño en los benchmarks sintéticos estándar no garantiza robustez o transferibilidad a problemas de optimización del mundo real. El estudio destaca que las diferencias estructurales entre los paisajes sintéticos y los del mundo real limitan fundamentalmente la generalización de cross-benchmark.

Los autores concluyen que los enfoques actuales de AS suelen ser insuficientes para el despliegue práctico sin abordar el cambio de distribución entre los dominios de entrenamiento y de destino. Sugieren que el desarrollo futuro debe desplazarse hacia:

1. Enriquecer las colecciones de benchmarks con instancias realistas y diversas.
2. Desarrollar representaciones de características que capturen mejor las características transferibles de los problemas.
3. Diseñar modelos de AS orientados explícitamente a la generalización de cross-dominio en lugar de optimizar el rendimiento para un benchmark específico.

El trabajo subraya la necesidad de ir más allá de los entornos sintéticos controlados para evaluar y desarrollar sistemas de AS capaces de manejar la heterogeneidad y la complejidad de las tareas de optimización del mundo real.