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 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.