Model-Based Genetic Algorithms for Algorithm Configuration

Automatic algorithm configurators are important practical tools for improving program performance measures, such as solution time or prediction accuracy. Local search approaches in particular have proven very effective for tuning algorithms. In sequential local search, the use of predictive models has proven beneficial for obtaining good tuning results. We study the use of non-parametric models in the context of population-based algorithm configurators. We introduce a new model designed specifically for the task of predicting high-performance regions in the parameter space. Moreover, we introduce the ideas of genetic engineering of offspring as well as sexual selection of parents. Numerical results show that model-based genetic algorithms significantly improve our ability to effectively configure algorithms automatically. Many algorithms have parameters that greatly affect their performance. These parameters allow algorithms to adapt to different usage scenarios and provide end users with greater flexibility in customizing software specifically for their needs. However, finding good parameters is difficult and timeconsuming because each evaluation of the algorithm being configured is expensive, often taking from seconds or hours to assess a single input (of which there are many). In comparison, typical local search approaches for standard benchmark problems are able to evaluate tens of thousands of solutions per second. Two types of configurators have emerged: non-model-based and model-based approaches. Non-model-based techniques generally rely on either an experimental design methodology, such as the case in CALIBRA [Adenso-Diaz and Laguna, 2006] and I/F-Race [Birattari et al., 2010], or a meta-heuristic as ParamILS [Hutter et al., 2009] or GGA [Ansotegui et al., 2009]. In contrast, model-based approaches like SMAC [Hutter et al., 2011] use machine learning in order to predict good parameterizations based on samples of the parameter space. We propose GGA++, an automatic algorithm configurator that harnesses Research partially supported by the Ministerio de Economı́a y Competividad research project TASSAT2: TIN2013-48031-C4-4-P. the power of model-based approaches within a non-modelbased genetic algorithm framework. 1 Gender-based Genetic Algorithm Configuration (GGA) GGA [Ansotegui et al., 2009] is a genetic algorithm-based approach to general algorithm configuration which has been used in practice for a wide array of applications, such as tuning solvers in SAT [Kadioglu et al., 2010]/MaxSAT [Ansótegui et al., 2014], machine reassignment [Malitsky et al., 2013a] and mixed-integer programming [Kadioglu et al., 2010]). We describe the key components of GGA, but refer readers to [Ansotegui et al., 2009] for further details.  GGA accepts a parameterized algorithm to be configured (called the target algorithm), a set of algorithm inputs, and a performance metric to be optimized. The performance metric can be the execution time of an algorithm or some value computed by the algorithm, for example, the result of a simulation or accuracy of a prediction. GGA then runs its specialized genetic algorithm that executes the target algorithm with different parameters in order to find a good setting. Once GGA has reached the target number of generations, the best parametrization found so far is returned.  A core idea in GGA is the partitioning of the population into a competitive and non-competitive population. The competitive population is directly evaluated on the target algorithm, whereas the non-competitive population simply acts as a source of diversity. This allows GGA to use strong intensification procedures on one part of the population while remaining diverse enough to avoid local optima.  A tournament-based selection mechanism is used for evaluating the competitive population. Tournaments are run on disjoint subsets of parameterizations in parallel on a subset of the instances. When tuning runtime, as soon as a set percentage of the parameterizations in a tournament are finished, all other participants in the tournament can be terminated. This saves significant amounts of CPU time that would otherwise be spent evaluating bad parameterizations. Genome representation: GGA represents parameterizations using an AND-OR tree in order to capture the dependencies between parameters. A node in the tree is a parameter or an AND node that binds multiple parameters together. Several sample trees are shown in Figure 1. In these particular Figure 1: The GGA recombination operator. trees, the root node is a categorical parameter that activates the left branch when it takes the value 0, and the right branch when it takes the value 1 (think of a parameter that chooses which subroutine is used, with parameters in the left subtree affecting only subroutine ’0’ and parameters only affecting subroutine ’1’ in the right tree). Recombination and mutation: The crossover operator in GGA takes two genomes, one from the competitive and one from the non-competitive population. The competitive genome is a tournament winner, while the other genome is drawn uniformly at random from the non-competitive population. The crossover process is shown in Figure 1, and it can be viewed as a hybrid of the traditional multi-point and uniform crossovers that considers parameter dependencies. GGA performs mutation simply by selecting random parameter settings and replacing them with values drawn from either a Gaussian (for discrete and continuous parameters) or a uniform (for categorical parameters) distribution. 2 Non-Parametric Models for Predicting High-Performance Parameter Regions GGA evaluates a parameter setting by running the target algorithm with the parameter setting on a collection of training instances. That is, we conduct a black box optimization with an extremely expensive to run black box. One idea to improve optimization performance is to reduce the high costs of querying the black box directly. To this end, the idea of trying to learn a so-called “surrogate model” that is faster to evaluate and that “approximates” the actual black box has been introduced. The so-called response surface methodology [Box and Wilson, 1951], e.g., fits a second degree polynomial to the observed black box output and then optimizes over that polynomial to predict an optimal input for the black box. A state-of-the-art sequential local search algorithm configurator that uses a surrogate model is SMAC [Hutter et al., 2011]. SMAC directly evaluates algorithm performance for some initial parameter settings and then uses this experience to train a random forest that predicts expected algorithm performance over the parameter inputs. Importantly, SMAC also computes the model’s variance/uncertainty in its predictions. As a next point for direct evaluation of the algorithm on the training inputs, SMAC chooses a parametrization for which the model predicts high performance plus uncertainty. The model is re-trained using this information, along with several random parameterizations that are also directly evaluated. A new parametrization is then chosen based on the updated model, and this process is repeated until the designated CPU time for configuration is exhausted. The use of variance in SMAC is very important. First, this leads to an improvement of the model itself by favoring points where the model has little “confidence” in its own predictions. Secondly, a vanilla random forest can never return predictions that exceed the most highly rated prior experience. Consequently, if variance was not used to score new parametrization candidates the system could repeatedly re-evaluate the same parameter settings. 3 Surrogate Models for Genetic Algorithms The core idea of this paper is to study the use of surrogate models in genetic algorithms for algorithm configuration. In particular, 1. How can surrogate models help find high-quality solutions faster in the context of a population-based local search approach? 2. Are there surrogate models that are more suited for predicting high-performance parameterizations? There is already work on combining evolutionary and genetic algorithms with model-based approaches (e.g., [Rasheed and Hirsh, 2000; Jin, 2011]). These hybrids employ vanilla machine learning models as surrogates. They consider the various uses of surrogates within genetic algorithms and decide when to re-train the model. In this work we devise specialized surrogate models and tightly integrate them within a genetic algorithm. The core operation that defines the next fitness evaluations in a genetic algorithm is the crossover, possibly in combination with mutation. Usually, the crossover method is randomized in some fashion. We introduce the idea of using a surrogate model for predicting offspring performance and to “genetically engineer” offspring that are expected to perform better. Note that changing the way new parameterizations are introduced into the population can have a drastic effect on the trajectory of the entire search, as this modifies the delicate balance of exploration vs. exploitation. Within GGA, the question then becomes what percentage of offspring should be selected by the model and what percentage should be produced by the existing crossover operator, and how sufficiently high levels of diversity in the gene pool can be maintained. Another idea we introduce is that of model-based “sexual selection.” As outlined above, GGA maintains two populations, one that competes for the right of mating, and one within which individuals mate with equal probability. Based on the assessment of a surrogate model, winning competitive individuals could choose a mating partner based on some definition of their “attractiveness.” Regarding the second question posed above, based on the developments in algorithm portfolios, where non-parametric, or at least low-bias models, have led to the currently best performing approaches [Xu et al., 2012; Mal