Hostname: page-component-745bb68f8f-kw2vx Total loading time: 0 Render date: 2025-02-11T06:56:41.709Z Has data issue: false hasContentIssue false
  • English
  • Français

A GENERALIZED CONVERGENCE RESULT FOR THE GRAPH-BASED ANT SYSTEM METAHEURISTIC

Published online by Cambridge University Press:  24 September 2003

Walter J. Gutjahr
Walter J. Gutjahr
Affiliation:
Department of Statistics and Decision Support Systems, University of Vienna, Vienna, Austria, E-mail: walter.gutjahr@univie.ac.at
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

It is shown that on fairly weak conditions, the current solutions of a metaheuristic following the ant colony optimization paradigm, the graph-based ant system, converge with a probability that can be made arbitrarily close to unity to one element of the set of optimal solutions. The result generalizes a previous result by removing the very restrictive condition that both the optimal solution and its encoding are unique (this generalization makes the proof distinctly more difficult) and by allowing a wide class of implementation variants in the first phase of the algorithm. In this way, the range of application of the convergence result is considerably extended.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 17 , Issue 4 , October 2003 , pp. 545 - 569
Copyright
© 2003 Cambridge University Press