Landscape-Aware Automated Algorithm Configuration Using Multi-output Mixed Regression and Classification

Fu Xing Long, Moritz Frenzel, Peter Krause, Markus Gitterle, Thomas Bäck, Niki van Stein

TL;DR

This paper introduces a novel approach for automated algorithm configuration (AAC) that leverages landscape-aware machine learning models. By training dense neural networks on diverse, randomly generated functions (RGF) alongside existing benchmarks, they achieve near-optimal configurations for black-box optimization problems, often outperforming default settings and competing with state-of-the-art solvers.

What Problem Does This Paper Address?

Finding the best algorithm and its optimal settings (hyperparameters) for a given optimization problem can be a daunting task, especially for practitioners without deep expertise. Traditional methods often rely on extensive trial-and-error or pre-defined configurations that may not be suitable for novel or complex problems. The effectiveness of "landscape-aware" approaches, which use problem characteristics (landscape features) to predict good configurations, is heavily dependent on the training data's ability to represent the real-world problems encountered. Existing benchmarks like BBOB, while useful, are not always representative of practical engineering applications. This paper addresses this gap by exploring more diverse training data sources and developing a robust AAC system.

Methods

The core of this work lies in using dense neural networks (NNs) for predicting optimal algorithm configurations. The approach involves two main phases:

  • Training Phase:
    • Randomly Generated Functions (RGF): Instead of solely relying on standard benchmarks, the authors generate a large set of RGFs. These functions are designed to cover a broader spectrum of optimization problem classes, aiming for better generalization.
  • RGF Selection: A crucial step is implemented to filter these RGFs, selecting only those that exhibit characteristics suitable for AAC. This involves estimating the global optimum and analyzing the ranking ambiguity of configurations found through hyperparameter optimization (HPO).
  • Exploratory Landscape Analysis (ELA): Landscape features are extracted from the selected RGFs using ELA. These features serve as the input for the NN models.
  • Hyperparameter Optimization (HPO): For each RGF, HPO is performed to find the best configuration. This provides the target output for the NN training.
  • NN Training: Dense NNs are trained to map ELA features to optimal configurations. These NNs are designed to handle multi-output mixed regression and classification tasks, as hyperparameters can be continuous, integer, or categorical.
  • Testing Phase:
    • ELA Feature Extraction: ELA features are computed for unseen black-box optimization (BBO) problems.
  • Configuration Prediction: The trained NN models predict the optimal configurations based on these ELA features.

The paper also compares their NN approach against Random Forests (RF), another popular method for landscape-aware algorithm selection.

Datasets

  • Training Data:
    • Randomly Generated Functions (RGF): A large set of RGFs generated using a function generator, designed to be more diverse than standard benchmarks.
  • Many-Affine BBOB (MA-BBOB) Functions: These are generated by affine combinations of BBOB functions, offering a way to extend the BBOB suite's diversity.
  • A combination of RGF and MA-BBOB functions was found to be most effective for training.
  • Evaluation Data:
    • Black-Box Optimization Benchmarking (BBOB) Suite: Used as unseen test problems. The experiments were conducted on BBOB functions in both 5-dimensional (5d) and 20-dimensional (20d) settings.

Key Insights and Ideas

  • RGFs are Crucial for Generalization: The paper strongly advocates for using RGFs as training data. Their inherent diversity allows models to generalize better to unseen problems compared to models trained solely on the BBOB suite.
  • RGF Selection is Key: Not all RGFs are equally useful. A pre-selection step to identify RGFs that provide clear configuration rankings and avoid ambiguous or outlier optima is critical for improving model accuracy. This addresses a potential limitation of previous work that used RGFs without such filtering.
  • Dense NNs Excel at Multi-Output Tasks: The use of dense neural networks is well-suited for the multi-output nature of AAC, where multiple hyperparameters (continuous, integer, and categorical) need to be predicted simultaneously.
  • Combining RGF and MA-BBOB is Optimal: The best performance was achieved when NN models were trained on a combination of RGF and MA-BBOB functions, suggesting a synergistic effect of broad diversity (RGF) and focused extension (MA-BBOB).
  • Landscape Features are Predictive: The study reinforces the idea that landscape features can effectively predict good algorithm configurations, even for problems not explicitly seen during training.

Key Results

  • Outperforming Defaults: The predicted optimal configurations from the NN models consistently outperformed the off-the-shelf default configurations for most BBOB functions in both 5d and 20d settings.
  • Competitive with Single Best Solver (SBS): In many cases, the predicted configurations were competitive with, and sometimes even better than, the Single Best Solver (SBS) – a configuration that performs well on average across all BBOB functions.
  • NNs vs. RFs: In some instances, NN models performed better than Random Forest models, which are often considered a strong baseline for landscape-aware ASP.
  • Dimensionality Matters: Performance improvements in 20d were generally less pronounced than in 5d, indicating that high dimensionality presents a challenge and suggests room for improvement.
  • Complex Functions are Challenging: The approach struggled with highly multi-modal functions (e.g., F16, F23), suggesting that current ELA features might not fully capture the complexity of such problems.

Limitations and Future Work

  • Limitations:
    • The performance on highly multi-modal functions is limited, possibly due to the inability of current ELA features to capture their complex landscape characteristics.
  • The performance gains in higher dimensions (20d) are less significant than in lower dimensions (5d).
  • While the estimated global optimum ($y_{opt}$) was robust, further confirmation is needed.
  • Future Work:
    • Expand the configuration search space to include more optimization algorithms and hyperparameters.
  • Investigate further fine-tuning of NN models (e.g., learning rate, batch size).
  • Explore alternative ELA feature pre-processing methods (e.g., standardization vs. normalization).
  • Develop more efficient methods for identifying appropriate RGFs for AAC.
  • Evaluate the approach on real-world expensive BBO problems to quantify its practical benefits.

Summary updated

Abstract

In landscape-aware algorithm selection problem, the effectiveness of feature-based predictive models strongly depends on the representativeness of training data for practical applications. In this work, we investigate the potential of randomly generated functions (RGF) for the model training, which cover a much more diverse set of optimization problem classes compared to the widely-used black-box optimization benchmarking (BBOB) suite. Correspondingly, we focus on automated algorithm configuration (AAC), that is, selecting the best suited algorithm and fine-tuning its hyperparameters based on the landscape features of problem instances. Precisely, we analyze the performance of dense neural network (NN) models in handling the multi-output mixed regression and classification tasks using different training data sets, such as RGF and many-affine BBOB (MA-BBOB) functions. Based on our results on the BBOB functions in 5d and 20d, near optimal configurations can be identified using the proposed approach, which can most of the time outperform the off-the-shelf default configuration considered by practitioners with limited knowledge about AAC. Furthermore, the predicted configurations are competitive against the single best solver in many cases. Overall, configurations with better performance can be best identified by using NN models trained on a combination of RGF and MA-BBOB functions.
BibTeX
@inproceedings{long2024landscape,
  author = {Fu Xing Long and Moritz Frenzel and Peter Krause and Markus Gitterle and Thomas Bäck and Niki van Stein},
  title = {{Landscape-Aware Automated Algorithm Configuration Using Multi-output Mixed Regression and Classification}},
  booktitle = {PPSN},
  year = {2024},
  url = {https://openreview.net/forum?id=ETwvE5JQNZ},
}
Figure