Abstract
A generalized version of Gutjahr’s Graph-based Ant System (GBAS) framework for solving static combinatorial optimization problems is examined in the present paper. A new transition rule which intends to balance between the exploration and the exploitation in the search progress of Ant-based algorithms, is added into Gutjahr’s GBAS model. As shown in this paper, our generalized model still holds all convergent properties of the GBAS model and may show a promising improvement in solution quality to Ant-based algorithms in literature.
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
E. Aarts and J. Korst. Simulated annealing and Boltzmann machines: A stochastic approach to combinatorial optimization and neural computing. John Wiley and Sons, Inc.: New York, 1990.
M. Dorigo and G. Di Caro. The ant colony optimization metaheuristic. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas In Optimization. McGraw-Hill, 1999.
M. Dorigo, G. Di Caro, and L.M. Gambardella. Ant algorithms for discrete optimization. Artificial Life, 5:137–172, 1999.
M. Dorigo and L.M. Gambardella. Ant colony system: A cooperative learning approach to the travelling salesman problem. IEEE Transactions on Evolutionary Computation, 1:53–66, 1997.
M. Dorigo, V. Maniezzo, and A. Colorni. The ant system: Optimization by a colony of cooperating agents. IEEE Transaction on Systems, Man, and Cybernetics, 26:29–41, 1996.
F. Glover. Tabu search, part I. ORSA Journal on Computing, 1:190–206, 1989.
F. Glover and M. Laguna. Tabu Search. Kluwer Academic Publishers: Boston, MA, 1997.
W.J. Gutjahr. A graph-based ant system and its convergence. Future Gerneration Computer Systems, 16(9):873–888, 2000.
W.J. Gutjahr. Aco algorithms with guaranteed convergence to the optimal solution. Information Processing Letters, 82:145–153, 2002.
W.J. Gutjahr. A generalized convergence result for the graph-based ant system metaheuristic. Probability in the Engineering and Informational Sciences, 17(4):545–569, 2003.
J.H. Holland. Adaption in Natural and Artificial Systems. Univ. of Michigan Press: Ann Arbor. Reprinted in 1992 by MIT Press, Cambridge MA, 1975.
Z. Michalewics. Genetic Algorithms + Data Structures = Evolutionary Programs. Springer: New York, 3rd edition, 1996.
P. Salamon, P. Sibani, and R. Frost. Facts, Conjectures, and Improvements for Simulated Annealing. SIAM, 2003.
T. Stützle and M. Dorigo. A short convergence proof for a class of ACO algorithms. IEEE Transactions on Evolutionary Computation, 6(4):358–365, 2002.
T. Stützle and H.H. Hoos. The MAX-MIN ant system and local search for the traveling salesman problem. In T. Bäck, Z. Michalewicz, and X. Yao, editors, Proceedings of the 4th International Conference on Evolutionary Computation (ICEC’97), pages 308–313. IEEE Press, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dinh, H.T., Al Mamun, A., Huynh, H.T. (2005). A generalized version of Graph-based Ant System and its applicability and convergence. In: Abraham, A., Dote, Y., Furuhashi, T., Köppen, M., Ohuchi, A., Ohsawa, Y. (eds) Soft Computing as Transdisciplinary Science and Technology. Advances in Soft Computing, vol 29. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-32391-0_98
Download citation
DOI: https://doi.org/10.1007/3-540-32391-0_98
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25055-5
Online ISBN: 978-3-540-32391-4
eBook Packages: EngineeringEngineering (R0)