Abstract
In this work, we propose a stochastic algorithm for solving\( \mathcal{N}{\wp } - hard \) combinatorial optimization problems. The procedure is formulated within the Ant Colony Optimization (ACO) framework, and extends the so-called Graph-based Ant System with time-dependent evaporation factor, (GBAS/tdev) studied in Gutjahr (2002). In particular, we consider an ACO search procedure which also takes into account the objective function value. We provide a rigorous theoretical study on the convergence of the proposed algorithm. Further, for a toy example, we compare by simulation the rate of convergence of the proposed algorithm with those from the Random Search (RS) and from the corresponding procedure in Gutjahr (2002).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Dorigo and L. M. Gambardella, “Ant colony systems: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation vol. 1 pp. 53–66, 1997.
M. Dorigo, V. Maniezzo, and A. Colorni, “The ant system: Optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man and Cybernetics Part B vol. 26 pp. 29–41, 1996.
M. Dorigo, G. Di Caro, and L. M. Gambardella, “Ant algorithms for discrete optimization,” Artificial Life vol. 5 pp. 137–172, 1999.
S. Droste, T. Jansen, and I. Wegener, “On the analysis of the (1 + 1) evolutionary algorithm,” Theoretical Computer Science vol. 276 pp. 51–81, 2002.
S. Geman and D. Geman, “Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images,” IEEE Transactions on Pattern Analysis and Machine Intelligence vol. 6 pp. 721–741, 1984.
F. Glover and M. Laguna, Tabu Search, Kluwer Academic Publishers: Boston, 1997.
D. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley: Reading, 1989.
W. J. Gutjahr, “A Graph-based ant system and its convergence,” Future Generation Computer Systems vol. 16 pp. 873–888, 2000.
W. J. Gutjahr, “ACO algorithms with guaranteed convergence to the optimal solution,” Information Processing Letters vol. 82 pp. 145–153, 2002.
W. J. Gutjahr, “A generalized convergence result for the graph-based ant system metaheuristic,” Probability in the Engineering and Informational Sciences vol. 17 pp. 545–569, 2003.
B. Hajek, “Cooling schedules for optimal annealing,” Mathematics of Operations Research vol. 13 pp. 311–329, 1988.
S. Kirkpatrick, C. D. Jr. Gellat, and M. P. Vecchi, “Optimization by simulated annealing,” Science vol. 220 pp. 671–680, 1983.
Ch. D. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall: Englewood Cliffs, 1982.
R. Y. Rubinstein, “Combinatorial optimization, cross-entropy, ants and rare events,” In S. Uryasev and P. M. Pardalos (eds.), Stochastic Optimization: Algorithms and Applications, pp. 1–57, Kluwer Academic Publishers: Boston, 2001.
H. P. Schwefel, Evolution and Optimum Seeking, Wiley: New York, 1995.
Author information
Authors and Affiliations
Corresponding author
Additional information
AMS 2000 Subject Classification: 9OC15, 9OC27
Rights and permissions
About this article
Cite this article
Sebastiani, G., Luca Torrisi, G. An Extended Ant Colony Algorithm and Its Convergence Analysis. Methodol Comput Appl Probab 7, 249–263 (2005). https://doi.org/10.1007/s11009-005-1485-z
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s11009-005-1485-z