Abstract—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 is taken as one of the high performance computing methods for Traveling salesman problem (TSP). TSP is one of the most famous combinatorial optimization (CO) problems and which has wide application background.. ACO has very good search capability for optimization problems, but it still remains a computational bottleneck that the ACO algorithm costs too much time to convergence and traps in local optima in order to find an optimal solution for TSP problems. The presented paper proposes an improved ant colony optimization algorithm with two highlights. First, candidate set strategy is adopted to rapid convergence speed. Second, a dynamic updating rule for heuristic parameter based on entropy to improve the performance in solving TSP. Algorithms are tested on benchmark problems from TSPLIB and test results are presented. From our experiments, the proposed algorithm has better performance than the conventional ACO algorithm and the results of the proposed algorithms are found to be satisfactory.
Index Terms—Ant colony optimization, entropy, traveling salesman problem
Authors are with the University of Computer Studies, Yangon, Myanmar (e-mail: zarchisusuhlaing@ gmail.com).
Cite: Zar Chi Su Su Hlaing and May Aye Khine, "Solving Traveling Salesman Problem by Using Improved Ant Colony Optimization Algorithm," International Journal of Information and Education Technology vol. 1, no. 5, pp. 404-409, 2011.