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

Technical Summary: Structural (Dis)Agreement of Landscape Representations in Black-Box Optimization

Problem Statement
Automated Algorithm Selection (AAS) for black-box optimization relies heavily on landscape feature representations to map problem instances to algorithm performance. While various representations exist—ranging from traditional Exploratory Landscape Analysis (ELA) features to deep learning-based embeddings (e.g., DoE2Vec, DeepELA, TransOptAS)—there is limited understanding of how these different representations agree or disagree regarding the structural organization of problem spaces. Current research faces two primary challenges: a lack of sufficiently diverse benchmark datasets to test generalization, and the uncertainty of whether existing representations capture complementary or redundant information about underlying landscape properties. Specifically, it remains unclear if different representations organize the same set of problems in consistent ways or if they emphasize distinct geometric versus semantic properties.

Methodology
The authors propose a systematic, unsupervised evaluation pipeline to analyze the structural consistency and complementarity of four state-of-the-art landscape representations:

1. ELA: Traditional low-level statistical features (62 features per instance).
2. DoE2Vec: A variational autoencoder producing 32-dimensional latent vectors.
3. TransOptAS: A transformer-based encoder producing 50-dimensional embeddings trained to predict algorithm performance.
4. DeepELA: A self-supervised transformer producing 48-dimensional features invariant to function transformations.

Data Generation:
To ensure diversity beyond standard benchmarks, the study utilizes the MA-BBOB suite. This dataset consists of 8,280 transformed problem instances generated via affine combinations of 552 pairs of distinct BBOB problem classes. Each combination is evaluated using a Latin Hypercube Sample of size $50d$ with dimension $d=10$.

Experimental Procedure:

1. Clustering: For each representation, the authors performed an extensive grid search over five clustering algorithms (Agglomerative, K-Means, Spectral, Gaussian Mixture, BIRCH) and hyperparameters (cluster counts $k \in [5, 500]$). The optimal configuration for each representation was selected based on the Silhouette Score.
2. Within-Representation Analysis: The authors constructed coverage matrices to track how problem instances distribute across clusters. They evaluated these structures using Homogeneity (H), Completeness (C), and V-measure (V) to assess how well the clusters align with the ground-truth problem classes.
3. Cross-Representation Analysis: To compare representations, the authors derived vector-based descriptions of clusters (where each vector entry represents the frequency of a specific problem in a cluster) and computed cosine similarity between clusters of different representations. Hierarchical clustering was applied to these similarity scores to identify structural alignments.
4. Performance Alignment: Finally, the study analyzed the relationship between feature-space clusters and algorithm performance. Using portfolios of Differential Evolution (DE) and Particle Swarm Optimization (PSO) variants, the authors measured how consistently the best-performing algorithm configuration was selected within the clusters defined by each representation.

Key Results
The study reveals that no single representation dominates; rather, each organizes the problem space in a fundamentally different manner, capturing complementary aspects of the landscape:

• Geometric Cohesion (ELA & TransOptAS): These representations form compact, well-separated geometric structures. ELA achieved the highest Silhouette score (0.3505), and TransOptAS followed (0.2670). However, both exhibited low Homogeneity, meaning that while clusters are geometrically tight, they often contain mixed problem types.
• Semantic Fidelity vs. Fragmentation (DoE2Vec): DoE2Vec achieved the highest Homogeneity (0.5612) and V-measure (0.5882), indicating strong alignment with true problem semantics. However, it produced a highly fragmented landscape with a large number of clusters (355) and the lowest Silhouette score (0.1722), suggesting over-segmentation of the feature space.
• Balanced View (DeepELA): DeepELA provided an intermediate view, balancing geometric separation and semantic consistency, though it showed moderate similarity to other representations.
• Structural Disagreement: Cross-representation similarity heatmaps showed that while TransOptAS aligns closely with ELA, DoE2Vec diverges significantly due to its fine-grained clustering. The four representations organize the same problems in markedly different ways.
• Performance Trade-off: When analyzing algorithm performance (DE and PSO), a trade-off emerged. DoE2Vec showed the highest homogeneity in performance selection (problems in the same cluster tend to share the best algorithm), but low completeness (similar algorithms were selected across different clusters). Conversely, TransOptAS showed high completeness (grouping similar performance problems together) but lower purity. No single representation fully captured algorithm performance behavior.

Significance and Contributions
The paper's primary contribution is the demonstration that landscape representations are not interchangeable; they impose distinct structural views on the same problem space.

• Complementarity: The findings highlight that ELA/TransOptAS favor geometric cohesion, while DoE2Vec prioritizes semantic purity. This suggests that multi-view analyses are essential for building robust meta-learning systems, as relying on a single representation may miss critical aspects of the problem landscape.
• Guidance for Selection: The results offer guidance for downstream tasks: if the goal is to group problems with similar algorithmic behavior, representations with high completeness (like TransOptAS) may be preferable, whereas those with high homogeneity (like DoE2Vec) may better isolate specific problem types.
• Limitations: The authors note that the study is limited to a single benchmark suite (MA-BBOB) and specific algorithm families (DE and PSO). However, the proposed empirical framework is designed to be extensible to other benchmarks and optimization domains.

In conclusion, the study argues against the existence of a "universal" landscape representation. Instead, it advocates for the integration of multiple representations to leverage their complementary strengths in automated algorithm selection and meta-learning.