A Gender-Based Genetic Algorithm

A problem that is inherent to the development and efficient use of solvers is that of tuning parameters. The CP community has a long history of ad- dressing this task automatically. We propose a robust, inherently parallel genetic algorithm for the problem of configuring solvers automatically. In order to cope with the high costs of evaluating the fitness of individuals, we introduce a gender separation whereby we apply different selection pressure on both genders. Exper-

imental results on a selection of SAT solvers show significant performance and robustness gains over the current state-of-the-art in automatic algorithm configu- ration. 1 Introduction We consider the problem of automatic solver configuration. Practically all solvers have parameters that are partly fixed by the programmer and partly set by the user. In recent years, systems have been devised which automate the task of tuning parameters for a given set of training instances that are assumed to represent typical instances for the target algorithm. There are several motivations for such an automation, the first being that it is of course time consuming to tune parameters and it may lead to better results when leaving the configuration of solvers to a computer rather than doing it by hand. Moreover, it is conceivable that the existence of an effective tuning environment will cause algorithm developers to parameterize more aspects of their algorithms and thus leave more freedom for algorithmic solutions that are automatically tailored to the problems of individual users. In particular, many of the SAT solvers that are available today have parameters which cannot be set through the command line. These parameters have been fixed to values that the developers have found beneficial without knowledge about the particular instances a user may want to use the solver for. Automatic parameter tuning allows solvers to adapt to the final environment in which they need to perform. After being shipped, rather than relying on default parameters, an algorithm can be star This work was partly supported by the projects TIN2007-68005-C04-04 and TIN2006-15662- C02-02 funded by the MEC, and by the the National Science Foundation through the Ca- reer: Cornflower Project (award number 0644113). I.P. Gent (Ed.): CP 2009, LNCS 5732, pp. 142–157, 2009. c©Springer-Verlag Berlin Heidelberg 2009 A Gender-Based Genetic Algorithm for the Automatic Configuration of Algorithms 143 tuned automatically for the common tasks it is actually used for, and without requiring the user to learn about the algorithm parameters. For this very reason, Cplex 11 now comes with an automatic performance tuning tool. Another argument for automatic solver configuration regards our own science: when we re-implement algorithms to conduct experimental comparisons with competing ap- proaches, it is not unreasonable to assume that scientists spend much more time tuning their own algorithm than the algorithms of their competitors. A fair comparison could be achieved if all algorithms were tuned by an independent system. That...

Website: cs.brown.edu | Filesize: -
No of Page(s): 16
Download A Gender-Based Genetic Algorithm for the ... - Brown University.pdf