On Metaheuristic Algorithms for Combinatorial Optimization Problems
Mutsunori YAGIURA and Toshihide IBARAKI
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.
combinatorial optimization problem,
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
The Transactions of the Institute of Electronics, Information
and Communication Engineers, Vol. J83-D-I, No.1, pp. 3-25, Jan. 2000).
back to the list of publications