Tuning Metaheuristics: A Machine Learning Perspective

Metaheuristics are a relatively new but already established approachto c- binatorial optimization. A metaheuristic is a generic algorithmic template that can be used for ?nding high quality solutions of hard combinatorial - timization problems. To arrive at a functioning algorithm, a metaheuristic needs to be con?gured: typically some modules need to be instantiated and someparametersneedto betuned.Icallthese twoproblems"structural"and "parametric" tuning, respectively. More generally, I refer to the combination of the two problems as "tuning". Tuning is crucial to metaheuristic optimization both in academic research andforpracticalapplications.Nevertheless,relativelylittle researchhasbeen devoted to the issue. This book shows that the problem of tuning a me- heuristic can be described and solved as a machine learning problem. Using the machine learning perspective, it is possible to give a formal de?nitionofthetuningproblemandtodevelopagenericalgorithmfortuning metaheuristics.Moreover,fromthemachinelearningperspectiveitispossible tohighlightsome?awsinthecurrentresearchmethodologyandtostatesome guidelines for future empirical analysis in metaheuristics research. This book is based on my doctoral dissertation and contains results I have obtained starting from 2001 while working within the Metaheuristics Net- 1 work. During these years I have been a?liated with two research groups: INTELLEKTIK, Technische Universitat Darmstadt, Darmstadt, Germany and IRIDIA, Universite Libre de Bruxelles, Brussels, Belgium. I am the- fore grateful to the research directors of these two groups: Prof. Wolfgang Bibel, Dr. Thomas Stutzle, Prof. Philippe Smets, Prof. Hugues Bersini, and Prof. Marco Dorigo.