Time Complexity Analysis of Ant Colony Algorithm on First Order Deceptive Problem
CHEN Ling1,2,SUN Hai-Yin1
1.Department of Computer,College of Information Engineering,Yangzhou University,Yangzhou 225009 2.State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210093
Abstract The time complexity of ant colony optimization (ACO) on the deceptive systems is analyzed. Based on the study of the n-bit trap problem which is a first order deceptive problem of ACO, It is proved that time complexity for n-bit trap problem is O(n2mlnn) by max-min ant system (MMAS), which is an ACO with limitations on the pheromone on each edge. Here, n is the size of the problem and m is the number of artificial ants. The experimental results confirm the correctness of the conclusions.
[1] Dorigo M, Stützle T. Ant Colony Optimization. New York, USA: MIT Press, 2004 [2] Dorigo M, Blum C. Ant Colony Optimization Theory: A Survey. Theoretical Computer Science, 2005, 344(2/3): 243-278 [3] Blum C. Ant Colony Optimization: Introduction and Recent Trends. Physics of Life Reviews, 2005, 2(4): 353-373 [4] Shtovba S. Ant Algorithms: Theory and Applications. Programming and Computer Software, 2005, 31(4): 167-178 [5] Dréo J, Siarry P. Continuous Interacting Ant Colony Algorithm Based on Dense Hierarchy. Future Generation Computer Systems, 2004, 20(5): 841-856 [6] Elbeltagi E, Hegazy T, Grierson D. Comparison among Five Evolutionary-Based Optimization Algorithms. Advanced Engineering Informatics, 2005, 19(1): 43-53 [7] Stefan J, Daniel M, Middendorf M, et al. On Enforced Convergence of ACO and Its Implementation on the Reconfigurable Mesh Architecture Using Size Reduction Tasks. Journal of Supercomputing, 2003, 26(3): 221-238 [8] Martin M, Frank R, Hartmut S. Multi Colony Ant Algorithms. Journal of Heuristics, 2002, 8(3): 305-320 [9] Sun Jun, Xiong Shengwu, Guo Fuming. A New Pheromone Updating Strategy in Ant Colony Optimization // Proc of the International Conference on Machine Learning and Cybernetics. Shanghai, China, 2004, Ⅰ: 620-625 [10] Coleman C M, Rothwell E J, Ross J E. Investigation of Simulated Annealing, Ant-Colony Optimization, and Genetic Algorithms for Self-Structuring Antennas. IEEE Trans on Antennas and Propagation, 2004, 52(4): 1007-1014 [11] Agarwal A, Lim M H, Er M J, et al. ACO for a New TSP in Region Coverage // Proc of the IEEE/RSJ International Conference on Intelligent Robots and Systems. Edmonton, Canada, 2005: 1717-1722 [12] Blum C. Beam-ACO-Hybridizing Ant Colony Optimization with Beam Search: An Application to Open Shop Scheduling. Computers and Operations Research, 2005, 32(6): 1565-1591 [13] Prokopenko M, Wang P, Foreman M, et al. On Connectivity of Reconfigurable Impact Networks in Ageless Aerospace Vehicles. Robotics and Autonomous Systems, 2005, 53(1): 36-58 [14] Chen Yixin, Chen Ling, Tu Li. Parallel Ant Colony Algorithm for Mining Classification Rules // Proc of the IEEE International Conference on Granular Computing. Georgia, USA, 2006: 85-90 [15] Kuo R J, Kuo Y P, Chen Kaiying. Developing a Diagnostic System through Integration of Fuzzy Case-Based Reasoning and Fuzzy Ant Colony System. Expert Systems with Applications, 2005, 28(4): 783-797 [16] Katangur A K, Akkaladevi S, Pan Y, et al. Applying Ant Colony Optimization to Routing in Optical Multistage Interconnection Networks with Limited Crosstalk // Proc of the 18th International Parallel and Distributed Processing Symposium. Santa Fe, USA, 2004: 163-170 [17] Shyu S J, Lin B M T, Hsiao T S. Ant Colony Optimization for the Cell Assignment Problem in PCS Networks. Computers and Operations Research, 2006, 33(6): 1713-1740 [18] Maniezzo V, Carbonaro A. An ANTS Heuristic for the Frequency Assignment Problem. Future Generation Computer Systems, 2000, 16(9): 927-935 [19] Kalinli A, Karaboga N. Artificial Immune Algorithm for IIR Filter Design. Engineering Applications of Artificial Intelligence, 2005, 18(8): 919-929 [20] Talbi E G, Roux O, Fonlupt C, et al. Parallel Ant Colonies for the Quadratic Assignment Problem. Future Generation Computer Systems, 2001, 17(4): 441-449 [21] Gambardella L M, Dorigo M. An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem. INFORMS Journal on Computing, 2000, 12(3): 237-255 [22] Lee Z J, Lee C Y, Su S F. An Immunity-Based Ant Colony Optimization Algorithm for Solving Weapon-Target Assignment Problem. Applied Soft Computing, 2002, 2(1): 39-47 [23] Blum C, Dorigo M. Deception in Ant Colony Optimization // Proc of the International Workshop on Ant Colony Optimization and Swarm Intelligence. Brussels, Belgium, 2004: 119-130 [24] Blum C, Dorigo M. Search Bias in Ant Colony Optimization: On the Role of Competition-Balanced Systems. IEEE Trans on Evolutionary Computation, 2005, 9(2): 159-174 [25] Gutjahr W J. A Graph-Based Ant System and Its Convergence. Future Generation Computer Systems, 2000, 16(9): 873-888 [26] Gutjahr W J. ACO Algorithms with Guaranteed Convergence to the Optimal Solution. Information Processing Letters, 2002, 82(3): 145-153 [27] Stützle T, Dorigo M. A Short Convergence Proof for a Class of Ant Colony Optimization Algorithms. IEEE Trans on Evolutionary Computation, 2002, 6(4): 358-365 [28] Blum C, Dorigo M. The Hypercube Framework for Ant Colony Optimization. IEEE Trans on Systems, Man and Cybernetics, 2004, 34(2): 1161-1172 [29] Blum C. Theoretical and Practical Aspects of Ant Colony Optimization. Berlin, Germany: IOS Press, 2004 [30] Neumann F, Witt C. Runtime Analysis of a Simple Ant Colony Optimization Algorithm. Technical Report, CI-200/06, Dortmund, Germany: University of Dortmund. Department of Computer Science, 2006 [31] Attiratanasunthron N, Fakcharoenphol J. A Running Time Analysis of an Ant Colony Optimization Algorithm for Shortest Paths in Directed Acyclic Graphs. Information Processing Letters, 2008, 105(3): 88-92 [32] Hao Zhifeng, Huang Han, Zhang Xili, et al. A Time Complexity Analysis of ACO for Linear Functions // Proc of the 6th International Conference on Simulated Evolution and Learning. Hefei, China, 2006: 513-520 [33] Huang Han, Hao Zhifeng, Wu Chunguo, et al. The Convergence Speed of Ant Colony Optimization. Chinese Journal of Computers, 2007, 38(8): 1344-1353 (in Chinese) (黄 翰,郝志峰,吴春国,等.蚁群算法的收敛速度分析.计算机学报, 2007, 38(8): 1344-1353)
2010, Vol. 23 
