Abstract
ACO has been proved to be one of the best performing algorithms for NP-hard problems as TSP. Many strategies for ACO have been studied, but little theoretical work has been done on ACO’s parameters α and β, which control the relative weight of pheromone trail and heuristic value. This paper describes the importance and functioning of α and β, and draws a conclusion that a fixed β may not enable ACO to use both heuristic and pheromone information for solution when α= 1. Later, following the analysis, an adaptive β strategy is designed for improvement. Finally, a new ACO called adaptive weight ant colony system (AWACS) with the adaptive β and α= 1 is introduced, and proved to be more effective and steady than traditional ACS through the experiment based on TSPLIB test.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Dorigo, M., Caro, G.D., Gambardella, L.M.: Ant Algorithms for Discrete Optimization. Massachusetts Institute of Technology, Artificial Life 5, 137–172 (1999)
Dorigo, M., Gambardella, L.M.: Ant Colony System: A Cooperative Learning Approah to the Travelling Salesman Problem. IEEE Transactions on Evolutionary Computation 1(1), 53–66 (1997)
Stützle, T., Hoos, H.H.: MAX-MIN Ant System. Future Gener. Comput. Syst. 16(8), 889–914 (2000)
Gutjahr, W.J.: Ageneralized Convergence Result for the Graph-Based Ant System Metaheuristic. Tech. Report 99-09, Department of Statistics and Decision Support Systems, University of Vienna, Austria (1999)
Gutjahr, W.J.: Agraph-Based Ant System and Its Convergence. Future Gen. Comput. Systems 16(9), 873–888 (2000)
Gutjahr, W.J.: ACO Algorithms with Guaranteed Convergence to the Optimal Solution. Information Processing Letters 82, 145–153 (2002)
Stützle, T., Dorigo, M.: A Short Convergence Proof for a Class of Ant Colony Optimization Algorithms. IEEE Transactions on Evolutionary Computation 6(4), 358–365 (2002)
Dorigo, M., Stützle, T.: Ant Colony Optimization. MIT Press, Cambridge (2004)
Dorigo, M., Blum, C.: Ant colony optimization theory: A survey. Theoretical Computer Science 344, 243–278 (2005)
Badr, A., Fahmy, A.: A Proof of Convergence for Ant Algorithms. Information Sciences 160, 267–279 (2004)
Fidanova, S.: ACO Algorithm with Additional Reinforcement. In: Dorigo, M., Di Caro, G.A., Sampels, M. (eds.) Ant Algorithms 2002. LNCS, vol. 2463, pp. 292–293. Springer, Heidelberg (2002)
Fidanova, S.: Convergence Proof for a Monte Carlo Method for Combinatorial Optimization Problems. In: Bubak, M., van Albada, G.D., Sloot, P.M.A., Dongarra, J. (eds.) ICCS 2004. LNCS, vol. 3039, pp. 523–530. Springer, Heidelberg (2004)
Watanabe, I., Matsui, S.: Improving the Performance of ACO Algorithms by Adaptive Control of Candidate Set. Evolutionary Computation, 2003. In: CEC 2003. The 2003 Congress on 2 (8-12), pp. 1355–1362 (2003)
Pilat, M.L., White, T.: Using Genetic Algorithms to Optimize ACS-TSP. In: Dorigo, M., Di Caro, G.A., Sampels, M. (eds.) Ant Algorithms 2002. LNCS, vol. 2463, pp. 282–287. Springer, Heidelberg (2002)
Zecchin, A.C., Simpson, A.R., Maier, H.R., Nixon, J.B.: Parametric Study for an Ant Algorithm Applied to Water Distribution System Optimization. IEEE Transactions on evolutionary computation 9(2) (April 2005)
Dorigo, M., Gambardella, L.M.: Ant Colonies for the Traveling Salesman Problem. BioSystems 43, 73–81 (1997)
Sim, K.M., Sun, W.H.: Ant Colony Optimization for Routing and Load-Balancing: Survey and New Directions. IEEE Transactions on Systems, Man, and Cybernetics—Part A: Systems and Humans 33(5) (September 2003)
Blum, C., Dorigo, M.: Search Bias in Ant Colony Optimization: On the Role of Competition-Balanced Systems. IEEE Transactions on evolutionary computation 9(2) (April 2005)
Reinelt, G.: TSPLIB. A Traveling Salesman Problem Library. ORSA Journal on Computing 3(4), 376–384 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Huang, H., Yang, X., Hao, Z., Cai, R. (2006). A Novel ACO Algorithm with Adaptive Parameter. In: Huang, DS., Li, K., Irwin, G.W. (eds) Computational Intelligence and Bioinformatics. ICIC 2006. Lecture Notes in Computer Science(), vol 4115. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11816102_2
Download citation
DOI: https://doi.org/10.1007/11816102_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37277-6
Online ISBN: 978-3-540-37282-0
eBook Packages: Computer ScienceComputer Science (R0)