Statistical methods for parameter fine-tuning of metaheuristics
Tutor / Supervisor
Juan Pérez, Angel Alejandro
Student
Calvet Liñán, Laura
Document type
Master thesis
Date
2014
rights
Open Access
Publisher
Universitat de Barcelona
UPCommons
Abstract
Metaheuristics are an approximate method widely used to solve many hard optimization problems in a multitude of fields. They depend on a variable number of parameters. Despite the fact that they are usually capable of finding good solutions within a reasonable time, the difficulty in selecting appropriate values for their parameters causes a loss of efficiency, as it normally requires much time, skills and experience. This master degree s thesis provides a survey of the main approaches developed in the last decade to tackle the problem of choosing a good set of parameter values, called the Parameter Setting Problem, and compares them from a methodological point of view focusing on the statistical procedures used so far by the scientific community. This analysis is accompanied by a proposal of a general methodology. The results of applying it to fine-tuning the parameters of a hybrid algorithm, which combines Biased Randomization with the Iterated Local Search metaheuristic, for solving the Multi-depot Vehicle Routing Problem are also reported. The computational experiment shows promising results and the need / suitability of further investigations based on a wider range of statistical learning techniques. Along these same lines, different suggestions for future work are described. In addition, this work highlights the importance of statistics in operations research giving a real-world example.
Participating teacher
- Juan Pérez, Angel Alejandro