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.
