On Metaheuristic Algorithms for Combinatorial Optimization Problems

Mutsunori YAGIURA and Toshihide IBARAKI

Abstract
Metaheuristic algorithms are widely recognized as one of the most practical approaches for combinatorial optimization problems. Among representative metaheuristics are genetic algorithm, simulated annealing, tabu search and so on. In this paper, we explain essential ideas used in such metaheuristic algorithms within a generalized framework of local search. We then conduct numerical experiment of metaheuristic algorithms using rather simple implementations, to observe general tendencies of their performance. From these results, we propose a few recommendations about the use of metaheuristics as simple optimization tools. We also mention some advanced techniques to enhance the ability of metaheuristics. Finally, we summarize some theoretical results on metaheuristic algorithms.

Keywords: combinatorial optimization problem, approximate algorithm, metaheuristics, local search, genetic algorithm, simulated annealing, tabu search.

Systems and Computers in Japan, Vol. 32, Issue 3, 2001, pp. 33-55.
(The translation of the following paper: M. Yagiura and T. Ibaraki, "On Metaheuristic Algorithms for Combinatorial Optimization Problems (in Japanese)", The Transactions of the Institute of Electronics, Information and Communication Engineers, Vol. J83-D-I, No.1, pp. 3-25, Jan. 2000).

PostScript file

back to the list of publications