| Title: | A pheromone-rate-based analysis on the convergence time of ACO algorithm |
| Address: | "School of Software Engineering, South China University of Technology, Guangzhou 510006, China. hhan@scut.edu.cn" |
| Journal Title: | IEEE Trans Syst Man Cybern B Cybern |
| DOI: | 10.1109/TSMCB.2009.2012867 |
| ISSN/ISBN: | 1941-0492 (Electronic) 1083-4419 (Linking) |
| Abstract: | "Ant colony optimization (ACO) has widely been applied to solve combinatorial optimization problems in recent years. There are few studies, however, on its convergence time, which reflects how many iteration times ACO algorithms spend in converging to the optimal solution. Based on the absorbing Markov chain model, we analyze the ACO convergence time in this paper. First, we present a general result for the estimation of convergence time to reveal the relationship between convergence time and pheromone rate. This general result is then extended to a two-step analysis of the convergence time, which includes the following: 1) the iteration time that the pheromone rate spends on reaching the objective value and 2) the convergence time that is calculated with the objective pheromone rate in expectation. Furthermore, four brief ACO algorithms are investigated by using the proposed theoretical results as case studies. Finally, the conclusions of the case studies that the pheromone rate and its deviation determine the expected convergence time are numerically verified with the experiment results of four one-ant ACO algorithms and four ten-ant ACO algorithms" |
| Keywords: | "*Algorithms Animals Ants/*physiology Cybernetics/*methods *Markov Chains Models, Biological Models, Statistical Pheromones/*physiology;" |
| Notes: | "MedlineHuang, Han Wu, Chun-Guo Hao, Zhi-Feng eng Research Support, Non-U.S. Gov't 2009/04/22 IEEE Trans Syst Man Cybern B Cybern. 2009 Aug; 39(4):910-23. doi: 10.1109/TSMCB.2009.2012867. Epub 2009 Apr 17" |
