Chinese Journal of Computers   Full Text
Title	The Convergence Speed of Ant Colony Optimization
Authors	HUANG Han1) HAO Zhi-Feng1),2) WU Chun-Guo3) QIN Yong4)
Address	1)(College of Computer Science and Engineering, South China University of Technology, Guangzhou 510640) 2)(State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093) 3)(College of Computer Science and Technology, Key Laboratory of Symbol Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012) 4)(Center of Information and Network, Maoming University, Maoming, Guangdong 525000)
Year	2007
Issue	No.8(1344—1353)
Abstract &   Background	Abstract Ant colony optimization (ACO) which is one of the popular methods in machine learning is used widely to solve combinatorial optimization problems. However, there are few theoretical studies for ACO, compared with the counterparts for genetic algorithm (GA). How to analyze the convergence speed is the first open problem of ACO research. In this paper the first open problem is studied via modeling ACO algorithm as an absorbing Markov process, based on which the theoretical results of convergence speed are presented. The convergence speed of ACO algorithm is analyzed by estimating the expected convergence time. The authors propose the method to estimating the expected convergence time of ACO algorithm, and the approach to judging whether a TSP problem belongs to ACO-easy class or ACO-hard class. Finally, the convergence speed of ant colony system (ACS) is analyzed as an example to demonstrate the effectiveness of the theory proposed in this paper. keywords ant colony optimization; absorbing Markov process; expected convergence time; ACO-hard and ACO-easy problems; optimal path background Ant colony optimization (ACO) is one of the popular methods in machine learning. How to analyze the convergence speed is the first open problem of ACO research. This paper introduces a framework to solve this open problem by proposing the absorbing Markov process model, the method to estimating the expected convergence time of ACO algorithm, and the approach to judging whether a TSP problem belongs to ACO-easy class or ACO-hard class. This work is supported by the National Natural Science Foundation of China (60433020, 10471045, 60673023), Natural Science Foundation of Guangdong Province (970472, 000463, 04020079, 05011896), State Key Laboratory for Novel Software Technology, Nanjing University (200603), open research fund of National Mobile Communications Research Laboratory, Southeast University (A200605) and Nature Science Foundation of Education Department of Guangdong Province (Z03080). The work of the projects is mainly about the theoretical foundation and application of evolutionary computation. The results can be used to analyze the performance of evolutionary computation methods, solve the combinatorial optimization problems and optimize the design of engineering.