A Dynamic Edge Exchanged Ant Colony Algorithm for TSP Problem

Abstract:

Aimed at solving premature convergence and low speed in heuristic algorithms for TSP problems, this paper analyzed the principle of Max-Min Ant colony algorithm (MMAS) and Lin-Kernighan algorithm, then proposed a dynamic exchange of Max-Min Ant colony algorithm (MMAS-LK). The new algorithm used MMAS to initially a set of the solutions in the early state, then utilized the improved Lin-Kernighan algorithm for local optimization, and dynamic adjustment parameters according to the process of computing avoid falling into local optimum. The simulation results showed that the proposed algorithm compared with the original MMAS and Lin-Kernighan algorithm, it has a better speed and precision in the TSP problem.

• Periodical: Applied Mechanics and Materials (Volumes 687-691)
• Pages: 1608-1611
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.687-691.1608
• Online since: November 2014
• Authors: Yu Zhong Liu, Hua Ping Yu
• Keywords: Ant Colony Algorithm (ACA), Lin-Kernighan Algorithm, Local Search, TSP

References

[1] Information on http: /en. wikipedia. org/wiki/Travelling_salesman_problem.

[2] Dorigo M, Maniezzo V, Colorni A: Systems, Man, and Cybernetics (Part B), Vol. 26 (1996) No. 3, pp.29-41.

[3] Lin S, Kernighan B W. An effective heuristic algorithm for the traveling-salesman problem[J]. Operations research, Vol. 21. 2(1973), pp.498-516.

DOI: 10.1287/opre.21.2.498

[4] Stutzle T, Hoos H: MAX-MIN ant system and local search for the traveling salesman problem, Evolutionary Computation (April 4-5, 1997). Vol. 1, pp.309-314.

DOI: 10.1109/icec.1997.592327

[5] Duan H, Wei X, Dong Z. Multiple UCAVs cooperative air combat simulation platform based on PSO, ACO, and game theory[J]. Aerospace and Electronic Systems Magazine, IEEE, Vol. 28. 11(2013), pp.12-19.

DOI: 10.1109/maes.2013.6678487

[6] Information on http: /comopt. ifi. uni-heidelberg. de/software/TSPLIB95.