Research on Traveling Salesman Problem Based on the Ant Colony Optimization Algorithm and Genetic Algorithm

ABSTRACT

In this paper, we prompt a new multi-dimensional algoithm to solve the traveling salesman problem based on the ant colony optimization algorithm and genetic algorithm. Ant Colony Optimization (ACO) is a heuristic algorithm which has been proven a successful technique and applied to a number of combinatorial optimization (CO) problems. The traveling salesman problem (TSP) is one of the most important combinatorial problems. ACO is taken as one of the high performance computing methods for TSP. It still has some drawbacks such as stagnation behavior, long computational time, and premature convergence problem of the basic ACO algorithm on TSP. Those problems will be more obvious when the considered problems size increases. The proposed system based on basic ACO algorithm with well distribution strategy and information entropy which is conducted on the configuration strategy for updating the heuristic parameter in ACO to improve the performance in solving TSP. Then, ACO for TSP has been improved by incorporating local optimization heuristic. Algorithms are tested on benchmark problems from TSPLIB and test results are presented. From our experiments, the proposed algorithm has better performance than ACO algorithm.

Keywords: