Research on the A. S. convergence properties of basic ant colony algorithm

Ant colony algorithm is a novel category of bionic meta-heuristic algorithm. Although ant colony algorithm for the heuristic solution of combinational optimization problems enjoys a rapidly growing popularity, but little is known about its convergence properties, especially its A. S. (almost surely) convergence properties. In this paper, we are concerned specifically with the A. S. convergence properties of the basic ant colony algorithm. Based on the introduction of the principle of basic ant colony algorithm, theoretical proof for the A. S. convergence properties of the basic ant colony algorithm is conducted by using Markov chains and martingale. The convergence properties of the pheromone trail vector are studied by changing the optimum solution set sequence into the submartingale sequence. Finally, the definition of the first passage time for the basic ant colony algorithm is proposed. Meanwhile, the theoretical analysis for the expected values of the first passage time is also performed in this paper.