|
|
|
| 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.
|
|
Received: 07 July 2009
|
|
|
|
|
|
[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 
