A short convergence proof for a class of ant colony optimization algorithms

Abstract

We prove some convergence properties for a class of ant colony optimization algorithms. In particular, we prove that for any small constant /spl epsiv/ > 0 and for a sufficiently large number of algorithm iterations t, the probability of finding an optimal solution at least once is P*(t) /spl ges/ 1 - /spl epsiv/ and that this probability tends to 1 for t/spl rarr//spl infin/. We also prove that, after an optimal solution has been found, it takes a finite number of iterations for the pheromone trails associated to the found optimal solution to grow higher than any other pheromone trail and that, for t/spl rarr//spl infin/, any fixed ant will produce the optimal solution during the tth iteration with probability P /spl ges/ 1 /spl epsiv//spl circ/(/spl tau//sub min/, /spl tau//sub max/), where /spl tau//sub min/ and /spl tau//sub max/ are the minimum and maximum values that can be taken by pheromone trails.