SONG Jin-juan (宋锦娟)，BAI Yan-ping (白艳萍)
（Dept. of Mathematics, North University of China, Taiyuan 030051, China）
Abstract：Ant colony system (ACS), a kind of ant colony algorithm, is an effective way of solving shortest path problem, however, it has some defects. In this paper, ACS is improved for avoiding getting stuck in a local minimum, whose defects mainly include the following two aspects: initial pheromone solution and pheromone updating. In order to learn the advantages of improved ant colony system (IACS), experiments are conducted for some times. First, it is applied to 8 traveling salesman problem (TSP) instances, and compared with three self-organizing map (SOM) algorithms. Then the author analyzes the space complexity and convergence of two algorithms and compares them. Simulation results show that IACS has much better performance in solving TSP, and it has certain theoretical reference value and practical significance.
Key words： ant colony system (ACS); pheromone; traveling salesman problem; spcae complexity
CLD number： TP301.6 Document code： A
Article ID： 1674-8042(2013)01-0023-07 doi： 10.3969/j.issn.1674-8042.2013.01.006
References
[1] Balachandar S R, Kannan K. Randomized gravitational emulation search algorithm for symmetric traveling salesman problem. Applied Mathematics and Computation, 2007, 192(2): 413-421.
[2] Goldberg D E. Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Boston, 1989.
[3] Van Laarhoven P J, Aarts E H. Simulated annealing: theory and applications. Springer, 1987.
[4] Kohonen T. Self-organized formation of topologically correct feature maps. Biological Cybernetics, 1982, 43(1): 59-69.
[5] Fort J C. Solving a combinatorial problem via self-organizing process: an application of the Kohonen algorithm to the traveling salesman problem. Biological Cybernetics, 1988, 59(1): 33-40.
[6] Dorigo M, Gambardella L M, Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-56.
[7] Mullen R J, Monekosso D, Barman S, et al. A review of ant algorithms. Expert Systems with Applications, 2009, 36 (6): 9608-9617.
[8] Stützle T, Hoos H H. Max-min ant system. Future Generation Computer Systems, 2000, 16(8): 889-914.
[9] ZHANG Wen-dong, BAI Yan-ping, HU Hong-ping. The incorporation of an efficient initialization method and parameter adaptation using self-organizing maps to solve the TSP. Applied Mathematics and Computation, 2006, 172(1): 603-623.
[10] CHENG Chi-bin, MAO Chun-pin. A modified ant colony system for solving the traveling salesman problem with time windows. Mathematical and Computer Modelling, 2007, 46(9/10): 1225-1235.
[11] Yadlapalli S, Malik W A, Darbha S, et al. A lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem. Nonlinear Analysis: Real World Applications, 2009, 10(4): 1990-1999.
[12] Ruprecht-karls-universitat heidelberg. Symmetric traveling salesman problem (TSP): TSP data, best solutions for symmetric TSPs. [2012-08-15]. http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.
[13] WU Ling-yun. The application for neural networks in combinatorial optimization and DNA sequencing. Department of Mathematics, Academy of Sciences, China, 2002: 51-56.
[full text view]
