ABSTRACT
Providing tools for algorithm tuning (and the related statistical analysis) is the main topic of this tutorial. This tutorial provides the necessary background for performing algorithm tuning with state-of-the-art tools. We will discuss pros and cons of manual, interactive, and automatic tuning of randomized algorithms such as Genetic Algorithms, Differential Evolution, Particle Swarm, and Evolution Strategies. Moreover, we highlight the important components of experimental work such as proper setup, visualization, and reporting and refer to the most prominent mistakes that may occur, giving examples for failed and successful experiments.
The Sequential Parameter Optimization Toolbox (SPOT) is introduced as an example, being freely available via CRAN (free R package server network), see http://cran.r-project.org/web/packages/SPOT/index.html
Other tuning approaches such as F-Race, REVAC and ParamILS will be discussed as well.
- Anne Auger and Nikolaus Hansen. Performance Evaluation of an Advanced Local Search Evolutionary Algorithm. In B. McKay et al., editors, Proc. 2005 Congress on Evolutionary Computation (CEC'05), Piscataway NJ, 2005. IEEE Press.Google ScholarCross Ref
- Thomas Bartz-Beielstein. Experimental Research in Evolutionary Computation--The New Experimentalism. Natural Computing Series. Springer, Berlin, Heidelberg, New York, 2006. Google ScholarDigital Library
- Thomas Bartz-Beielstein. Sequential parameter optimization--an annotated bibliography. Technical Report 04/2010, Institute of Computer Science, Faculty of Computer Science and Engineering Science, Cologne University of Applied Sciences, Germany, 2010.Google Scholar
- Thomas Bartz-Beielstein, Marco Chiarandini, Luis Paquete, and Mike Preuss, editors. Empirical Methods for the Analysis of Optimization Algorithms. Springer, Berlin, Heidelberg, New York, 2010. Google ScholarDigital Library
- Thomas Bartz-Beielstein, Christian Lasarczyk, and Mike Preuß. Sequential parameter optimization. In B. McKay et al., editors, Proceedings 2005 Congress on Evolutionary Computation (CEC'05), Edinburgh, Scotland, volume 1, pages 773--780, Piscataway NJ, 2005. IEEE Press.Google ScholarCross Ref
- Thomas Bartz-Beielstein, Boris Naujoks, Tobias Wagner, and Simon Wessing. In Hermann Locarek-Junge and Claus Weihs, editors, Proceedings 11th IFCS Internat. Conference 2009. Classification as a tool for research, Dresden, 2009.Google Scholar
- Thomas Bartz-Beielstein, Konstantinos E. Parsopoulos, and Michael N. Vrahatis. Design and analysis of optimization algorithms using computational statistics. Applied Numerical Analysis and Computational Mathematics (ANACM), 1(2):413--433, 2004.Google Scholar
- Oliver Flasch, Thomas Bartz-Beielstein, Artur Davtyan, Patrick Koch, Wolfgang Konen, Tosin Daniel Oyetoyan, and Michael Tamutan. Comparing ci methods for prediction models in environmental engineering. Technical Report 02/2010, Institute of Computer Science, Faculty of Computer Science and Engineering Science, Cologne University of Applied Sciences, Germany, 2010.Google Scholar
- Thomas Fober, Marco Mernberger, Gerhard Klebe, and Eyke Hüllermeier. Evolutionary construction of multiple graph alignments for the structural analysis of biomolecules. Bioinformatics, 25(16):2110--2117, 2009. Google ScholarDigital Library
- Thomas Fober. Experimentelle Analyse Evolutionärer Algorithmen auf dem CEC 2005 Testfunktionensatz. Master's thesis, Universität Dortmund, Germany, 2006.Google Scholar
- Frank Hutter, Thomas Bartz-Beielstein, Holger Hoos, Kevin Leyton-Brown, and Kevin P. Murphy. Sequential model-based parameter optimisation: an experimental investigation of automated and interactive approaches empirical methods for the analysis of optimization algorithms. In Thomas Bartz-Beielstein, Marco Chiarandini, Luis Paquete, and Mike Preuss, editors, Empirical Methods for the Analysis of Optimization Algorithms, pages 361--414. Springer, Berlin, Heidelberg, New York, 2009.Google Scholar
- Frank Henrich, Claude Bouvy, Christoph Kausch, Klaus Lucas, Mike, Preuß, Günter Rudolph, and Peter Roosen. Economic optimization of non-sharp separation sequences by means of evolutionary algorithms. Computers and Chemical Engineering, 32(7):1411--1432, 2008.Google ScholarCross Ref
- F. Hutter, H. H. Hoos, K. Leyton-Brown, and K. P. Murphy. Time-bounded sequential parameter optimization. In Proc. of LION-10, 2010. To appear. Google ScholarDigital Library
- Nikolaus Hansen and Stefan Kern. Evaluating the cma evolution strategy on multimodal test functions. In X. Yao, H.-P. Schwefel, et al., editors, Parallel Problem Solving from Nature -- PPSN VIII, Proc. Eighth Int'l Conf., Birmingham, pages 282--291, Berlin, 2004. Springer.Google Scholar
- Oliver Kramer, Bartek Gloger, and Andreas Goebels. An experimental analysis of evolution strategies and particle swarm optimisers using design of experiments. In Proceedings of the 9th annual conference on Genetic and evolutionary computation, GECCO '07, pages 674--681, New York, NY, USA, 2007. ACM. Google ScholarDigital Library
- J. P. C. Kleijnen. Design and analysis of simulation experiments. Springer, New York NY, 2008. Google ScholarDigital Library
- W. Konen, T. Zimmer, and T. Bartz-Beielstein. Optimierte Modellierung von Füllständen in Regenüberlaufbecken mittels CI-basierter Parameterselektion Optimized Modelling of Fill Levels in Stormwater Tanks Using CI-based Parameter Selection Schemes. at-Automatisierungstechnik, 57(3):155--166, 2009.Google ScholarCross Ref
- Christian W. G. Lasarczyk. Genetische Programmierung einer algorithmischen Chemie. PhD thesis, Technische Universität Dortmund, 2007.Google Scholar
- Christian W. G. Lasarczyk and Wolfgang Banzhaf. Total synthesis of algorithmic chemistries. In GECCO '05: Proceedings of the 2005 conference on Genetic and evolutionary computation, pages 1635--1640, New York, NY, USA, 2005. ACM. Google ScholarDigital Library
- Jörn Mehnen, Thomas Michelitsch, Christian Lasarczyk, and Thomas Bartz-Beielstein. Multi-objective evolutionary design of mold temperature control using DACE for parameter optimization. International Journal of Applied Electromagnetics and Mechanics, 25(1--4):661--667, 2007.Google ScholarCross Ref
- D. C. Montgomery. Design and Analysis of Experiments. Wiley, New York NY, 5th edition, 2001.Google Scholar
- Boris Naujoks, Domenico Quagliarella, and Thomas Bartz-Beielstein. Sequential parameter optimisation of evolutionary algorithms for airfoil design. In G. et al. Winter, editor, Proc. Design and Optimization: Methods and Applications, (ERCOFTAC'06), pages 231--235. University of Las Palmas de Gran Canaria, 2006.Google Scholar
- Niels Hendrik Pothmann. Kreuzungsminimierung für k-seitige Buchzeichnungen von Graphen mit Ameisenalgorithmen. Master's thesis, Universität Dortmund, Germany, 2007.Google Scholar
- Mike Preuss. Adaptability of algorithms for real-valued optimization. In Mario Giacobini et al., editors, Applications of Evolutionary Computing, EvoWorkshops 2009. Proceedings, volume 5484 of Lecture Notes in Computer Science, pages 665--674, Berlin, 2009. Springer. Google Scholar
- Mike Preuss, Günter Rudolph, and Feelly Tumakaka. Solving multimodal problems via multiobjective techniques with Application to phase equilibrium detection. In Proceedings of the International Congress on Evolutionary Computation (CEC2007). Piscataway (NJ): IEEE Press. Im Druck, 2007.Google ScholarCross Ref
- Günter Rudolph, Mike Preuss, and Jan Quadflieg. Two-layered surrogate modeling for tuning optimization metaheuristics. Algorithm Engineering Report TR09-2-005, Faculty of Computer Science, Algorithm Engineering (Ls11), Technische Universität Dortmund, Germany, September 2009.Google Scholar
- Selmar K. Smit and A. E. Eiben. Comparing Parameter Tuning Methods for Evolutionary Algorithms. In IEEE Congress on Evolutionary Computation (CEC), pages 399--406, May 2009. Google ScholarDigital Library
- Heike Trautmann and Jörn Mehnen. Statistical methods for improving multi-objective evolutionary optimisation. International Journal of Computational Intelligence Research (IJCIR), 5(2):72--78, 2009.Google Scholar
- Marko Tosic. Evolutionäre Kreuzungsminimierung. Diploma thesis, University of Dortmund, Germany, January 2006.Google Scholar
- L.G. Volkert. Investigating ea based training of hmm using a sequential parameter optimization approach. In Gary G. Yen, Simon M. Lucas, Gary Fogel, Graham Kendall, Ralf Salomon, Byoung-Tak Zhang, Carlos A. Coello Coello, and Thomas Philip Runarsson, editors, Proceedings of the 2006 IEEE Congress on Evolutionary Computation, pages 2742--2749, Vancouver, BC, Canada, 16--21 July 2006. IEEE Press.Google Scholar
- Yu Yi. Fuzzy Operator Trees for Modeling Utility Functions. PhD thesis, Philipps-Universität Marburg, 2008.Google Scholar
Index Terms
- Automatic and interactive tuning of algorithms
Recommendations
Comparing parameter tuning methods for evolutionary algorithms
CEC'09: Proceedings of the Eleventh conference on Congress on Evolutionary ComputationTuning the parameters of an evolutionary algorithm (EA) to a given problem at hand is essential for good algorithm performance. Optimizing parameter values is, however, a non-trivial problem, beyond the limits of human problem solving. In this light it ...
Tuning of Multiple Parameter Sets in Evolutionary Algorithms
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016Evolutionary optimization algorithms typically use one or more parameters that control their behavior. These parameters, which are often kept constant, can be tuned to improve the performance of the algorithm on specific problems. However, past studies ...
Automatic tuning of MPI runtime parameter settings by using machine learning
CF '10: Proceedings of the 7th ACM international conference on Computing frontiersMPI implementations provide several hundred runtime parameters that can be tuned for performance improvement. The ideal parameter setting does not only depend on the target multiprocessor architecture but also on the application, its problem and ...
Comments