Ant Colony Optimization Based on Adaptive Volatility Rate of Pheromone Trail

Zhaoquan CAI, Han HUANG, Yong QIN, Xianheng MA

.

DOI: 10.4236/ijcns.2009.28092                

Abstract

Ant colony optimization (ACO) has been proved to be one of the best performing algorithms for NP-hard problems as TSP. The volatility rate of pheromone trail is one of the main parameters in ACO algorithms. It is usually set experimentally in the literatures for the application of ACO. The present paper first proposes an adaptive strategy for the volatility rate of pheromone trail according to the quality of the solutions found by artificial ants. Second, the strategy is combined with the setting of other parameters to form a new ACO method. Then, the proposed algorithm can be proved to converge to the global optimal solution. Finally, the experimental results of computing traveling salesman problems and film-copy deliverer problems also indicate that the proposed ACO approach is more effective than other ant methods and non-ant methods.

Keywords

Ant Colony Optimization (ACO), Adaptive Volatility Rate, Pheromone Trail

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	M. Dorigo, G. D. Caro, and L. M. Gambardella, “Ant algorithms for discrete optimization,” Massachusetts Institute of Technology, Artificial Life 5, pp. 137–172, 1999.
[2]	M. Dorigo and L. M. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 53–66, 1997.
[3]	T. Stützle and H. H. Hoos, “MAX-MIN ant system, future gener,” Computer System, Vol. 16, No. 8, pp. 889– 914, 2000.
[4]	M. Dorigo and C. Blum, “Ant colony optimization theory: A survey,” Theoretical Computer Science, Vol. 344, pp. 243–278, 2005.
[5]	A. C. Zecchin, A. R. Simpson, H. R. Maier, and J. B. Nixon, “Parametric study for an ant algorithm applied to water distribution system optimization,” IEEE Transactions on Evolutionary Computation, Vol. 9, No. 2, April 2005.
[6]	M. Dorigo and L. M. Gambardella, “Ant colonies for the traveling salesman problem,” Bio-systems, Vol. 43, pp. 73–81, 1997.
[7]	K. M. Sim and W. H. Sun, “Ant colony optimization for routing and load-balancing: Survey and new directions,” IEEE Transactions on Systems, Man, and Cybernetics— Part A: Systems and Humans, Vol. 33, No. 5, September 2003.
[8]	I. Watanabe and S. L. Matsui, “Improving the performance of ACO algorithms by adaptive control of candidate set, evolutionary computation,” CEC’03, Vol. 2, pp. 1355–1362, 2003.
[9]	M. L. Pilat and T. White, “Using genetic algorithms to optimize ACS-TSP,” M. Dorigo et al. (Eds.):ANTS’02, LNCS 2463, pp. 282–287, 2002.
[10]	L. M. Gambardella and M. Dorigo, “Ant-Q: A reinforcement learning approach to the traveling salesman problem,” Appeared in: Proceedings of ML-95, Twelfth Intern. Conference on Machine Learning, Morgan Kauf-mann, pp. 252–260, 1995.
[11]	H. Huang and Z. F. Hao, “A bi-directional searching ant colony system,” Proceedings of 2006 International Conference on Intelligent Systems and Knowledge Engineer-ing (ISKE’06), April 6-7, 2006.
[12]	R. W.Cheng and M. Gen, “Film-copy deliverer problem using genetic algorithms,” Computers & Industrial Engineering, Vo1. 29, No. l-4, pp. 549–553, 1995.
[13]	J. Sun, S. W. Xiong, and F. M. Guo, “A new pheromone updating strategy in ant colony optimization,” Proceedings of 2004 International Conference on Machine Learning and Cybernetics, Vol. 1, pp. 620–625, 2004.
[14]	Z. F.Hao, H. Huang, X. W. Yang, Y. C. Liang, “Solve the film-copy deliverer problem using ant colony system,” Proceedings of the Third International Conference on Machine Learning and Cybernetics, Shanghai, 26-29 August 2004.
[15]	G. Reinelt, “A traveling salesman problem library,” ORSA Journal on Computing, TSPLIB, Vol. 3, No. 4, pp. 376–384, 1991.