Abstract:
Traveling salesman problem (TSP) is one of
the most famous combinatorial optimization
(CO) problems, which has wide application
background. Ant Colony Optimization (ACO) is
a heuristic algorithm which has been proven a
successful technique and applied to a number of
combinatorial optimization problems and taken
as one of the high performance computing
methods for TSP. ACO has very good search
capability for optimization problems, but it still
has some drawbacks for solving TSP. These
drawbacks will be more obvious when the
problem size increases. The present paper
proposes an ACO algorithm with nearest
neighbor (NN) heuristic approach and
information entropy which is conducted on the
configuration strategy for the adjustable
parameters to improve the efficiency of ACO in
solving TSP. The performance of ACO also
depends on the appropriate setting of
parameters. 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 superior search performance over
traditional ACO algorithms do.
