Graph-based Ant System and its convergence

A general framework for solving combinatorial optimization problems heuristically by the Ant System approach is developed. The framework is based on the concept of a construction graph, a graph assigned to an instance of the optimization problem under consideration, encoding feasible solutions by walks. It is shown that under certain conditions, the solutions generated in each iteration of this Graph-based Ant System converge with a probability that can be made arbitrarily close to 1 to the optimal solution of the given problem instance. (C) 2000 Elsevier Science B.V. All rights reserved.