Project Topics
Get Complete Project Material File(s) Now! »
Personalizing Performance Regression Models to Black-Box Optimization Problems [GECCO’21b]
This paper focuses on analyzing the possibility of personalizing performance regression models to specific types of optimization problems. Accurately predicting the performance of different optimization algorithms for previously unseen problem instances is crucial for high-performing algorithm selection techniques. In the context of numerical black-box optimization, researchers and practitioners typically stick to standard choices of the machine learning models as a basis for algorithms selectors.
These are, most frequently, off-the-shelf tools, which can seem rather naïve from the machine learning viewpoint. Thus, we are presented with a risk of not achieving thefull potential of a machine learning technique if we disregard proper investigation of its actual suitability for the problems we encounter.
With this study, we bring to the attention of evolutionary computation community one way of increasing the suitability of machine learning tools for the problems at hand. Instead of aiming for a single model that works well across a whole set of possibly diverse problems, our personalized regression approach acknowledges that different models may suit different types of problems. Going one step further, we also investigate the impact of selecting not a single regression model per problem, but personalized ensembles. We test our approach on predicting the performance of numerical optimization heuristics on the BBOB benchmark suite and we show that this approach opens promising avenues for further increasing the regression quality and, consequently, the accuracy of the algorithm selector built atop.
Adaptive Landscape Analysis [GECCO’19]
This paper takes a deeper dive into the underlying properties of different black-box optimization problems. In order for the optimization process to be as efficient as possible, one must first recognize the nature of the problem at hand and then proceed to choose the algorithm exhibiting the best performance for that type of problem. A standard way of identifying similarities and differences between various problems lies in ELA feature extraction and representation of the problem via these numerical values.
We present here some first steps towards adaptive landscape analysis. Our approach is aimed at taking a closer look into how feature values evolve during the optimization process and whether this local feature information can be used to discriminate between different problems. The motivation of our work is to understand if and how one could exploit the information provided by local features to get a step closer to dynamic (also known as online) algorithm selection. The idea behind it is fairly simple, yet extremely promising in terms of gaining efficiency and performance quality; the choice of an algorithm is tracked and adapted during the optimization process, allowing for switching from one algorithm to a better suited one. The long-term goal of this analysis is to leverage local landscape information for adjusting the choice of the algorithm on the fly, i.e., during the optimization process itself.
We show that the local feature values differ drastically compared to the global ones, which gives a promising insight into how the problem landscape looks locally, as seen by the algorithm. These insights could turn out to be crucial for ultimately designing an algorithm selector model that operates in an online fashion.
Towards Feature-Based Performance Regression Using Trajectory Data [EvoAPPs’21]
The final paper investigates a novel framework where the performance regression model is based on the information obtained via a search trajectory of a default solver. The pipeline of this trajectory-based approach is shown in Figure 2.2. Existing ELAbased algorithm selection approaches require the approximation of problem features based on a significant number of samples. They are typically selected through uniform sampling or Latin hypercube designs, and they are computed in a problem-specific fashion, independently of the optimization process that occurs later. The evaluation of these points is costly, and the benefit of an ELA-based algorithm selection over a default algorithm must therefore be significant in order to pay it off.
One could hope to by-pass the evaluations for the feature approximations by using the samples that a default algorithm would anyway perform, i.e., by using the points of the default algorithm’s trajectory. We analyze here how well such an approach can work. Concretely, we test how accurately trajectory-based ELA approaches can predict the final solution quality of the particular default solver (the CMA-ES algorithm) after a fixed budget of function evaluations.
We observe that the loss of trajectory-based predictions can be surprisingly small, even negligible, compared to the classical global sampling approach, if the remaining budget for which solution quality shall be predicted is not too large. This important result fortifies our vision of trajectory-based algorithm selection being the future of dynamic algorithm selection. It goes without saying that a large pool of open questions are yet to be answered. Nonetheless, we note that the untapped potential within this research direction remains the central point of our research efforts in the imminent future.
Per-Instance Algorithm Selection
Many prominent optimization problems have long been considered to be central specimens in active research efforts when it comes to developing new solving strategies. For those well-analyzed and well-understood problems, a range of high-performing algorithms is available, but there is typically no single algorithm that dominates all others on all possible instances of the problem at hand. Instead, different algorithms achieve best performance on different problem instances, which is known as performance complementarity [BKK+16; KHN+19; Kot14; Ric76; Smi09]. This long-existing observation has naturally led to the necessity of appropriate algorithm selection for the problem instances we can face. Given an optimization problem, its specific instance that needs to be solved, and a set of algorithms that can be used to solve it, the so-called per-instance algorithm selection (PIAS) problem arises: how to determine which of those algorithms can be expected to perform best on that particular instance?.
The (per-instance) algorithm selection problem has historically been tackled manually, using expert knowledge to make algorithm recommendations. Addressing the question of reducing bias which is inherent to the manual approach was soon deemed indispensable; it paved the way towards the concept of automating this process by means of various tools available in related fields. To this day, automated algorithm selection has been steadily gaining prominence, resulting in a large body of work [CV97; KT19; LHH+15; LNA+03; XHH+08; XHH+12]. From high-level, passive strategies that are based on choosing an algorithm as a function of a priori available features [BS04; LMP+20; MRW+21], through active, bet-and-run approaches that consist of running several algorithms and stopping all but the best-performing one (i.e., per-set algorithm selection) [MBT+11; ME13; MKH15], the research focus has ultimately turned towards establishing efficient landscape-aware algorithm selection models that operate using low-level problem features, which are computed beforehand [BMT+12; CDL+21; HKV19; KHN+19; KT19; MKH12].
From Performance Regression to Algorithm Selection
This thesis makes use of the prediction of algorithm performance as a foundation upon which the algorithm selection models are built. This pipeline component (illustrated in Figure 1.2) relies on machine learning techniques. As briefly mentioned in Chapter 5, general approaches differ based on the type of learning model. Supervised learning methods, such as classification and regression, are the ones coupled with the information about landscape (ELA) features to make predictions about how well certain algorithms will perform on certain problem instances. To this end, we employ ELA-based regression, as we are concerned not only in knowing which algorithm is recommended, but also in further interpreting and comprehending the actual behavior of algorithms. Regression models allow for keeping track of precise magnitudes of differences between performances of different algorithms. This interpretability aspect is especially important due to settings that include portfolios of very similar algorithms.
With respect to the available regression techniques, a general state-of-the-art recommendation highlights random forests as a method that outperforms other typically used regressors in the context of automated algorithm selection [HXH+14]. Random forests [Bre01] are ensemble-based meta-estimators that fit decision trees on various sub-samples of the data set and use averaging to improve the predictive accuracy and to control over-fitting. We adopt them as a principal regression model going forward, but we also investigate the potential of other models under fixed-budget circumstances (cf. Chapter 7).
Table of contents :
Abstract
Résumé
Acknowledgments
Contents
1 Introduction
1.1 Algorithm Selection
1.2 Exploratory Landscape Analysis
1.3 Key Objective of the Thesis
1.4 Outline of the Thesis
2 Contributions of the Thesis
2.1 Combining Fixed-Budget Regression Models
2.2 Impact of Hyper-Parameter Tuning
2.3 Personalized Performance Regression
2.4 Adaptive Landscape Analysis
2.5 Trajectory-Based Algorithm Selection
I The Background
3 Black-Box Optimization
3.1 Black-Box Optimization Algorithms
3.1.1 CMA-ES
3.1.2 Modular CMA-ES
3.1.3 Additional Algorithms
3.2 Algorithm Performance Measures
3.3 Problem Collections
3.3.1 BBOB Test Suite
4 Exploratory Landscape Analysis
4.1 ELA Features
4.2 Choice of Features
4.3 Feature Computation
5 Algorithm Selection
5.1 Per-Instance Algorithm Selection
5.2 From Performance Regression to Algorithm Selection
5.3 State of the Art
5.4 Performance Assessment of Algorithm Selectors
II Contributions
6 Combining Fixed-Budget Regression Model
6.1 Preliminaries
6.2 Fixed-Budget Performance Regression
6.2.1 Impact of Feature Selection
6.3 Fixed-Budget Algorithm Selection
6.3.1 Impact of the Threshold Value and the Feature Portfolio
6.3.2 Impact of the Algorithm Portfolio
6.3.3 Impact of the Sample Size for Feature Extraction
6.4 Conclusions
7 Impact of Hyper-Parameter Tuning
7.1 Preliminaires
7.2 Performance Regression Quality of Different Models
7.3 ELA-Based Algorithm Selection
7.4 Sensitivity Analyses
7.5 Conclusions
8 Personalized Performance Regression
8.1 Preliminaries
8.2 Personalized Machine Learning Models
8.3 Use-Case: ELA-Based Fixed-Budget Performance Regression
8.3.1 Experimental Setup
8.3.2 BIPOP-CMA-ES Performance Prediction
8.4 Conclusions
9 Adaptive Landscape Analysis
9.1 Preliminaries
9.2 “Zooming In” into the Landscapes
9.3 Conclusions
10 Trajectory-Based Performance Regression
10.1 Preliminaries
10.2 Supervised Machine Learning for Performance Regression
10.3 Comparison with Global Feature Values
10.4 Sensitivity Analyses
10.5 Conclusions
11 General Conclusions and Outlook
Bibliography
