Strategies for the Parallel Implementation of Metaheuristics

Van-Dat Cung (Van-Dat.Cungprism.uvsq.fr)
Simone Martins (simoneinf.puc-rio.br)
Celso Ribeiro (celsoinf.puc-rio.br)
Catherine Roucairol (Catherine.Roucairolprism.uvsq.fr)

Abstract: Parallel implementations of metaheuristics appear quite naturally as an effective alternative to speed up the search for approximate solutions of combinatorial optimization problems. They not only allow solving larger problems or finding improved solutions with respect to their sequential counterparts, but they also lead to more robust algorithms. We review some trends in parallel computing and report recent results about linear speedups that can be obtained with parallel implementations using multiple independent processors. Parallel implementations of tabu search, GRASP, genetic algorithms, simulated annealing, and ant colonies are reviewed and discussed to illustrate the main strategies used in the parallelization of different metaheuristics and their hybrids.

Keywords: Metaheuristics, Parallelism

Category 1: Combinatorial Optimization (Meta Heuristics )

Citation: To appear in Essays and Surveys in Metaheuristics (C.C. Ribeiro and P. Hansen, editors), Kluwer, 2001.

Download: [Postscript]

Entry Submitted: 05/03/2001
Entry Accepted: 05/03/2001
Entry Last Modified: 05/03/2001

Modify/Update this entry