[1]XIA Xiaoyun,ZHOU Yuren.Advances in theoretical research of ant colony optimization[J].CAAI Transactions on Intelligent Systems,2016,11(1):27-36.[doi:10.11992/tis.201510002]
Copy

Advances in theoretical research of ant colony optimization

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 11 Number of periods: 2016 1 Page number: 27-36 Column: 综述 Public date: 2016-02-25
Title:
Advances in theoretical research of ant colony optimization
Author(s):
XIA Xiaoyun1; 2;  ZHOU Yuren3
1. School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou 341000, China;
2. School of Computer Science and Engineering, South China University of Technology, Guangzhou 510006, China;
3. School of Data and Computer Science, Sun Yat-Sen University, Guangzhou 510006, China
Keywords:
ant colony optimization; theoretical research; combinatorial optimization; convergence; time complexity; approximation performance
CLC:
TP18;TP301.6
DOI:
10.11992/tis.201510002
Abstract:
Theoretical investigations of the ant colony optimization (ACO) algorithm can help to improve our understanding of the theoretical basis of the algorithm and guide its appropriate application. Theoretical research on ACO has included analyses of early convergence, time complexity, and approximation performance. Investigation objectives have ranged from simple Boolean functions, to combinatorial optimization and practical application problems, to the analysis of NP-hardness problems. In this paper, we survey state-of-the-art theoretical ACO research from two aspects: the most common mathematical techniques and those less common. In addition, we introduce two mathematical analysis tools, including fitness value partitioning and drift analysis, and discuss important ACO issues, including ACO runtime analysis and approximation performance. More specifically, we provide comparative results for ACO’s performance in solving various problems. These studies provide a direction for better understanding the working principles of ACO. Finally, we highlight further research directions, including the introduction of new analytical tools and the study of more complicated algorithmic models.
References:
[1] DORIGO M, MANIEZZO V, COLORNI A. Theantsystem:An autocatalytic optimizing process Technical Report 91-016[R]. Milan, Italy:Dipartimento di Elettronica, Politecnico di Milano, 1991.
[2] DORIGO M, STUTZLE T. 蚁群优化[M]. 张军, 胡晓敏, 罗旭耀, 译. 北京:清华大学出版社, 2007:110-246.
[3] DORIGO M, BLUM C. Ant colony optimization theory:a survey[J]. Theoretical computer science, 2005, 344(2-3):243-278.
[4] 段海滨, 王道波, 于秀芬. 蚁群算法的研究现状及其展望[J]. 中国工程科学, 2007, 9(2):98-102.DUAN Haibin, WANG Daobo, YU Xiufen. Ant colony algorithm:survey and prospect[J]. Engineering science, 2007, 9(2):98-102.
[5] NOCEDAL J, WRIGHT S J. Numerical optimization[M]. New York:Springer, 2000.
[6] VAZIRANI V V. Approximation algorithms[M]. Berlin Heidelberg:Springer, 2003.
[7] GAREY M R, JOHNSON D S. Computers and Intractability-A Guide to the Theory of NP-Completeness[M]. New York:Freeman W H and Company, 1979.
[8] COLORNI A, DORIGO M, MANIEZZO V. An investigation of some properties of an "Ant algorithm"[C]//Proceedings of Parallel Problem Solving from Nature II (PPSN 92). Brussels, Belgium, 1992:515-526.
[9] STVTZLE T, HOOS H H. MAX-MIN ant system[J]. Future generation computer systems, 2000, 16(8):889-914.
[10] GUTJAHR W J. Mathematical runtime analysis of ACO algorithms:survey on an emerging issue[J]. Swarm intelligence, 2007, 1(1):59-79.
[11] DROSTE S, JANSEN T, WEGENER I. On the analysis of the (1+1) evolutionary algorithm[J]. Theoretical computer science, 2002, 276(1-2):51-81.
[12] WEGENER I, WITT C. On the analysis of a simple evolutionary algorithm on quadratic pseudo-boolean functions[J]. Journal of discrete algorithms, 2005, 3(1):61-78.
[13] WEGENER I. Towards a theory of randomized search heuristics[M]//ROVAN B, VOJTá? P. Mathematical Foundations of computer science 2003. Berlin Heidelberg:Springer, 2003:125-141.
[14] WEGENER I. Methods for the analysis of evolutionary algorithms on pseudo-boolean functions[M]//Evolutionary Optimization. Dordrecht:Kluwer Academic Publishers, 2002, 48:349-369.
[15] BEYER H G, SCHWEFEL H P, WEGENER I. How to analyse evolutionary algorithms[J]. Theoretical computer science, 2002, 287(1):101-130.
[16] HE J, YAO X. Towards an analytic framework for analysing the computation time of evolutionary algorithms[J]. Artificial intelligence, 2003, 145(1-2):59-97.
[17] HE J, YAO X. Drift analysis and average time complexity of evolutionary algorithms[J]. Artificial intelligence, 2001, 127(1):57-85.
[18] HE J, YAO X. From an individual to a population:an analysis of the first hitting time of population-based evolutionary algorithms[J]. IEEE transactions on evolutionary computation, 2002, 6(5):495-511.
[19] GUTJAHR W J. A graph-based ant system and its convergence[J]. Future generation computer systems, 2000, 16(8):873-888.
[20] STVTZLE T, DORIGO M. A short convergence proof for a class of ACO algorithms[J]. IEEE transactions on evolutionary computation, 2002, 6(4):358-365.
[21] GUTJAHR W J. On the finite-time dynamics of ant colony optimization[J]. Methodology and computing in applied probability, 2006, 8(1):105-133.
[22] 黄翰, 郝志峰, 吴春国,等. 蚁群算法的收敛速度分析[J]. 计算机学报, 2007, 30(8):1344-1353. HUANG Han, HAO Zhifeng, WU Chunguo, et al. The convergence speed of ant colony optimization[J]. Chinese journal of computers, 2007, 30(8):1344-1353.
[23] BIRATTARI M, Dicaro G, DORIGO M. Toward the formal foundation of ant programming[M]//DORIGO M, DI CARO G, SAMPELS M. Ant Algorithms. Berlin Heidelberg:Springer-Verlag, 2002, 2463:188-201.
[24] MEULEAU N, DORIGO M. Ant colony optimization and stochastic gradient descent[J]. Artificial life, 2002, 8(2):103-121.
[25] ZLOCHIN M, BIRATTARI M, MEULEAU N, et al. Model-based search for combinatorial optimization:a critical survey[J]. Annals of operations research, 2004, 131(1-4):373-395.
[26] GUTJAHR W J. A generalized convergence result for the graph-based ant system metaheuristic[J]. Probability in the engineering and informational sciences, 2003, 17(4):545-569.
[27] NEUMANN F, WITT C. Runtime analysis of a simple ant colony optimization algorithm[C]//Proceedings of the 17th International Symposium on Algorithms, ISAAC 2006. Kolkata, India, 2006, 4288:618-627.
[28] NEUMANN F, SUDHOLT D, Wit C. Comparing variants of MMAS ACO algorithms on pseudo-Boolean functions[C]//Proceedings of International Workshop, SLS 2007. Brussels, Belgium, 2007:61-75.
[29] NEUMANN F, WITT C. Runtime analysis of a simple ant colony optimization algorithm[J]. Algorithmica, 2009, 54(2):243-255.
[30] GUTJAHR W J. First steps to the runtime complexity analysis of ant colony optimization[J]. Computers & operations research, 2008, 35(9):2711-2727.
[31] DOERR B, JOHANNSEN D. Refined runtime analysis of a basic ant colony optimization algorithm[C]//Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2007). Singapore, 2007:501-507.
[32] DOERR B, NEUMANN F, SUDHOLT D, et al. On the runtime analysis of the 1-ANT ACO algorithm[C]//Proceedings of Genetic and Evolutionary Computation Conference (GECCO’2007). London, England, 2007:33-40.
[33] DOERR B, NEUMANN F, SUDHOL D, et al. Runtime analysis of the 1-ANT ant colony optimizer[J]. Theoretical computer science, 2011, 412(17):1629-1644.
[34] GUTJAHR W J, SEBASTIANI G. Runtime analysis of ant colony optimization with best-so-far reinforcement[J]. Methodology and computing in applied probability, 2008, 10(3):409-433.
[35] NEUMANN F, SUDHOLT D, WITT C. Analysis of different MMAS ACO algorithms on unimodal functions and plateaus[J]. Swarm intelligence, 2009, 3(1):35-68.
[36] NEUMANN F, SUDHOLT D, WITT C. A few ants are enough:ACO with Iteration-best update[C]//Proceedings of Genetic and Evolutionary Computation Conference (GECCO’2010). Portland, USA, 2010:63-70.
[37] K?TZING T, NEUMANN F, SUDHOLT D, et al. Simple Max-Min ant systems and the optimization of linear pseudo-Boolean functions[C]//Proceedings of the 11th Work-shop on Foundations of Genetic Algorithms (FOGA 2011). New York, NY, USA, 2011:209-218.
[38] NEUMANN F, SUDHOLT D, WITT C. Rigorous analyses for the combination of ant colony optimization and local search[C]//Proceedings of the 6th International Conference on Ant Colony Optimization and Swarm Intelligence (ANTS08). Brussels, Belgium, 2008:132-143.
[39] NEUMANN F, WITT C. Ant colony optimization and the minimum spanning tree problem[J]. Theoretical computer science, 2010, 411(25):2406-2413.
[40] K?TZING T, LEHRE P K, OLIVETO P S, et al. Ant colony optimization and the minimum cut problem[C]//Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation Conference (GECCO’10). New York, NY, USA, 2010:1393-1400.
[41] ATTIRATANASUNTHRON N, FAKCHAROENPHOL J. A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs[J]. Information processing letters, 2008, 105(3):88-92.
[42] SUDHOLT D, THYSSEN C. Running time analysis of Ant Colony Optimization for shortest path problems[J]. Journal of discrete algorithms, 2012, 10:165-180.
[43] SUDHOLT D, THYSSEN C. A simple ant colony optimizer for stochastic shortest path problems[J]. Algorithmica, 2012, 64(4):643-672.
[44] LISSOVOI A, WITT C. Runtime analysis of ant colony optimization on dynamic shortest path problems[J]. Theoretical computer science, 2015, 561:73-85.
[45] ZHOU Y R. Runtime analysis of an ant colony optimization algorithm for TSP instances[J]. IEEE transactions on evolutionary computation, 2009, 13(5):1083-1092.
[46] K?TZING T, NEUMANN F, R?GLIN H, et al. Theoretical analysis of two ACO approaches for the traveling sales man problem[J]. Swarm intelligence, 2012, 6(1):1-21.
[47] LISSOVOI A, WITT C. MMAS versus population-based EA on a family of dynamic fitness functions[J]. Algorithmica, 2015, doi:10.1007/s00453-015-9975-z.
Similar References:

Memo

-

Last Update: 1900-01-01

Copyright © CAAI Transactions on Intelligent Systems