On metaheuristic algorithms for combinatorial optimization problems

Metaheuristic algorithms are widely recognized as one of the most practical approaches for combinatorial optimization problems. Among representative metaheuristics are genetic algorithms, 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 experiments 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.