Which Surrogate Works for Empirical Performance Modelling? A Case Study with Differential Evolution
This work addresses the problem of expensive algorithm configuration for meta-heuristic users, but it is incremental as it compares existing methods on a specific algorithm.
The study evaluated four regression algorithms as surrogates to model the empirical performance of Differential Evolution (DE) based on its parameters, finding that some models better predict performance and approximate parameter landscapes than others.
It is not uncommon that meta-heuristic algorithms contain some intrinsic parameters, the optimal configuration of which is crucial for achieving their peak performance. However, evaluating the effectiveness of a configuration is expensive, as it involves many costly runs of the target algorithm. Perhaps surprisingly, it is possible to build a cheap-to-evaluate surrogate that models the algorithm's empirical performance as a function of its parameters. Such surrogates constitute an important building block for understanding algorithm performance, algorithm portfolio/selection, and the automatic algorithm configuration. In principle, many off-the-shelf machine learning techniques can be used to build surrogates. In this paper, we take the differential evolution (DE) as the baseline algorithm for proof-of-concept study. Regression models are trained to model the DE's empirical performance given a parameter configuration. In particular, we evaluate and compare four popular regression algorithms both in terms of how well they predict the empirical performance with respect to a particular parameter configuration, and also how well they approximate the parameter versus the empirical performance landscapes.