Hybridizing multi-inver-over evolutionary algorithms with tabu search for the symmetric TSP

Abstract

The travelling salesman problem (TSP) is a NP-hard problem. Techniques as either Branch and Bound or Dynamic Programming supplied the global optimum solution for instances with more than 7000 cities. But, ther needed more than 4 years of CPU time. Fortunately, faster algorithms (simulated annealing, tabu search, neural networks, and evolutionary computation) exist although they do not guarantee to find the global optimum. Recently an EA based on a operator inver-over [4], provides optimal or near-optimal solutions in a very short time. A latest approach included a variant of inver-over called multi-inver-over [6]. The corresponding results showed advances when compared with other search techniques. This work shows a further enhancement, the Hybrid Multi-inver-over Evolutionary Algorithms (HMEAs), which consists in hybridizing multirecombined evolutionary algorithms with Tabu Search. In these algorithms local search is inserted in different stages of the evolutionary process as in [7 and 8]. They were tested on the hardest set of the test suite chosen in previous works. Details on implementation, experiments and results are discussed.