第11卷第1期 智能系统学报 Vol.11 No.1 2016年2月 CAAI Transactions on Intelligent Systems Feh.2016 D0I:10.11992/is.201510002 网络出版地址：http:/www.cnki.net/kcms/detail/23.1538.TP.20160105.1532.006.html 蚁群优化算法的理论研究进展 夏小云12，周育人3 (1.江西理工大学信息工程学院，江西赣州341000：2.华南理工大学计算机与工程学院，广东广州510006： 3.中山大学数据科学与计算机学院，广东广州510006) 摘要：蚁群优化算法的理论研究有助于更好地理解算法的原理以及指导算法应用。回顾了蚁群优化算法的收敛 性分析、时间复杂度分析与近似性能分析等理论研究进展，分析了其理论研究的对象从简单的拟布尔函数转为组合 优化问题以及实际应用问题。从蚁群算法理论分析方法和研究问题类型2个方面对蚁群算法的理论研究进行综 述。介绍了适应值划分、漂移分析等最基本的数学分析工具，对时间复杂性及近似性能等重要问题进行了探讨。总 结比较了蚁群算法求解各类问题的性能，指出这些研究能够更加深入了解蚁群算法的运行机制。最后，探讨了目前 蚁群算法理论研究中亟待解决的问题，指出引入新的分析工具以及研究更为复杂的算法模型等是值得进一步研究 的方向和内容。 关键词：蚁群优化算法：理论研究：组合优化：收敛性：时间复杂度：近似性能 中图分类号：TP18:TP301.6文献标志码：A文章编号：1673-4785(2016)01-0027-10 中文引用格式：夏小云，周育人.蚊群优化算法的理论研究进展[J].智能系统学报，2016,11(1)：2736. 英文引用格式：XIA Xiaoyun,ZHOU Yuren.Advances in theoretical research of ant colony optimization[J】.CAAI Transactions on Intelligent Systems,2016,11(1):27-36. Advances in theoretical research of ant colony optimization XIA Xiaoyun'.2,ZHOU Yuren (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) Abstract:Theoretical investigations of the ant colony optimization (ACO)algorithm can help to improve our under- standing 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 objec- tives 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 mathe- matical analysis tools,including fitness value partitioning and drift analysis,and discuss important ACO issues,in- cluding 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 ana- lytical tools and the study of more complicated algorithmic models. Keywords:ant colony optimization;theoretical research;combinatorial optimization;convergence;time complexi- ty:approximation performance 随机启发式搜索(randomized search heuristics, 应用中取得了丰富的成果。这类启发式算法主要包 R$Hs)算法是近年来发展较快的研究领域，在许多 括随机局部搜索(randomized local search,RLS)、禁 忌搜索(tabu search)、模拟退火(simulated annea- 收稿日期：2015-10-07.网络出版日期：2016-01-05. 基金项目：国家自然科学基金资助项目(61170081,61472143)：江西省 ling,SA)、演化算法(evolutionary algorithms,EAs) 自然科学基金资助项目(20151BAB217008). 以及粒子群优化算法(particle swarm optimization, 通信作者：周育人.E-mail:yrzhou@scut.cdu.cn.第 １１ 卷第 １ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．１ ２０１６ 年 ２ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｆｅｂ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１５１０００２ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０１０５．１５３２．００６．ｈｔｍｌ 蚁群优化算法的理论研究进展 夏小云１，２ ，周育人３ （１．江西理工大学 信息工程学院，江西 赣州 ３４１０００；２．华南理工大学 计算机与工程学院，广东 广州 ５１０００６； ３．中山大学 数据科学与计算机学院，广东 广州 ５１０００６） 摘 要：蚁群优化算法的理论研究有助于更好地理解算法的原理以及指导算法应用。 回顾了蚁群优化算法的收敛 性分析、时间复杂度分析与近似性能分析等理论研究进展，分析了其理论研究的对象从简单的拟布尔函数转为组合 优化问题以及实际应用问题。 从蚁群算法理论分析方法和研究问题类型 ２ 个方面对蚁群算法的理论研究进行综 述。 介绍了适应值划分、漂移分析等最基本的数学分析工具，对时间复杂性及近似性能等重要问题进行了探讨。 总 结比较了蚁群算法求解各类问题的性能，指出这些研究能够更加深入了解蚁群算法的运行机制。 最后，探讨了目前 蚁群算法理论研究中亟待解决的问题，指出引入新的分析工具以及研究更为复杂的算法模型等是值得进一步研究 的方向和内容。 关键词：蚁群优化算法；理论研究；组合优化；收敛性；时间复杂度；近似性能 中图分类号：ＴＰ１８； ＴＰ３０１．６ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０１⁃００２７⁃１０ 中文引用格式：夏小云，周育人．蚁群优化算法的理论研究进展［Ｊ］． 智能系统学报， ２０１６， １１（１）： ２７⁃３６． 英文引用格式：ＸＩＡ Ｘｉａｏｙｕｎ，ＺＨＯＵ Ｙｕｒｅｎ． Ａｄｖａｎｃｅｓ ｉｎ ｔｈｅｏｒｅｔｉｃａｌ ｒｅｓｅａｒｃｈ ｏｆ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１６， １１（１）： ２７⁃３６． Ａｄｖａｎｃｅｓ ｉｎ ｔｈｅｏｒｅｔｉｃａｌ ｒｅｓｅａｒｃｈ ｏｆ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ＸＩＡ Ｘｉａｏｙｕｎ １， ２ ，ＺＨＯＵ Ｙｕｒｅｎ ３ （１． Ｓｃｈｏｏｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｊｉａｎｇｘｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｇａｎｚｈｏｕ ３４１０００， Ｃｈｉｎａ； ２． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｓｏｕｔｈ Ｃｈｉｎａ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｇｕａｎｇｚｈｏｕ ５１０００６， Ｃｈｉｎａ； ３． Ｓｃｈｏｏｌ ｏｆ Ｄａｔａ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， Ｓｕｎ Ｙａｔ⁃Ｓｅｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｇｕａｎｇｚｈｏｕ ５１０００６， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅｏｒｅｔｉｃａｌ ｉｎｖｅｓｔｉｇａｔｉｏｎｓ ｏｆ ｔｈｅ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ （ＡＣＯ） ａｌｇｏｒｉｔｈｍ ｃａｎ ｈｅｌｐ ｔｏ ｉｍｐｒｏｖｅ ｏｕｒ ｕｎｄｅｒ⁃ ｓｔａｎｄｉｎｇ ｏｆ ｔｈｅ ｔｈｅｏｒｅｔｉｃａｌ ｂａｓｉｓ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ａｎｄ ｇｕｉｄｅ ｉｔｓ ａｐｐｒｏｐｒｉａｔｅ ａｐｐｌｉｃａｔｉｏｎ． Ｔｈｅｏｒｅｔｉｃａｌ ｒｅｓｅａｒｃｈ ｏｎ ＡＣＯ ｈａｓ ｉｎｃｌｕｄｅｄ ａｎａｌｙｓｅｓ ｏｆ ｅａｒｌｙ ｃｏｎｖｅｒｇｅｎｃｅ， ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ， ａｎｄ ａｐｐｒｏｘｉｍａｔｉｏｎ ｐｅｒｆｏｒｍａｎｃｅ． Ｉｎｖｅｓｔｉｇａｔｉｏｎ ｏｂｊｅｃ⁃ ｔｉｖｅｓ ｈａｖｅ ｒａｎｇｅｄ ｆｒｏｍ ｓｉｍｐｌｅ Ｂｏｏｌｅａｎ ｆｕｎｃｔｉｏｎｓ， ｔｏ ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ ｐｒａｃｔｉｃａｌ ａｐｐｌｉｃａｔｉｏｎ ｐｒｏｂｌｅｍｓ， ｔｏ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ＮＰ⁃ｈａｒｄｎｅｓｓ ｐｒｏｂｌｅｍｓ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｗｅ ｓｕｒｖｅｙ ｓｔａｔｅ⁃ｏｆ⁃ｔｈｅ⁃ａｒｔ ｔｈｅｏｒｅｔｉｃａｌ ＡＣＯ ｒｅｓｅａｒｃｈ ｆｒｏｍ ｔｗｏ ａｓｐｅｃｔｓ： ｔｈｅ ｍｏｓｔ ｃｏｍｍｏｎ ｍａｔｈｅｍａｔｉｃａｌ ｔｅｃｈｎｉｑｕｅｓ ａｎｄ ｔｈｏｓｅ ｌｅｓｓ ｃｏｍｍｏｎ． Ｉｎ ａｄｄｉｔｉｏｎ， ｗｅ ｉｎｔｒｏｄｕｃｅ ｔｗｏ ｍａｔｈｅ⁃ ｍａｔｉｃａｌ ａｎａｌｙｓｉｓ ｔｏｏｌｓ， ｉｎｃｌｕｄｉｎｇ ｆｉｔｎｅｓｓ ｖａｌｕｅ ｐａｒｔｉｔｉｏｎｉｎｇ ａｎｄ ｄｒｉｆｔ ａｎａｌｙｓｉｓ， ａｎｄ ｄｉｓｃｕｓｓ ｉｍｐｏｒｔａｎｔ ＡＣＯ ｉｓｓｕｅｓ， ｉｎ⁃ ｃｌｕｄｉｎｇ ＡＣＯ ｒｕｎｔｉｍｅ ａｎａｌｙｓｉｓ ａｎｄ ａｐｐｒｏｘｉｍａｔｉｏｎ ｐｅｒｆｏｒｍａｎｃｅ． Ｍｏｒｅ ｓｐｅｃｉｆｉｃａｌｌｙ， ｗｅ ｐｒｏｖｉｄｅ ｃｏｍｐａｒａｔｉｖｅ ｒｅｓｕｌｔｓ ｆｏｒ ＡＣＯ’ ｓ ｐｅｒｆｏｒｍａｎｃｅ ｉｎ ｓｏｌｖｉｎｇ ｖａｒｉｏｕｓ ｐｒｏｂｌｅｍｓ． Ｔｈｅｓｅ ｓｔｕｄｉｅｓ ｐｒｏｖｉｄｅ ａ ｄｉｒｅｃｔｉｏｎ ｆｏｒ ｂｅｔｔｅｒ ｕｎｄｅｒｓｔａｎｄｉｎｇ ｔｈｅ ｗｏｒｋｉｎｇ ｐｒｉｎｃｉｐｌｅｓ ｏｆ ＡＣＯ． Ｆｉｎａｌｌｙ， ｗｅ ｈｉｇｈｌｉｇｈｔ ｆｕｒｔｈｅｒ ｒｅｓｅａｒｃｈ ｄｉｒｅｃｔｉｏｎｓ， ｉｎｃｌｕｄｉｎｇ ｔｈｅ ｉｎｔｒｏｄｕｃｔｉｏｎ ｏｆ ｎｅｗ ａｎａ⁃ ｌｙｔｉｃａｌ ｔｏｏｌｓ ａｎｄ ｔｈｅ ｓｔｕｄｙ ｏｆ ｍｏｒｅ ｃｏｍｐｌｉｃａｔｅｄ ａｌｇｏｒｉｔｈｍｉｃ ｍｏｄｅｌｓ． Ｋｅｙｗｏｒｄｓ：ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ； ｔｈｅｏｒｅｔｉｃａｌ ｒｅｓｅａｒｃｈ； ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ； ｃｏｎｖｅｒｇｅｎｃｅ； ｔｉｍｅ ｃｏｍｐｌｅｘｉ⁃ ｔｙ； ａｐｐｒｏｘｉｍａｔｉｏｎ ｐｅｒｆｏｒｍａｎｃｅ 收稿日期：２０１５⁃１０⁃０７． 网络出版日期：２０１６⁃０１⁃０５． 基金项目：国家自然科学基金资助项目（ ６１１７００８１， ６１４７２１４３）；江西省 自然科学基金资助项目（２０１５１ＢＡＢ２１７００８）． 通信作者：周育人．Ｅ⁃ｍａｉｌ：ｙｒｚｈｏｕ＠ ｓｃｕｔ．ｅｄｕ．ｃｎ． 随机启发式搜索（ ｒａｎｄｏｍｉｚｅｄ ｓｅａｒｃｈ ｈｅｕｒｉｓｔｉｃｓ， ＲＳＨｓ）算法是近年来发展较快的研究领域，在许多 应用中取得了丰富的成果。 这类启发式算法主要包 括随机局部搜索（ｒａｎｄｏｍｉｚｅｄ ｌｏｃａｌ ｓｅａｒｃｈ， ＲＬＳ）、禁 忌搜索（ ｔａｂｕ ｓｅａｒｃｈ）、模拟退火 （ ｓｉｍｕｌａｔｅｄ ａｎｎｅａ⁃ ｌｉｎｇ， ＳＡ） 、演化算法（ ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍｓ， ＥＡｓ） 以及粒子群优化算法（ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ