Article ID: | iaor2005356 |
Country: | United Kingdom |
Volume: | 17 |
Issue: | 4 |
Start Page Number: | 545 |
End Page Number: | 569 |
Publication Date: | Oct 2003 |
Journal: | Probability in the Engineering and Informational Sciences |
Authors: | Gutjahr Walter J. |
Keywords: | ant system |
Itis 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.