Unsupervised Multi-kernel Learning for Automated Algorithm Selection
Authors: Yihang Lu, Tome Eftimov, Carola Doerr
Organizations: Sorbonne Université, CNRS, INRAE, IRD, iEES, Paris, France · LIP6, Sorbonne Université, CNRS, Paris, France · Computer Systems Department, Jožef Stefan Institute, Ljubljana, Slovenia
Abstract
Automated algorithm selection in black-box optimization typically relies on supervised models that map landscape features to algorithm performance labels. Such models are costly to train, benchmark-dependent, and often fail to generalize to unseen problem classes. We study an unsupervised alternative: multi-kernel clustering over heterogeneous landscape representations, in which problem instances are grouped without using performance labels in the clustering stage, and the resulting clusters are mapped post hoc to solver recommendations through a strictly separated three-stage evaluation protocol. Drawing on two decades of advances in multiple kernel learning, we adopt a multi-kernel k-means formulation that jointly learns cluster assignments and kernel weights over four heterogeneous landscape views: ELA, DeepELA, DoE2Vec, and TransOptAS. On affine BBOB-derived selector tasks for Differential Evolution (DE) and Particle Swarm Optimization (PSO) at a fixed evaluation budget, we report mean plus or minus standard deviation selector profiles over 50 independent random seeds for stochastic configurations. Multi-kernel clustering obtains the strongest mean profile on the DE portfolio and remains competitive with, and nominally ahead of, the leading baselines on the more compressed PSO portfolio, where differences among the best methods are small relative to stochastic variation. In representative median-seed runs used for visualization, the learned kernel weights retain ELA and TransOptAS while assigning zero weight to DeepELA and DoE2Vec, providing a task-specific interpretation of which representations are retained by the multi-kernel model for selector-oriented grouping.
Landscape feature representations play a central role in automated algorithm selection and meta-learning for black-box optimization, yet little is known about how different representations agree (or disagree) in the structures they impose on problem spaces. This paper presents a systematic unsupervised evaluation of four state-of-the-art representations (ELA, DeepELA, TransOptAS, and DoE2Vec) using a diverse set of affine combinations of BBOB functions (MA-BBOB). By applying extensive clustering analyses, coverage-based stability measures, and cross-representation similarity assessments, we show that each representation organizes the same problems in markedly different ways: ELA and TransOptAS form compact geometric structures, DeepELA provides a balanced intermediate view, and DoE2Vec achieves strong semantic alignment but with substantial fragmentation. Our results reveal that no single representation dominates; rather, they capture complementary aspects of the underlying landscapes. These findings highlight the importance of multi-view analyses for understanding representation behavior and offer guidance on selecting or combining representations in downstream meta-learning and algorithm selection tasks. In addition, across two different algorithm families (Differential Evolution and Particle Swarm Optimization), we show that landscape representations face an inherent trade-off in how well they align structural landscape descriptions with observed performance, indicating that no single representation can fully capture algorithm performance.
Sara Gjorgjieva, Eva Tuba, Barbara Koroušić Seljak +2
The present paper introduces a new representation-driven approach to per-instance algorithm selection, applied to black-box optimization, for automatically choosing the most promising solver from a fixed portfolio. Prior work in continuous optimization largely relies on numerical descriptors, including Exploratory Landscape Analysis features and learned embeddings such as Deep-ELA. This work studies a complementary representation: contour-map visualizations of probed landscapes. A CNN regressor takes multiple instance-specific contour views (stacked or encoded per view and aggregated) and predicts per-solver performance, enabling selection by the predicted best value. On the standard BBOB 2009 single-objective protocol, the resulting selectors significantly outperform the single best solver (SBS) and are competitive with feature-based baselines. A subsequent bi-objective evaluation under the DeepELA setting further indicates that the same image-based principle can be competitive when using windowed contour views. Overall, the results suggest that simple vision models can exploit spatial structure in probed landscapes for algorithm selection without handcrafted ELA features.
In black-box optimization, a central question is which algorithm to use to solve a given, previously unseen, problem. Selecting a single algorithm, however, entails inherent risks: inaccuracies in the selector may lead to poor choices, and even well-performing algorithms with high variance can yield unsatisfactory results in a single run. A natural remedy is to split the evaluation budget across multiple runs of potentially different algorithms. Such sequential algorithm portfolios benefit from variance reduction and complementarities between algorithms, often outperforming approaches that allocate the entire budget to a single solver. While effective portfolios can be constructed post-hoc, transferring this idea to the algorithm selection setting is non-trivial. We show that a naive portfolio constructed over the full training set already outperforms the strongest traditional baseline, the virtual best solver. We then propose a simple yet effective k-nearest-neighbor-based finetuning approach to construct portfolios tailored to unseen instances, yielding further improvements and highlighting the effectiveness of portfolio selection in fixed-budget black-box optimization.