A high performance hybrid metaheuristic for traveling salesman problem

Genetic algorithm (GA) is one of the most widely used metaheuristics in finding the approximate solutions of complex problems in a variety of domains. As such, many researchers have focused their attention on enhancing the performance of GA - in terms of either the speed or the quality but rarely in terms of both. This paper presents an efficient hybrid metaheuristic to resolve these two seemingly conflicting goals. That is, the proposed method can not just reduce the running time of GA and its variants, but it can also make the loss of quality small, called High Performance Hybrid Metaheuristic (or HPHM for short). The underlying idea of the proposed algorithm is to leverage the strengths of GA, Tabu Search, and the notion of Pattern Reduction. To evaluate the performance of the proposed algorithm, we use it to solve the traveling salesman problem. Our experimental results indicate that the proposed algorithm can significantly enhance the performance of GA and its variants - especially the speed.