Markov Chains and Martingale Theory Based Convergence Proof of Ant Colony Algorithm and Its Simulation Platform
Markov Chains and Martingale Theory Based Convergence Proof of Ant Colony Algorithm and Its Simulation Platform
复制标题
DOI：
10.1109/wcica.2006.1712928
复制
发表时间：
2006-10
期刊：
影响因子：
--
通讯作者：
H. Duan;Daobo Wang;Xiufen Yu
中科院分区：
文献类型：
--
作者：
H. Duan;Daobo Wang;Xiufen Yu
Ant colony algorithm is a novel category of bionic meta-heuristic algorithm, and parallel computation and positive feedback mechanism are adopted in this algorithm. In this paper, we present a new approach to the convergence proof of the ant colony algorithm. Here the theoretical proof for the convergence properties of the ant colony algorithm is conducted by using Markov chains and martingale theory. When the iteration time is infinite, the pheromone trail vector almost surely converge to the optimum solution. The event that at least one ant transverse an optimal path. Together with the solution set, is a positive bounded submartingale. Then, the definition of the first passage time for the ant colony algorithm is proposed, and the theoretical analysis for the expected value of the first passage time is also performed. Finally, a Matlab GUI-based ant colony algorithm simulation platform is developed in this paper, and the interface of this simulation platform is very friendly, easy to use and modify
