On the Structural (Dis)Agreement of Landscape Representations in Black-Box Optimization

Resumen Técnico: (Des)Acuerdo Estructural de las Representaciones del Paisaje en la Optimización de Caja Negra

Planteamiento del Problema
La Selección Automática de Algoritmos (AAS) para la optimización de caja negra depende en gran medida de las representaciones de características del paisaje para mapear instancias de problemas al rendimiento de los algoritmos. Aunque existen diversas representaciones —desde características tradicionales del Análisis Exploratorio del Paisaje (ELA) hasta incrustaciones basadas en aprendizaje profundo (por ejemplo, DoE2Vec, DeepELA, TransOptAS)—, hay un conocimiento limitado sobre cómo estas diferentes representaciones coinciden o discrepan respecto a la organización estructural de los espacios de problemas. La investigación actual enfrenta dos desafíos principales: la falta de conjuntos de datos de referencia suficientemente diversos para probar la generalización, y la incertidumbre sobre si las representaciones existentes capturan información complementaria o redundante sobre las propiedades subyacentes del paisaje. Específicamente, sigue sin estar claro si diferentes representaciones organizan el mismo conjunto de problemas de manera consistente o si enfatizan propiedades geométricas versus semánticas distintas.

Metodología
Los autores proponen una tubería de evaluación sistemática y no supervisada para analizar la consistencia estructural y la complementariedad de cuatro representaciones del paisaje de última generación:

1. ELA: Características estadísticas de bajo nivel tradicionales (62 características por instancia).
2. DoE2Vec: Un autoencoder variacional que produce vectores latentes de 32 dimensiones.
3. TransOptAS: Un codificador basado en transformadores que produce incrustaciones de 50 dimensiones entrenadas para predecir el rendimiento del algoritmo.
4. DeepELA: Un transformador auto-supervisado que produce características de 48 dimensiones invariantes a las transformaciones de la función.

Generación de Datos:
Para asegurar la diversidad más allá de los estándares de referencia, el estudio utiliza la suite MA-BBOB. Este conjunto de datos consta de 8.280 instancias de problemas transformadas generadas mediante combinaciones afines de 552 pares de clases distintas de problemas BBOB. Cada combinación se evalúa utilizando una Muestra Hipercúbica Latina de tamaño $50d$ con dimensión $d=10$.

Procedimiento Experimental:

1. Agrupamiento (Clustering): Para cada representación, los autores realizaron una búsqueda exhaustiva en cuadrícula sobre cinco algoritmos de agrupamiento (Aglomerativo, K-Means, Espectral, Mezcla Gaussiana, BIRCH) e hiperparámetros (números de clústeres $k \in [5, 500]$). La configuración óptima para cada representación se seleccionó basándose en la Puntuación Silueta.
2. Análisis Dentro de la Representación: Los autores construyeron matrices de cobertura para rastrear cómo se distribuyen las instancias de problemas a través de los clústeres. Evaluaron estas estructuras utilizando Homogeneidad (H), Completitud (C) y Medida V (V) para evaluar qué tan bien los clústeres se alinean con las clases de problemas de verdad fundamental.
3. Análisis Cruzado entre Representaciones: Para comparar representaciones, los autores derivaron descripciones basadas en vectores de los clústeres (donde cada entrada del vector representa la frecuencia de un problema específico en un clúster) y calcularon la similitud del coseno entre clústeres de diferentes representaciones. Se aplicó agrupamiento jerárquico a estas puntuaciones de similitud para identificar alineaciones estructurales.
4. Alineación del Rendimiento: Finalmente, el estudio analizó la relación entre los clústeres del espacio de características y el rendimiento del algoritmo. Utilizando portafolios de variantes de Evolución Diferencial (DE) y Optimización por Enjambre de Partículas (PSO), los autores midieron qué tan consistentemente se seleccionaba la configuración de algoritmo de mejor rendimiento dentro de los clústeres definidos por cada representación.

Resultados Clave
El estudio revela que ninguna representación única domina; más bien, cada una organiza el espacio de problemas de una manera fundamentalmente diferente, capturando aspectos complementarios del paisaje:

• Cohesión Geométrica (ELA y TransOptAS): Estas representaciones forman estructuras geométricas compactas y bien separadas. ELA logró la puntuación Silueta más alta (0.3505), seguida por TransOptAS (0.2670). Sin embargo, ambas exhibieron una baja Homogeneidad, lo que significa que, aunque los clústeres son geométricamente compactos, a menudo contienen tipos de problemas mezclados.
• Fidelidad Semántica frente a Fragmentación (DoE2Vec): DoE2Vec logró la mayor Homogeneidad (0.5612) y Medida V (0.5882), indicando una fuerte alineación con la semántica real del problema. Sin embargo, produjo un paisaje altamente fragmentado con un gran número de clústeres (355) y la puntuación Silueta más baja (0.1722), lo que sugiere una sobre-segmentación del espacio de características.
• Visión Equilibrada (DeepELA): DeepELA proporcionó una visión intermedia, equilibrando la separación geométrica y la consistencia semántica, aunque mostró una similitud moderada con otras representaciones.
• Desacuerdo Estructural: Los mapas de calor de similitud cruzada entre representaciones mostraron que, aunque TransOptAS se alinea estrechamente con ELA, DoE2Vec diverge significativamente debido a su agrupamiento de granularidad fina. Las cuatro representaciones organizan los mismos problemas de maneras marcadamente diferentes.
• Compensación del Rendimiento: Al analizar el rendimiento del algoritmo (DE y PSO), surgió una compensación. DoE2Vec mostró la mayor homogeneidad en la selección de rendimiento (los problemas en el mismo clúster tienden a compartir el mejor algoritmo), pero una baja completitud (se seleccionaron algoritmos similares a través de diferentes clústeres). Por el contrario, TransOptAS mostró alta completitud (agrupando problemas de rendimiento similar juntos) pero menor pureza. Ninguna representación única capturó completamente el comportamiento del rendimiento del algoritmo.

Significado y Contribuciones
La contribución principal del artículo es la demostración de que las representaciones del paisaje no son intercambiables; imponen visiones estructurales distintas sobre el mismo espacio de problemas.

• Complementariedad: Los hallazgos destacan que ELA/TransOptAS favorecen la cohesión geométrica, mientras que DoE2Vec prioriza la pureza semántica. Esto sugiere que los análisis de múltiples vistas son esenciales para construir sistemas robustos de meta-aprendizaje, ya que depender de una sola representación puede omitir aspectos críticos del paisaje del problema.
• Guía para la Selección: Los resultados ofrecen orientación para tareas posteriores: si el objetivo es agrupar problemas con comportamientos algorítmicos similares, las representaciones con alta completitud (como TransOptAS) pueden ser preferibles, mientras que aquellas con alta homogeneidad (como DoE2Vec) pueden aislar mejor tipos de problemas específicos.
• Limitaciones: Los autores señalan que el estudio se limita a una sola suite de referencia (MA-BBOB) y familias de algoritmos específicas (DE y PSO). Sin embargo, el marco empírico propuesto está diseñado para ser extensible a otras referencias y dominios de optimización.

En conclusión, el estudio argumenta en contra de la existencia de una representación de paisaje "universal". En su lugar, aboga por la integración de múltiples representaciones para aprovechar sus fortalezas complementarias en la selección automática de algoritmos y el meta-aprendizaje.