Modified Ant Colony Optimization Algorithm for Traveling Salesman Problem

Abstract

Ant Colony Optimization (ACO) is a useful approach for finding near optimal solutions in polynomial time for Nondeterministic Polynomial time (NP) problems. Traveling salesman problem (TSP) is a typical NP hard problem in path optimization, and ACO algorithm is an effective way to solve TSP. However, when the problems come to high dimensions, the traditional ant algorithm works with low efficiency and accuracy, and usually trap in local optimal solution. To overcome the shortcoming of the algorithm, this paper proposes a modified ant colony optimization algorithm which combines candidate list strategy and local search to improve the efficiency and accuracy of the algorithm. Experiments are carried out to verify the availability and analyze the performance of the proposed algorithm. The results illustrate the higher efficiency of the proposed algorithm to solve TSP, comparing with ant colony algorithm and prove that the proposed algorithm is a positive effective way to tackle TSP.