Source-linked AI summary
Automated Algorithm Selection on Continuous Black-Box Problems By Combining Exploratory Landscape Analysis and Machine Learning
Pascal Kerschke, Heike Trautmann
TL;DR
Continuous black-box optimization lacks broadly established methods for selecting among many competing solvers on unseen problems. The paper combines ELA features with machine learning to build algorithm selectors, achieving about half the resource use of the portfolio’s single best solver while remaining bounded by the BBOB benchmark setting.
Problem
Few studies perform algorithm selection for continuous optimization, despite the many available solvers and the need to choose well for unseen problem instances.
Method
The paper combines automatically computed ELA features with machine learning and feature selection to construct selectors from a complementary portfolio evaluated on COCO/BBOB data.
Results
The selector reduces the portfolio’s single best solver’s mean relative ERT by half, requiring only half its resources on average.
Takeaways & Limitations
Feature-based selection can automatically construct powerful solver selectors for unseen single-objective continuous black-box problems, with a small set of ELA features and function evaluations.
Takeaways & Limitations
The models’ quality depends on the benchmark, performance measure, and representativeness of the included optimization problems, with possible shortcomings in the BBOB setting.
Abstract
from arXiv · showhide
In this paper, we build upon previous work on designing informative and efficient Exploratory Landscape Analysis features for characterizing problems' landscapes and show their effectiveness in automatically constructing algorithm selection models in continuous black-box optimization problems. Focussing on algorithm performance results of the COCO platform of several years, we construct a representative set of high-performing complementary solvers and present an algorithm selection model that - compared to the portfolio's single best solver - on average requires less than half of the resources for solving a given problem. Therefore, there is a huge gain in efficiency compared to classical ensemble methods combined with an increased insight into problem characteristics and algorithm properties by using informative features. Acting on the assumption that the function set of the Black-Box Optimization Benchmark is representative enough for practical applications the model allows for selecting the best suited optimization algorithm within the considered set for unseen problems prior to the optimization itself based on a small sample of function evaluations. Note that such a sample can even be reused for the initial population of an evolutionary (optimization) algorithm so that even the feature costs become negligible.
1 Introduction
The paper addresses continuous optimization algorithm selection by using problem-specific landscape features to choose among complementary solvers. Its ELA-based selector improves benchmark performance and requires half the resources of the portfolio’s single best solver.
- Motivation: The Algorithm Selection Problem chooses the best algorithm from a portfolio for an unseen problem instance.Continuous optimization has relatively few algorithm-selection studies, despite the large number of available solvers.
- Approach: ELA supplies instance-specific features that enable machine-learning models to select solvers for single-objective continuous optimization.The approach transfers feature-based selection ideas from other optimization domains to continuous black-box problems.
- Results: The ELA-based selector achieves strong average performance improvements over every portfolio solver and approaches the virtual best solver.The virtual best solver is an oracle-like selector that always predicts the best algorithm without feature costs.
- Results: The selector requires only half the resources needed by the portfolio’s single best solver.The model combines automatically computed ELA features with machine learning and feature selection on a broad portfolio and benchmark set.
- Contribution: The study extends automated machine learning to optimization while analyzing selectors, algorithm differences, and problem instances.The paper presents this as the first such extensive combination of ELA features, machine learning, and feature selection for continuous black-box optimization.
2 Exploratory Landscape Analysis
Exploratory Landscape Analysis characterizes optimization landscapes numerically through feature values computed from sampled decision spaces. The paper situates ELA within earlier landscape measures and provides tools for computing and inspecting these features.
- Scope: The study restricts its feature-based analysis to single-objective, continuous optimization problems.Problem-dependent landscape features can generally be computed for optimization problems, but this work focuses on one domain.
- Exploratory Landscape Analysis: ELA characterizes a problem’s landscape using 50 numerical measures grouped into six low-level feature categories.The features are based on systematic decision-space sampling, including latin hypercube designs.
- Related Work: Earlier landscape analysis used measures such as fitness-distance correlation, dispersion, ruggedness, and fitness-distance analyses.These methods preceded the introduction of the ELA terminology.
- Related Work: Subsequent work expanded landscape features with hill climbing, information content, length scales, constrained-problem measures, local features, and nearest better clustering.Nearest better clustering distinguishes funnel-shaped landscapes from landscapes with more randomly aligned local optima.
- Feature Representation: ELA’s feature categories relate low-level numerical features to higher-level landscape properties.Figure 2 presents this relation using grey rectangles for high-level properties and white ellipses for low-level features.
- Flacco: Flacco consolidates landscape-analysis features in an R package, while its web-hosted GUI provides a platform-independent interface.The GUI offers a slimmer, user-friendly version of flacco for specifying optimization functions and related inputs.
3 Exploratory Data Analysis of COCO
The study reuses COCO performance data from multiple BBOB competitions to analyze continuous black-box optimization solvers. It retains a common set of instances after data validation, while acknowledging important comparability limitations in the benchmark setup.
- COCO data: COCO5 provides performance results for 129 optimization algorithms submitted across five BBOB competitions from 2009 to 2015.The platform includes broad algorithm-class coverage and current state-of-the-art optimizers.
- COCO data: The competitions covered dimensions d ∈ {2, 3, 5, 10, 20, 40}, 24 functions, and 15 instances per dimension-function pair.Only instances 1 to 5 were common to every competition; the other ten varied by year.
- Performance data: The performance records log function evaluations and fitness values, enabling success and evaluation-cost assessment at precision thresholds ε ∈ {10^1, 10^0, ..., 10^-7}.These records support computing solver performance measures such as Expected Runtime.
- Limitations: The benchmark setup has drawbacks because fixed absolute precision thresholds and ERT aggregation across different instances can undermine cross-instance comparability.The authors retain the setup for established community-wide comparability while identifying these concerns explicitly.
- Limitations: Different transformations of the same BBOB problem can produce substantially different landscapes, motivating replicated runs and instance-level rather than only function-level evaluation.The authors recommend at least five to ten replicated runs on each instance.
- Preprocessing: The analysis uses instances 1 to 5 because they are the only instance set shared across all five competitions, allowing all 129 solvers to contribute valid data.Later competitions contained submissions that failed some run or instance checks, but their first five instances remained usable.
4 Experimental Setup
The experimental setup derives solver performance from COCO records using ERT observations for dimensions 2, 3, 5, and 10, across 24 BBOB functions and five instances.
- Performance measurements: 61 920 ERT observations were computed across 129 solvers, four dimensions, 24 BBOB functions, and five problem instances.The ERT threshold was ε = 10^-2, because smaller thresholds produced too many unsuccessful runs.
4.2 Instance Feature Data
The feature data characterize each problem through 102 ELA-derived measurements computed from sampled decision-space observations. Feature values are aggregated across five instances to match the performance-data layout.
- Feature computation: Each ELA feature set used an improved latin hypercube design with 50×d observations sampled in [−5, +5]^d.Features were computed for four dimensions, 24 BBOB problems, and five instances.
- Feature computation: Cell mapping angle features used three blocks per dimension because larger values would create too many empty cells in higher-dimensional spaces.This design choice addresses the curse of dimensionality in the discretized representation.
- Feature computation: The feature collection contains 102 measurements per problem instance spanning six classical feature groups, dispersion, information content, nearest better clustering, and principal components.These feature families combine statistical, geometric, and landscape-structure information.
- Feature aggregation: Feature values were aggregated across the five instances of each BBOB problem using the median, reducing the data to 96 observations matching 24 problems across four dimensions.The authors note that this aggregation causes information loss.
4.3 Constructing the Algorithm Portfolio
The portfolio is constructed to be compact, complementary, and high-performing by selecting solvers that rank among the top three for at least one BBOB function in each dimension.
- Portfolio construction: The portfolio-selection procedure ranks solvers by ERT for each BBOB problem and retains those reaching the “Top 3” for at least one of 24 functions.Four solver sets are built, one for each considered dimension.
- Portfolio composition: The resulting portfolio contains 12 optimization algorithms grouped into four categories.The categories represent distinct solver strategies rather than a single algorithm family.
- Brent-STEP variants: The Brent-STEP variants BSrr and BSqi perform axis-parallel searches while choosing dimensions through round-robin or quadratic-interpolation strategies.Brent-STEP accelerates the STEP global line-search method with Brent’s method.
- Multi-level approaches: The multi-level category includes stochastic multistart and local-search methods such as MLSL, fmincon, fminunc, HMLSL, and MCS.MCS partitions the search space into boxes containing known observations before launching local searches from promising boxes.
- Other solver families: The portfolio also includes CMA-ES variants, surrogate-assisted and model-based methods, and the commercial multistart solver OQNLP.The cited portfolio descriptions include IPOP400D, BIPOP-s∗aACM-ES-k, SMAC-BBOB, and OQNLP.
4.4 Machine Learning Algorithms
The study trains algorithm selectors with classification, regression, and paired regression, using several machine-learning models and a limited hyperparameter configuration.
- Learning strategies: Three supervised-learning strategies are considered: classification predicts the best optimizer, while regression and paired regression predict solver performance before selecting a solver.Classification ignores performance differences among non-best solvers, whereas regression models predict each optimizer’s performance.
- Learning strategies: Four model families—regression trees, kernel-based support vector machines, random forests, and extreme gradient boosting—are used across the learning strategies.The models are implemented with the R-package mlr.
- Configuration: SVM inverse kernel width is automatically configured, while other hyperparameters use default settings, including Gaussian kernels and 500-tree random forests.The random-forest feature-sampling rule differs between classification and regression tasks.
- Solver context: BIPOP-CMA-ES is a multistart CMA-ES with equal budgets for increasing-population and varying-small-population restart strategies.This solver is identified in the section’s optimizer references.
- Solver context: Ties between solvers are resolved by uniform random sampling.
4.5 Feature Selection Strategies
The framework starts with all 102 features but applies feature-selection strategies to reduce noise and redundancy and improve selector performance.
- Feature-selection setup: The 14 algorithm selectors are initially trained with all 102 features, although noise and redundancy may harm their performance.The considered selectors span classification, regression, and paired regression approaches.
- Greedy strategies: Greedy forward-backward selection starts empty and alternates adding and removing features while performance improves.
- Greedy strategies: Greedy backward-forward selection starts with all 102 features and alternates removing and adding features per iteration.
- Genetic strategies: The (10 + 5)-GA represents selected features as a 102-bit string and evolves subsets for up to 100 generations using mutation and crossover.Its default population and offspring sizes are 10 and 5, respectively.
- Genetic strategies: The (10 + 50)-GA increases offspring from 5 to 50 per generation to increase selection pressure.
4.6 Performance Assessment
Performance is assessed with normalized relative ERTs, penalized missing values, cross-validation, and comparisons against virtual-best and single-best solver baselines.
- Evaluation metric: Relative ERT normalizes each solver’s expected running time by the best solver’s ERT for the corresponding BBOB problem.This reduces bias toward multimodal and higher-dimensional problems and supports comparisons across problems and dimensions.
- Evaluation metric: Missing relative ERTs are replaced by a PAR10 penalty of 36 690.3, equal to ten times the highest valid relative ERT.
- Validation: Selectors are evaluated by mean relative ERT, including initial-design costs, using leave-one-function-out cross-validation.The procedure trains and tests selectors across held-out BBOB functions.
- Baselines: The virtual best solver supplies a theoretical lower bound by always choosing the best-performing algorithm for each instance.
- Baselines: The single best solver is the portfolio’s aggregated best solver and is the more practically important baseline because selectors must outperform it after feature costs.
4.7 Overview of the Interlinks Between our Framework’s Building Blocks
The framework links benchmarked solver performances and landscape features to machine-learning models, evaluates the resulting selectors, and feeds evaluation back into feature selection. Machine-learning hyperparameter tuning remains future work because the study mostly uses default configurations.
- Framework interlinks: The framework’s building blocks are connected through interactions among benchmarked performances, landscape features, machine-learning models, and selector evaluation.
- Framework interlinks: Benchmarked performances and automatically computable landscape features train machine-learning models whose selector performance is subsequently assessed.
- Feedback mechanisms: Evaluation results feed back into model development through choices such as selecting more informative feature subsets.
- Limitations: The study largely uses default machine-learning configurations, leaving optimal machine-learning configuration as future work.Only one important SVM parameter is configured separately.
- Figure 4: Figure 4 maps ELA, algorithm benchmarking, machine-learning modeling, and selector evaluation into blue, green, red, and yellow areas.A grey background connects these components to machine learning more generally.
5 Results
The portfolio contains complementary solvers, enabling ELA-based selectors to outperform the single best solver and approach virtual-best performance. Model 1 requires 16.67 ERT including feature costs and 13.60 excluding them, while feature costs are often negligible relative to optimization costs.
- 5.1 Analyzing the Algorithm Portfolio: Only ten BBOB problems have a ratio above two between the portfolio’s best solver and the best COCO solver, supporting the feasibility of effective selection.The paper concludes that a well-performing selector will likely require less than twice the evaluations of the best COCO algorithm.
- 5.1 Analyzing the Algorithm Portfolio: HCMA is the portfolio’s single best solver, with mean relERT 30.37, but it is not best across all problem groups.BSqi and BSrr lead separable problems; MLSL, fmincon and HMLSL lead highly conditioned unimodal problems; MCS or CMA-CSA lead adequately structured multimodal problems.
- 5.2 Analyzing the Best Algorithm Selector: 16.67 is Model 1’s mean relative ERT including feature costs, versus 30.37 for HCMA; excluding feature costs, Model 1 reaches 13.60.Model 1 predicts an optimizer at least as good as HCMA on all but the 2D Rastrigin instance when feature costs are excluded.
- 5.2 Analyzing the Best Algorithm Selector: 50 × d evaluations for feature computation can have little total-cost impact on complex problems and can be reused as an evolutionary algorithm’s initial population.Model 1’s losses occur on simple, quickly solvable problems, while the virtual-best solver’s ERT ranges from 4.4 to 7 371 411.
- 5.3 Improving the Currently Best Algorithm Selector: Model 2 has the best overall performance and performs best on multimodal functions with weak global structure, FIDs 20 to 24.Model 2 differs from HCMA more often than Model 1, although both selectors remain biased toward the single best solver.
- 5.4 Critical Discussion: Robustness of the Results: Removing the problematic 3D FID 4 instance and restricting evaluation to 5D and 10D problems still produced selectors that substantially outperform HCMA.On higher-dimensional problems, HCMA remains best among portfolio solvers with relative ERTs of 6.5 and 6.9, respectively, yet a random-forest selector performs better.
6 Conclusion and Outlook
The study demonstrates that combining machine learning with informative ELA features can construct effective algorithm selectors for unseen continuous black-box problems. Its conclusions are bounded by the BBOB setting and reliance on ERT, while future work targets broader benchmarks, alternative measures, and additional optimization settings.
- Conclusion: ELA features combined with sophisticated machine learning reduced the portfolio single best solver’s mean relative ERT by half.The approach constructs algorithm selection models for unseen optimization problems using a small set of ELA features and function evaluations.
- Conclusion: The methodology is supported by an R package with a graphical user interface for transfer to other continuous optimization scenarios.
- Limitations: Model quality depends on the algorithm benchmark, performance measure, and representativeness of included optimization problems.The study used the commonly accepted BBOB workshop setting but identifies possible shortcomings and plans to include other benchmarks and practical applications.
- Limitations: The experiments relied on ERT, whose use across all possible settings is debatable and whose replacement may produce a different algorithm selection model.The authors plan to investigate alternative performance measures and their applicability to algorithm selection.
- Outlook: Future work includes more sophisticated feature selection, automated machine-learning hyperparameter tuning, and extensions to constrained and multi-objective optimization.