Back to the program.
The relevance of tuning the parameters of metaheuristics
Paola Pellegrini
Ca' Foscari University
Dorsoduro 3825/E Venice
Italy
paolap@pellegrini.it

Abstract

Metaheuristics, such as tabu search and genetic algorithms, are widely used to tackle combinatorial optimization problems. The results reported in the literature are in general very encouraging. A metaheuristic is a set of general purpose and problem-independent concepts, often characterized by modular structures and a set of parameters. A metaheuristic can be easily turned into a fully functioning algorithm for a specific combinatorial optimization problem. This is done by choosing the suitable modules and adapting them to the specific contexts, by varying the values of the parameters, and possibly by coupling them with other procedures, such as a local search. Thanks to their versatile nature, metaheuristics can be used in two different contexts: fast implementation and high performance. In the former context, one can use a metaheuristic right out-of-the-box. This approach typically achieves fairly good results. In the latter context, one has to accept getting your hands dirty by pairing the algorithm to the problem. This involves carefully choosing the various modules and accurately selecting the values of the parameters. The results that can be obtained in this second case are usually very good, up to the state-of-the-art. It is this tuning phase that differentiates between the two contexts. In this study we analyze the impact of the tuning procedure F-Race on the performance of five well known metaheuristics: Tabu Search, Simulated Annealing, Evolutionary Algorithm, Iterated Local Search, Ant Colony Optimization. The problem we consider is the vehicle routing problem with stochastic demand. Our computational analysis confirms that the two contexts can be clearly distinguished.

Keywords

metaheuristics, vehicle routing problem with stochastic demand, tuning problem

References

  1. Birattari Mauro. (2004) The Problem of Tuning Metaheuristics, as seem from a machine learning perspective. Ph.D. Thesis. Universite' Libre de Bruxelles, Belgium.
  2. Bianchi Leonora, Birattari Mauro, Chiarandini Marco, Manfrin Max, Mastrolilli Monaldo, Paquete Luis, Rossi-Doria Olivia and Schiavinotto Tommaso. (2005) Hybrid metaheuristics for the vehicle routing problem with Ssochastic demand, Journal of Mathematical Modelling and Algorithms, . Accepted for publication.
  3. Pellegrini Paola and Birattari Mauro. (2005) The relevance of tuning the parameters of metaheuristics. In preparation.