Parallel Ant Colony Optimization Algorithm Based on Multiplicate Pheromon Declining

Abstract:

To overcome the defect of the classical ant colony algorithm’s slow convergence speed, and its vulnerability to local optimization, the authors propose Parallel Ant Colony Optimization Algorithm Based on Multiplicate Pheromon Declining to solve Traveling Salesman Problem according to the characteristics of natural ant colony multi-group and pheromone updating features of ant colony algorithm, combined with OpenMP parallel programming idea. The new algorithm combines three different pheromone updating methods to make a new declining pheromone updating method. It effectively reduces the impact of pheromone on the non-optimal path in the ants parade loop to subsequent ants and improves the parade quality of subsequent ants. It makes full use of multi-core CPU's computing power and improves the efficiency significantly. The new algorithm is compared with ACO through experiments. The results show that the new algorithm has faster convergence rate and better ability of global optimization than ACO.

• Periodical: Advanced Materials Research (Volumes 433-440)
• Pages: 3577-3583
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.433-440.3577
• Online since: January 2012
• Authors: Yan Zhang, Hao Wang, Yong Hua Zhang, Yun Chen, Xu Li
• Keywords: Ant Colony Optimization (ACO), OpenMP, Pheromone, Traveling Salesman Problem (TSP)

References

[1] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies [C]/ Varela F, Bourgine P, eds. Proc. of the ECAL'91 European Conf. of Artificial Life. Paris: Elsevier, 1991. 134-144.

[2] Dorigo M, Maniezzo V, Colorni A. Ant system: Optimization by a colony cooperating Agents [J]. IEEE Trans. on Systems, Man and Cybernetics. Part B: Cybernetics (S1083-4419), 1996, 26(1): 28-41.

DOI: 10.1109/3477.484436

[3] Dorigo M, Gambardella LM. Ant colony system: A cooperative learning approach to the traveling salesman problem [J]. IEEE Trans. on Evolutionary Computation (S1063-6560), 1997, 1(l): 53-66.

DOI: 10.1109/4235.585892

[4] WU QingHong, ZHANG Ji Hui, XU Xin He. AN ANT COLONY ALGORITHM WITH MUTATION FEATURES [J]. JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT, 1999, 36(10): 1240~1245.

[5] MA Liang, XIANG Pei Jun. Applications of the ant algorithm to combinatorial optimization [J]. Journal of Manegement Sciences In China, 2001, 4 (2): 32~36.

[6] Costa D, Hertz A. Ants can colour graphs[J]. J. of the Opnl. Res. Soc. , 1997, 48 (3): 295-305.

DOI: 10.1038/sj.jors.2600357

[7] Kuntz P, Layzell P, Snyers D. A colony of ant-like agents for partitioning in VLSI technology[C]. Proc. of the4thEuropean Conf. on Artificial Life. Boston: MIT Press, 1997, 417-424.

[8] Schoonderwoerd R, Holland O, Bruten J. Ant-like agents for load balancing in telecommunications networks[C]. Proc. of Agents' 97. Marina del Rey, CA: ACM Press, 1997, 209-216.

DOI: 10.1145/267658.267718

[9] MA Xi-Jun, PAN Ruo-Yu, YANG Shan-Lin. Ant Colony Algorithm Based on Pheromone Declining[J]. Acta Simulata Systematica Sinica, 2006, 18(11): 3297-3300.

[10] Liu Shengfei1, Zhang Yunquan1, Sun Xiangzheng. An Improved Guided Loop Scheduling Algorithm for OpenMP [J]. Journal of Computer Research and Development, 2010, 47(4): 687-694.

[11] Stutzle T, Hhoos H. The MAX-MIN ant system and local search for the traveling salesman problem [A]. In: Proceedings of the IEEE Interna tional Conference on Evolutionary Computation (ICEC'97)[C]. Indianapolis, USA, 1997. 309~314.

DOI: 10.1109/icec.1997.592327