Yasha Pushak
Holger H. Hoos
ABSTRACT
Automated algorithm configuration procedures such as SMAC, GGA++ and irace can often find parameter configurations that substantially improve the performance of state-of-the-art algorithms for difficult problems - e.g., a three-fold speedup in the running time required by EAX, a genetic algorithm, to find optimal solutions to a set of widely studied TSP instances. However, it is usually recommended to provide these methods with running time budgets of one or two days of wall-clock time as well as dozens of CPU cores. Most general-purpose algorithm configuration methods are based on powerful meta-heuristics that are designed for challenging and complex search landscapes; however, recent work has shown that many algorithms appear to have parameter configuration landscapes with a relatively simple structure. We introduce the golden parameter search (GPS) algorithm, an automatic configuration procedure designed to exploit this structure while optimizing each parameter semi-independently in parallel. We compare GPS to several state-of-the-art algorithm configurators and show that it often finds similar or better parameter configurations using a fraction of the computing time budget across a broad range of scenarios spanning TSP, SAT and MIP.
Supplemental Material
Available for Download
Supplemental material.
- Carlos Ansótegui, Yuri Malitsky, Horst Samulowitz, Meinolf Sellmann, and Kevin Tierney. 2015. Model-Based Genetic Algorithms for Algorithm Configuration. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015). 733--739.Google Scholar
- Carlos Ansótegui, Meinolf Sellmann, and Kevin Tierney. 2009. A Gender-Based Genetic Algorithm for the Automatic Configuration of Algorithms. In Proceedings of the Fifteenth International Conference on Principles and Practice of Constraint Programming (CP 2009). 142--157.Google ScholarCross Ref
- Prasanna Balaprakash, Mauro Birattari, and Thomas Stützle. 2007. Improvement strategies for the F-Race algorithm: Sampling design and iterative refinement. In International workshop on hybrid metaheuristics. Springer, 108--122.Google ScholarCross Ref
- Thomas Bartz-Beielstein, Christian WG Lasarczyk, and Mike Preuss. 2005. Sequential parameter optimization. In 2005 IEEE congress on evolutionary computation, Vol. 1. IEEE, 773--780.Google Scholar
- Armin Biere. 2017. CaDiCaL, Lingeling, Plingeling, Treengeling and YalSAT Entering the SAT Competition 2017. In Proceedings of SAT Competition 2017: Solver and Benchmark Descriptions. 14--15.Google Scholar
- Mauro Birattari, Thomas Stützle, Luis Paquete, and Klaus Varrentrapp. 2002. A Racing Algorithm for Configuring Metaheuristics. In Proceedings of the Third Genetic and Evolutionary Computation Conference (GECCO 2002). 11--18.Google Scholar
- Mauro Birattari, Zhi Yuan, Prasanna Balaprakash, and Thomas Stützle. 2010. F-Race and iterated F-Race: An overview. In Experimental methods for the analysis of optimization algorithms. Springer, 311--336.Google Scholar
- Leslie Pérez Cáceres, Manuel López-Ibáñez, Holger H. Hoos, and Thomas Stützle. 2017. An experimental study of adaptive capping in irace. In Proceedings of the Eleventh International Conference on Learning and Intelligent Optimization (LION 2017). Springer, 235--250.Google ScholarCross Ref
- IBM Corp. 2020. IBM ILOG CPLEX Optimizer. https://www.ibm.com/analytics/data-science/prescriptive-analytics/cplex-optimizer, Last accessed on 2020-02-03. (2020).Google Scholar
- Stefan Falkner, Marius Lindauer, and Frank Hutter. 2015. SpySMAC: Automated configuration and performance analysis of SAT solvers. In International Conference on Theory and Applications of Satisfiability Testing (SAT 2015). 215--222.Google ScholarCross Ref
- Keld Helsgaun. 2000. An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research 126 (2000), 106--130.Google ScholarCross Ref
- Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown. 2011. Bayesian optimization with censored response data. In Procedings of 2011 NeurIPS workshop on Bayesian Optimization, Experimental Design, and Bandits.Google Scholar
- Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown. 2011. Sequential modelbased optimization for general algorithm configuration. In Proceedings of the Fifth International Conference on Learning and Intelligent Optimization (LION 2011). 507--523.Google ScholarDigital Library
- Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown. 2012. Parallel Algorithm Configuration. In Proceedings of Sixth International Conference on Learning and Intelligent Optimization (LION 2012). 55--70.Google ScholarCross Ref
- Frank Hutter, Holger H. Hoos, Kevin Leyton-Brown, and Kevin Murphy. 2010. Time-bounded sequential parameter optimization. In Proceedings of the Fourth International Conference on Learning and Intelligent Optimization (LION 2010). Springer, 281--298.Google ScholarDigital Library
- Frank Hutter, Holger H. Hoos, Kevin Leyton-Brown, and Thomas Stützle. 2009. ParamILS: an automatic algorithm configuration framework. Journal of Artificitial Intelligence Research 36 (2009), 267--306. Issue 1.Google ScholarDigital Library
- Frank Hutter, Holger H. Hoos, and Thomas Stützle. 2007. Automatic algorithm configuration based on local search. In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence (AAAI 2007), Vol. 7. 1152--1157.Google Scholar
- Frank Hutter, Manuel López-Ibáñez, Chris Fawcett, Marius Lindauer, Holger H. Hoos, Kevin Leyton-Brown, and Thomas" Stützle. 2014. AClib: A Benchmark Library for Algorithm Configuration. In Proceedings of the Fourteenth International Conference on Learning and Intelligent Optimization (LION 2014). 36--40.Google ScholarCross Ref
- Jack Kiefer. 1953. Sequential minimax search for a maximum. Proceedings of the American mathematical society 4, 3 (1953), 502--506.Google ScholarCross Ref
- Marius Lindauer and Frank Hutter. 2018. Warmstarting of model-based algorithm configuration. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI 2018). 1355--1362.Google Scholar
- Manuel López-Ibáñez, Jérémie Dubois-Lacoste, Leslie P. Cáceres, Thomas Stützle, and Mauro Birattari. 2016. The irace package: Iterated Racing for Automatic Algorithm Configuration. Operations Research Perspectives 3 (2016), 43--58.Google ScholarCross Ref
- Yuichi Nagata and Shigenobu Kobayashi. 2013. A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem. Institute for Operations Research and the Management Sciences Journal on Computing 25, 2 (2013), 346--363.Google ScholarDigital Library
- William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. 1992. Golden section search in one dimension. Numerical Recipes in C: The Art of Scientific Computing (1992).Google ScholarDigital Library
- Yasha Pushak and Holger H. Hoos. 2018. Algorithm configuration landscapes: More benign than expected?. In Proceedings of the Fifteenth International Conference on Parallel Problem Solving from Nature (PPSN 2018). Springer, 271--283.Google ScholarCross Ref
- James Styles and Holger H. Hoos. 2013. Ordered Racing Protocols for Automatically Configuring Algorithms for Scaling Performance. In Proceedings of the Fifteenth Conference on Genetic and Evolutionary Computation (GECCO 2013). ACM, 551--558.Google ScholarDigital Library
- James Styles, Holger H. Hoos, and Martin Müller. 2012. Automatically Configuring Algorithms for Scaling Performance. In Proceedings of the Sixth International Conference on Learning and Intelligent Optimization (LION 2012). 205--219.Google ScholarCross Ref
Index Terms
- Golden parameter search: exploiting structure to quickly configure parameters in parallel
Recommendations
Analysing differences between algorithm configurations through ablation
Developers of high-performance algorithms for hard computational problems increasingly take advantage of automated parameter tuning and algorithm configuration tools, and consequently often create solvers with many parameters and vast configuration ...
Algorithm Configuration via Continuously Racing: Preliminary Results
GECCO '23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary ComputationAutomatic algorithm configuration procedures aim at supporting the design and application of optimization algorithms by providing specialized tools to automatically adjust their parameters to use the available computational resources effectively. The ...
Automated configuration of genetic algorithms by tuning for anytime performance: hot-off-the-press track at GECCCO 2022
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference CompanionThis paper summarizes our work "Automated Configuration of Genetic Algorithms by Tuning for Anytime Performance", to appear in IEEE Transactions on Evolutionary Computation.
Finding the best configuration of algorithms' hyperparameters for a given ...
Comments