[1]夏小云,周育人.蚁群优化算法的理论研究进展[J].智能系统学报编辑部,2016,11(1):27-36.[doi:10.11992/tis.201510002]
 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]
点击复制

蚁群优化算法的理论研究进展(/HTML)
分享到:

《智能系统学报》编辑部[ISSN:1673-4785/CN:23-1538/TP]

卷:
第11卷
期数:
2016年1期
页码:
27-36
栏目:
出版日期:
2016-02-25

文章信息/Info

Title:
Advances in theoretical research of ant colony optimization
作者:
夏小云12 周育人3
1. 江西理工大学信息工程学院, 江西赣州 341000;
2. 华南理工大学计算机与工程学院, 广东广州 510006;
3. 中山大学数据科学与计算机学院, 广东广州 510006
Author(s):
XIA Xiaoyun12 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 optimizationtheoretical researchcombinatorial optimizationconvergencetime complexityapproximation performance
分类号:
TP18;TP301.6
DOI:
10.11992/tis.201510002
摘要:
蚁群优化算法的理论研究有助于更好地理解算法的原理以及指导算法应用。回顾了蚁群优化算法的收敛性分析、时间复杂度分析与近似性能分析等理论研究进展,分析了其理论研究的对象从简单的拟布尔函数转为组合优化问题以及实际应用问题。从蚁群算法理论分析方法和研究问题类型2个方面对蚁群算法的理论研究进行综述。介绍了适应值划分、漂移分析等最基本的数学分析工具,对时间复杂性及近似性能等重要问题进行了探讨。总结比较了蚁群算法求解各类问题的性能,指出这些研究能够更加深入了解蚁群算法的运行机制。最后,探讨了目前蚁群算法理论研究中亟待解决的问题,指出引入新的分析工具以及研究更为复杂的算法模型等是值得进一步研究的方向和内容。
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.

相似文献/References:

[1]裴小兵,张春花.应用改进区块遗传算法求解置换流水车间调度问题[J].智能系统学报编辑部,2019,14(03):541.[doi:10.11992/tis.201801041]
 PEI Xiaobing,ZHANG Chunhua.An improved puzzle-based genetic algorithm for solving permutation flow-shop scheduling problems[J].CAAI Transactions on Intelligent Systems,2019,14(1):541.[doi:10.11992/tis.201801041]

备注/Memo

备注/Memo:
收稿日期:2015-10-07;改回日期:。
基金项目:国家自然科学基金资助项目(61170081,61472143);江西省自然科学基金资助项目(20151BAB217008).
作者简介:夏小云,男,1982年生,博士研究生,主要研究方向为计算智能与机器学习;周育人,男,1965年生,教授,博士生导师,博士,主要研究方向为计算智能、数据挖掘及社会网络。主持国家、省部级项目多项,发表学术论文50余篇。
通讯作者:周育人.E-mail:yrzhou@scut.edu.cn.
更新日期/Last Update: 1900-01-01