【综述】蚁群优化算法的理论研究进展编辑部

第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

第 １１ 卷第 １ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．１ ２０１６ 年 ２ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｆｅｂ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１５１０００２ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０１０５．１５３２．００６．ｈｔｍｌ 蚁群优化算法的理论研究进展 夏小云１，２ ，周育人３ （１．江西理工大学 信息工程学院，江西 赣州 ３４１０００；２．华南理工大学 计算机与工程学院，广东 广州 ５１０００６； ３．中山大学 数据科学与计算机学院，广东 广州 ５１０００６） 摘 要：蚁群优化算法的理论研究有助于更好地理解算法的原理以及指导算法应用。 回顾了蚁群优化算法的收敛 性分析、时间复杂度分析与近似性能分析等理论研究进展，分析了其理论研究的对象从简单的拟布尔函数转为组合 优化问题以及实际应用问题。 从蚁群算法理论分析方法和研究问题类型 ２ 个方面对蚁群算法的理论研究进行综 述。 介绍了适应值划分、漂移分析等最基本的数学分析工具，对时间复杂性及近似性能等重要问题进行了探讨。 总 结比较了蚁群算法求解各类问题的性能，指出这些研究能够更加深入了解蚁群算法的运行机制。 最后，探讨了目前 蚁群算法理论研究中亟待解决的问题，指出引入新的分析工具以及研究更为复杂的算法模型等是值得进一步研究 的方向和内容。 关键词：蚁群优化算法；理论研究；组合优化；收敛性；时间复杂度；近似性能 中图分类号：ＴＰ１８； ＴＰ３０１．６ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０１⁃００２７⁃１０ 中文引用格式：夏小云，周育人．蚁群优化算法的理论研究进展［Ｊ］． 智能系统学报， ２０１６， １１（１）： ２７⁃３６． 英文引用格式：ＸＩＡ Ｘｉａｏｙｕｎ，ＺＨＯＵ Ｙｕｒｅｎ． Ａｄｖａｎｃｅｓ ｉｎ ｔｈｅｏｒｅｔｉｃａｌ ｒｅｓｅａｒｃｈ ｏｆ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１６， １１（１）： ２７⁃３６． Ａｄｖａｎｃｅｓ ｉｎ ｔｈｅｏｒｅｔｉｃａｌ ｒｅｓｅａｒｃｈ ｏｆ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ＸＩＡ Ｘｉａｏｙｕｎ １， ２ ，ＺＨＯＵ Ｙｕｒｅｎ ３ （１． Ｓｃｈｏｏｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｊｉａｎｇｘｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｇａｎｚｈｏｕ ３４１０００， Ｃｈｉｎａ； ２． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｓｏｕｔｈ Ｃｈｉｎａ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｇｕａｎｇｚｈｏｕ ５１０００６， Ｃｈｉｎａ； ３． Ｓｃｈｏｏｌ ｏｆ Ｄａｔａ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， Ｓｕｎ Ｙａｔ⁃Ｓｅｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｇｕａｎｇｚｈｏｕ ５１０００６， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅｏｒｅｔｉｃａｌ ｉｎｖｅｓｔｉｇａｔｉｏｎｓ ｏｆ ｔｈｅ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ （ＡＣＯ） ａｌｇｏｒｉｔｈｍ ｃａｎ ｈｅｌｐ ｔｏ ｉｍｐｒｏｖｅ ｏｕｒ ｕｎｄｅｒ⁃ ｓｔａｎｄｉｎｇ ｏｆ ｔｈｅ ｔｈｅｏｒｅｔｉｃａｌ ｂａｓｉｓ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ａｎｄ ｇｕｉｄｅ ｉｔｓ ａｐｐｒｏｐｒｉａｔｅ ａｐｐｌｉｃａｔｉｏｎ． Ｔｈｅｏｒｅｔｉｃａｌ ｒｅｓｅａｒｃｈ ｏｎ ＡＣＯ ｈａｓ ｉｎｃｌｕｄｅｄ ａｎａｌｙｓｅｓ ｏｆ ｅａｒｌｙ ｃｏｎｖｅｒｇｅｎｃｅ， ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ， ａｎｄ ａｐｐｒｏｘｉｍａｔｉｏｎ ｐｅｒｆｏｒｍａｎｃｅ． Ｉｎｖｅｓｔｉｇａｔｉｏｎ ｏｂｊｅｃ⁃ ｔｉｖｅｓ ｈａｖｅ ｒａｎｇｅｄ ｆｒｏｍ ｓｉｍｐｌｅ Ｂｏｏｌｅａｎ ｆｕｎｃｔｉｏｎｓ， ｔｏ ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ ｐｒａｃｔｉｃａｌ ａｐｐｌｉｃａｔｉｏｎ ｐｒｏｂｌｅｍｓ， ｔｏ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ＮＰ⁃ｈａｒｄｎｅｓｓ ｐｒｏｂｌｅｍｓ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｗｅ ｓｕｒｖｅｙ ｓｔａｔｅ⁃ｏｆ⁃ｔｈｅ⁃ａｒｔ ｔｈｅｏｒｅｔｉｃａｌ ＡＣＯ ｒｅｓｅａｒｃｈ ｆｒｏｍ ｔｗｏ ａｓｐｅｃｔｓ： ｔｈｅ ｍｏｓｔ ｃｏｍｍｏｎ ｍａｔｈｅｍａｔｉｃａｌ ｔｅｃｈｎｉｑｕｅｓ ａｎｄ ｔｈｏｓｅ ｌｅｓｓ ｃｏｍｍｏｎ． Ｉｎ ａｄｄｉｔｉｏｎ， ｗｅ ｉｎｔｒｏｄｕｃｅ ｔｗｏ ｍａｔｈｅ⁃ ｍａｔｉｃａｌ ａｎａｌｙｓｉｓ ｔｏｏｌｓ， ｉｎｃｌｕｄｉｎｇ ｆｉｔｎｅｓｓ ｖａｌｕｅ ｐａｒｔｉｔｉｏｎｉｎｇ ａｎｄ ｄｒｉｆｔ ａｎａｌｙｓｉｓ， ａｎｄ ｄｉｓｃｕｓｓ ｉｍｐｏｒｔａｎｔ ＡＣＯ ｉｓｓｕｅｓ， ｉｎ⁃ ｃｌｕｄｉｎｇ ＡＣＯ ｒｕｎｔｉｍｅ ａｎａｌｙｓｉｓ ａｎｄ ａｐｐｒｏｘｉｍａｔｉｏｎ ｐｅｒｆｏｒｍａｎｃｅ． Ｍｏｒｅ ｓｐｅｃｉｆｉｃａｌｌｙ， ｗｅ ｐｒｏｖｉｄｅ ｃｏｍｐａｒａｔｉｖｅ ｒｅｓｕｌｔｓ ｆｏｒ ＡＣＯ’ ｓ ｐｅｒｆｏｒｍａｎｃｅ ｉｎ ｓｏｌｖｉｎｇ ｖａｒｉｏｕｓ ｐｒｏｂｌｅｍｓ． Ｔｈｅｓｅ ｓｔｕｄｉｅｓ ｐｒｏｖｉｄｅ ａ ｄｉｒｅｃｔｉｏｎ ｆｏｒ ｂｅｔｔｅｒ ｕｎｄｅｒｓｔａｎｄｉｎｇ ｔｈｅ ｗｏｒｋｉｎｇ ｐｒｉｎｃｉｐｌｅｓ ｏｆ ＡＣＯ． Ｆｉｎａｌｌｙ， ｗｅ ｈｉｇｈｌｉｇｈｔ ｆｕｒｔｈｅｒ ｒｅｓｅａｒｃｈ ｄｉｒｅｃｔｉｏｎｓ， ｉｎｃｌｕｄｉｎｇ ｔｈｅ ｉｎｔｒｏｄｕｃｔｉｏｎ ｏｆ ｎｅｗ ａｎａ⁃ ｌｙｔｉｃａｌ ｔｏｏｌｓ ａｎｄ ｔｈｅ ｓｔｕｄｙ ｏｆ ｍｏｒｅ ｃｏｍｐｌｉｃａｔｅｄ ａｌｇｏｒｉｔｈｍｉｃ ｍｏｄｅｌｓ． Ｋｅｙｗｏｒｄｓ：ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ； ｔｈｅｏｒｅｔｉｃａｌ ｒｅｓｅａｒｃｈ； ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ； ｃｏｎｖｅｒｇｅｎｃｅ； ｔｉｍｅ ｃｏｍｐｌｅｘｉ⁃ ｔｙ； ａｐｐｒｏｘｉｍａｔｉｏｎ ｐｅｒｆｏｒｍａｎｃｅ 收稿日期：２０１５⁃１０⁃０７． 网络出版日期：２０１６⁃０１⁃０５． 基金项目：国家自然科学基金资助项目（ ６１１７００８１， ６１４７２１４３）；江西省 自然科学基金资助项目（２０１５１ＢＡＢ２１７００８）． 通信作者：周育人．Ｅ⁃ｍａｉｌ：ｙｒｚｈｏｕ＠ ｓｃｕｔ．ｅｄｕ．ｃｎ． 随机启发式搜索（ ｒａｎｄｏｍｉｚｅｄ ｓｅａｒｃｈ ｈｅｕｒｉｓｔｉｃｓ， ＲＳＨｓ）算法是近年来发展较快的研究领域，在许多 应用中取得了丰富的成果。 这类启发式算法主要包 括随机局部搜索（ｒａｎｄｏｍｉｚｅｄ ｌｏｃａｌ ｓｅａｒｃｈ， ＲＬＳ）、禁 忌搜索（ ｔａｂｕ ｓｅａｒｃｈ）、模拟退火 （ ｓｉｍｕｌａｔｅｄ ａｎｎｅａ⁃ ｌｉｎｇ， ＳＡ） 、演化算法（ ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍｓ， ＥＡｓ） 以及粒子群优化算法（ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ

·28 智能系统学报 第11卷 PS0)等。这些算法经常用来作为一些难解优化问 一步提出使用常微分方程逼近AC0随机过程，并基 题的近似求解方法。由于这类智能算法的智能性、 于此来对ACO算法的收敛速度进行粗糙的理论预 普适性以及全局搜索能力，使得其为求解NP难解 测。国内学者黄翰、郝志蜂等2)根据蚁群算法的特 优化问题开辟了一条新的途径。蚁群优化算法(ant 性，基于吸收态Markov过程的数学模型，提出了蚁 colony optimization,ACO)是这类算法的杰出代表 群算法的收敛速度分析理论，并给出了ACO-难和 之 ACO-易两类问题的界定方法。蚁群算法理论研究 蚁群算法是受蚂蚁群体觅食行为的启发，由意 的另一个方向是将蚁群算法和其他学习算法进行比 大利学者Dorigo等]提出的一种基于种群的模拟 较，如Birattari2】、Meuleau2]等分别建立了ACO 进化算法。蚂蚁觅食过程中借助于信息素(phero- 与最优控制加强学习算法、随机梯度下降算法的 mone)这种化学物质进行信息的交流和传递，能够 联系。 根据所走路径长度自主选择下一个将要行走的地 近年来，以遗传算法为基础的演化算法时间复 方，并表现出正反馈现象。这种正反馈机制能帮助 杂性研究取得了一些重要进展。以Drostel山、We 蚂蚁很快找到最优觅食路径。蚁群算法以信息素更 gener!等为代表的德国学派分析了群体规模为】 新和概率转移为基本操作，并以此指导搜索方向。 的简单爬山演化算法(1+1)EA求解一些拟布尔函 蚁群算法作为一种新型的智能仿生类进化算法，已 数(OneMax,LeadingOnes,Trap Function)的平均计 在许多领域获得了广泛的应用。例如在TSP(rave- 算时间，取得了一系列研究成果。He Jun和Yao Xin使用吸收马尔可夫链[16]、漂移分析]等工具建 ling salesman problem)问题、二次规划问题、函数优 化、网络路由优化、机器人路径规划、数据挖掘、作业 立演化算法时间复杂性分析模型和方法以及分析群 流程规划、图形着色等领域获得了广泛的应用，并取 体在演化算法时间复杂性分析中的作用)等。这 得了较好的效果，具体可以参考张军等的译著)。 些研究极大地激发和推动了蚁群算法的理论研究工 此外，国内学者段海滨等[4)对蚁群算法的应用领域 作。 蚁群算法最初用于旅行商问题的求解，进而推 的研究成果做了较全面的综述。 广到各种组合优化问题（甚至连续函数优化问题）。 自从蚁群算法提出后，许多研究者在蚁群算法 Dorigo和Blum3)总结了截至2005年蚁群算法理论 的设计及应用方面取得了丰富的研究成果。大量的 研究及应用中取得的阶段性研究成果，并特别指出 实验也表明其针对一些优化问题的求解非常有效。 蚁群算法时间复杂性将是今后一个重要的、有意义 然而，从理论上来看，蚁群算法缺乏比较完备的理论 的研究方向，将其列为蚁群算法理论研究的公开性 基础。目前更迫切地希望为该算法建立坚实的理论 问题。 基础[0，)]，以帮助更好地理解算法的运行机制，了 时间复杂度研究是指算法找到优化问题最优解 解算法对于求解什么类型的问题有效。为算法的设 或近似最优解的计算时间，是衡量算法性能最基本、 计，参数选取以及算法的运用指明改进的方向。当 最重要的指标。W.J.Gutjahr]总结了截止2007年 前蚁群算法理论研究远远落后于算法的数值实验和 的蚁群算法时间复杂性研究成果和方法，并指出了 真实应用，主要原因在于随机启发式算法理论分析 一些发展方向。目前，蚁群算法时间复杂性研究正 的艰难性。蚁群算法具有随机性、群体性、普适 处于启动阶段，研究内容、深度都非常有限，很多基 性等特性，这些特征使得算法表现出复杂的动态行 本问题尚未涉及。当前仅仅研究了蚂蚁规模为1的 为，由此引出的复杂多变的随机过程增加了算法理 1-ANT的情形，而与真实的蚁群算法相关的问题，如 论分析的难度，经典算法设计与分析的方法和工具 多蚂蚁蚁群系统求解真实的组合优化问题等，都有 也难以直接应用于这类新型随机仿生算法。 待深入研究。可以预计，这些研究将会有重要意义， 在2006年之前，研究人员主要关注于AC0收 同时又将是富有挑战性的、艰难的工作。目前ACO 敛性分析21,2以及AC0算法与其他优化算法的 算法理论研究主要是关于一些人工拟布尔函数以及 关系[2s],从理论上探素算法为什么有效。Gutjahr!町 ,些经典的组合优化问题的时间复杂性分析。最具 提出了一个基于图的蚂蚁系统(graph-based ant sys- 代表性的如国内学者Zhou Yuren【as)研究了AC0求 tem,GBAS),Gutjahr首次证明了该模型蚁群算法 解经典TSP问题的时间复杂度，这也是ACO算法在 在一定条件下以概率1-￡收敛到最优解，其中ε为 NP难解问题理论分析上的首项工作。 任意小的常数且s>0。Stutzle and Dorigo20等给出 一般情况下，对于典型的难问题一NP-完全 了普通蚁群算法(ant colony system,ACS)和MMAS ()non-deterministic polynomial-complete hard) (max-min ant system)的收敛性证明。Gutjahr2]进 化问题，人们找不到多项式时间的确定性算法。由

ＰＳＯ）等。 这些算法经常用来作为一些难解优化问 题的近似求解方法。 由于这类智能算法的智能性、 普适性以及全局搜索能力，使得其为求解 ＮＰ 难解 优化问题开辟了一条新的途径。 蚁群优化算法（ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ， ＡＣＯ） 是这类算法的杰出代表 之一。 蚁群算法是受蚂蚁群体觅食行为的启发，由意 大利学者 Ｄｏｒｉｇｏ 等［１］ 提出的一种基于种群的模拟 进化算法。 蚂蚁觅食过程中借助于信息素（ ｐｈｅｒｏ⁃ ｍｏｎｅ）这种化学物质进行信息的交流和传递，能够 根据所走路径长度自主选择下一个将要行走的地 方，并表现出正反馈现象。 这种正反馈机制能帮助 蚂蚁很快找到最优觅食路径。 蚁群算法以信息素更 新和概率转移为基本操作，并以此指导搜索方向。 蚁群算法作为一种新型的智能仿生类进化算法，已 在许多领域获得了广泛的应用。 例如在 ＴＳＰ（ｔｒａｖｅ⁃ ｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ）问题、二次规划问题、 函数优 化、网络路由优化、机器人路径规划、数据挖掘、作业 流程规划、图形着色等领域获得了广泛的应用，并取 得了较好的效果，具体可以参考张军等的译著［２］ 。 此外，国内学者段海滨等［４］ 对蚁群算法的应用领域 的研究成果做了较全面的综述。 自从蚁群算法提出后，许多研究者在蚁群算法 的设计及应用方面取得了丰富的研究成果。 大量的 实验也表明其针对一些优化问题的求解非常有效。 然而，从理论上来看，蚁群算法缺乏比较完备的理论 基础。 目前更迫切地希望为该算法建立坚实的理论 基础［１０，１３］ ，以帮助更好地理解算法的运行机制，了 解算法对于求解什么类型的问题有效。 为算法的设 计，参数选取以及算法的运用指明改进的方向。 当 前蚁群算法理论研究远远落后于算法的数值实验和 真实应用，主要原因在于随机启发式算法理论分析 的艰难性［１５］ 。 蚁群算法具有随机性、群体性、普适 性等特性，这些特征使得算法表现出复杂的动态行 为，由此引出的复杂多变的随机过程增加了算法理 论分析的难度，经典算法设计与分析的方法和工具 也难以直接应用于这类新型随机仿生算法。 在 ２００６ 年之前，研究人员主要关注于 ＡＣＯ 收 敛性分析［１９⁃２１，２６］以及 ＡＣＯ 算法与其他优化算法的 关系［２５］ ，从理论上探索算法为什么有效。 Ｇｕｔｊａｈｒ ［１９］ 提出了一个基于图的蚂蚁系统（ｇｒａｐｈ⁃ｂａｓｅｄ ａｎｔ ｓｙｓ⁃ ｔｅｍ， ＧＢＡＳ）， Ｇｕｔｊａｈｒ 首次证明了该模型蚁群算法 在一定条件下以概率 １⁃ε 收敛到最优解，其中 ε 为 任意小的常数且 ε＞０。 Ｓｔüｔｚｌｅ ａｎｄ Ｄｏｒｉｇｏ ［２０］ 等给出 了普通蚁群算法（ ａｎｔ ｃｏｌｏｎｙ ｓｙｓｔｅｍ，ＡＣＳ） 和 ＭＭＡＳ （ｍａｘ⁃ｍｉｎ ａｎｔ ｓｙｓｔｅｍ） 的收敛性证明。 Ｇｕｔｊａｈｒ ［２１］ 进 一步提出使用常微分方程逼近 ＡＣＯ 随机过程，并基 于此来对 ＡＣＯ 算法的收敛速度进行粗糙的理论预 测。 国内学者黄翰、郝志峰等［２２］ 根据蚁群算法的特 性，基于吸收态 Ｍａｒｋｏｖ 过程的数学模型，提出了蚁 群算法的收敛速度分析理论，并给出了 ＡＣＯ⁃难和 ＡＣＯ⁃易两类问题的界定方法。 蚁群算法理论研究 的另一个方向是将蚁群算法和其他学习算法进行比 较， 如 Ｂｉｒａｔｔａｒｉ ［２３］ 、Ｍｅｕｌｅａｕ ［２４］ 等分别建立了 ＡＣＯ 与最优控制加强学习算法、随机梯度下降算法的 联系。 近年来，以遗传算法为基础的演化算法时间复 杂性研究取得了一些重要进展。 以 Ｄｒｏｓｔｅ ［１１］ 、Ｗｅ⁃ ｇｅｎｅｒ ［１２］等为代表的德国学派分析了群体规模为 １ 的简单爬山演化算法（１＋１）ＥＡ 求解一些拟布尔函 数（ＯｎｅＭａｘ， ＬｅａｄｉｎｇＯｎｅｓ， Ｔｒａｐ Ｆｕｎｃｔｉｏｎ）的平均计 算时间，取得了一系列研究成果。 Ｈｅ Ｊｕｎ 和 Ｙａｏ Ｘｉｎ 使用吸收马尔可夫链［１６］ 、漂移分析［１７］等工具建 立演化算法时间复杂性分析模型和方法以及分析群 体在演化算法时间复杂性分析中的作用［１８］ 等。 这 些研究极大地激发和推动了蚁群算法的理论研究工 作。 蚁群算法最初用于旅行商问题的求解，进而推 广到各种组合优化问题（甚至连续函数优化问题）。 Ｄｏｒｉｇｏ 和 Ｂｌｕｍ ［３］ 总结了截至 ２００５ 年蚁群算法理论 研究及应用中取得的阶段性研究成果，并特别指出 蚁群算法时间复杂性将是今后一个重要的、有意义 的研究方向，将其列为蚁群算法理论研究的公开性 问题。 时间复杂度研究是指算法找到优化问题最优解 或近似最优解的计算时间，是衡量算法性能最基本、 最重要的指标。 Ｗ．Ｊ．Ｇｕｔｊａｈｒ ［１０］ 总结了截止 ２００７ 年 的蚁群算法时间复杂性研究成果和方法，并指出了 一些发展方向。 目前，蚁群算法时间复杂性研究正 处于启动阶段，研究内容、深度都非常有限，很多基 本问题尚未涉及。 当前仅仅研究了蚂蚁规模为 １ 的 １⁃ＡＮＴ 的情形，而与真实的蚁群算法相关的问题，如 多蚂蚁蚁群系统求解真实的组合优化问题等，都有 待深入研究。 可以预计，这些研究将会有重要意义， 同时又将是富有挑战性的、艰难的工作。 目前 ＡＣＯ 算法理论研究主要是关于一些人工拟布尔函数以及 一些经典的组合优化问题的时间复杂性分析。 最具 代表性的如国内学者 Ｚｈｏｕ Ｙｕｒｅｎ ［４５］研究了 ＡＣＯ 求 解经典 ＴＳＰ 问题的时间复杂度，这也是 ＡＣＯ 算法在 ＮＰ 难解问题理论分析上的首项工作。 一般情 况 下， 对 于 典 型 的 难 问 题—ＮＰ⁃完 全 （难） （ ｎｏｎ⁃ｄｅｔｅｒｍｉｎｉｓｔｉｃ ｐｏｌｙｎｏｍｉａｌ⁃ｃｏｍｐｌｅｔｅ ｈａｒｄ）优 化问题，人们找不到多项式时间的确定性算法。 由 ·２８· 智 能 系 统 学 报 第 １１ 卷

第1期 夏小云，等：蚁群优化算法的理论研究进展 ·29. 于NP难解组合优化问题本身结构的复杂性，确定 近似比r为：若为最大化问题，r=max f(D) 性算法（穷举法、分支界定、动态规划等）无法保证 ):若为最 在多项式内获得精确解，转而寻求一些近似算 (。也就是说，算法A能获得 小化问题，r=max A(D 法6。蚁群优化作为随机启发式方法，不能期待其 在多项式时间内找到NP-完全（难）优化问题所有实 r一近似比。若r=1,表明算法找到最优解。 例的精确解。实际上，蚁群算法在很多优化问题上 蚁群算法的启发来自于一个蚂蚁群体对食物源 扮演着近似算法的角色，一般用于获得满意解或者 的搜索，是一种杰出而具有代表性的群智能算法，对 近似解。因此蚁群优化算法的近似性能分析就变得 于其算法描述可以参考相关文献[1。AC0算法有 尤为重要。希望在平均多项式时间内获得近似最优 一些不同的变体，为了分析的方便，在当前理论分析 或者可接受的解，对于理解蚁群算法在NP难优化 方面，还是主要考虑一只蚂蚁的情况。下面给出蚁 问题上的工作原理以及寻求其能获得的近似性能非 群优化算法理论研究中用到的一个简单的ACO算 常关键，并将进一步推进蚁群算法的理论研究及应 法(1+1)蚂蚁算法((1+1)Ant Algorithm, 用进展。对于丰富和发展近似算法和组合优化理 (1+1)AA),其类似于演化算法理论分析中的 论，切实有效地解决一些实际问题具有重要现实意 (1+1)EA。不失一般性，考虑最小化问题。 义。 (1+1)AA算法描述如下 1 蚁群优化算法：模型、描述、变体 Algorithm 1:(1+1)AA Begin 1.1优化问题及算法描述 初始化：参数设置，信息素值，选择一个初始解 蚁群算法是一种随机启发式搜索方法，它具有 s,While(不满足终止条件) 较强的鲁棒性，优良的分布式计算机制并易于与其 使用构造过程构建一个新的解s': 他方法相结合等优，点。目前人们对蚁群算法的研究 选择：如果f(s')<f(s),则s=s';更新信息素值。 已经由当初单一的旅行商问题(TSP)领域渗透到了 End while 多个其他应用领域]，由解决一维、静态优化问题 End 发展到解决多维、动态优化问题，由离散求解空间逐 (1+1)AA算法使用简单的爬山选择策略，如果 渐拓展到连续求解空间，使得该群智能算法在科学 当前蚂蚁解的函数值大于新的蚂蚁解的函数值，则 研究及实际问题求解中表现出了巨大的潜力和 当前蚂蚁解被新蚂蚁解替代。以下两节分别介绍理 优势。 论分析中蚁群算法解的构建以及信息素更新机制。 优化问题可以分为两类：连续的优化问题和离 1.2解的构建 散的优化问题。连续的优化问题是指其具有连续的 对于一个给定的优化问题，其解通过蚂蚁在一 变量、经常需要计算导数、使用牛顿方法或者线性规 个具有信息素值的构造图(construction graph)的边 划技术等。本文关注的是离散的优化问题。离散优 上随机游走获得。另外，蚁群算法也使用启发式信 化问题也称为组合优化问题，是指在有限的或者可 息来指导随机游走的方向。蚂蚁从构造图的任意一 数无限的潜在解集中搜索满足给定约束条件的最优 个初始状态出发，随机游走到下一个邻域结点。这 解。然而，组合优化问题通常包含大量的局部极值 个移动是基于概率规则，依赖于信息素和启发式 点，而且许多组合优化问题为NP完全（难）问题。 信息。 一个组合优化问题P通常可描述为一个三元 令G=(V,E)为一给定问题的构造图。To为 组(S,f,2),其中S为给定的由所有状态构成的搜 边e=(u,u)∈E上的信息素值，nao为启发式信 索空间，f:S→R*为目标函数，一般为最大化或者最 息。假设蚂蚁当前所在位置为顶点“，其允许访问 小化；2为可行解满足的约束条件集合。一个可行 的后续结点为N.。蚂蚁在下一步访问结点v∈N, 解s·∈S,如果对于最小化问题有Hs∈S,f(s·)≤ 的概率由以下公式给出： f代s),对于最大化问题有s∈S,f(s·)≥f(s),则称 (ru)·(ne)B s·为一个全局最优解。定义最优解集合为S·二S, Pu=- 算法的目标是从优化问题的可行解集中找到最优解 ∑(r)·(m)日 回eN. s”eS°。 式中：参数α表示蚂蚁在运动过程中所积累的信息 给定算法A和优化问题P,对于一个给定的P 素在指导蚂蚊搜索路径的相对重要性：参数B表示 的实例I,其最优解为f(I)。如果算法A能在多项 路径能见度的相对重要性，即表示启发式信息， 式时间内获得最优解A(I),则算法A在问题P上的 的重要性

于 ＮＰ 难解组合优化问题本身结构的复杂性，确定 性算法（穷举法、分支界定、动态规划等） 无法保证 在多项 式 内 获 得 精 确 解， 转 而 寻 求 一 些 近 似 算 法［６］ 。 蚁群优化作为随机启发式方法，不能期待其 在多项式时间内找到 ＮＰ⁃完全（难）优化问题所有实 例的精确解。 实际上，蚁群算法在很多优化问题上 扮演着近似算法的角色，一般用于获得满意解或者 近似解。 因此蚁群优化算法的近似性能分析就变得 尤为重要。 希望在平均多项式时间内获得近似最优 或者可接受的解，对于理解蚁群算法在 ＮＰ 难优化 问题上的工作原理以及寻求其能获得的近似性能非 常关键，并将进一步推进蚁群算法的理论研究及应 用进展。 对于丰富和发展近似算法和组合优化理 论，切实有效地解决一些实际问题具有重要现实意 义。 １ 蚁群优化算法：模型、描述、变体 １．１ 优化问题及算法描述 蚁群算法是一种随机启发式搜索方法，它具有 较强的鲁棒性，优良的分布式计算机制并易于与其 他方法相结合等优点。 目前人们对蚁群算法的研究 已经由当初单一的旅行商问题（ＴＳＰ）领域渗透到了 多个其他应用领域［２］ ，由解决一维、静态优化问题 发展到解决多维、动态优化问题，由离散求解空间逐 渐拓展到连续求解空间，使得该群智能算法在科学 研究及实际问题求解中表现出了巨大的潜力和 优势。 优化问题可以分为两类：连续的优化问题和离 散的优化问题。 连续的优化问题是指其具有连续的 变量、经常需要计算导数、使用牛顿方法或者线性规 划技术等。 本文关注的是离散的优化问题。 离散优 化问题也称为组合优化问题，是指在有限的或者可 数无限的潜在解集中搜索满足给定约束条件的最优 解。 然而，组合优化问题通常包含大量的局部极值 点，而且许多组合优化问题为 ＮＰ 完全（难）问题。 一个组合优化问题 Ｐ 通常可描述为一个三元 组（ Ｓ，ｆ，Ω），其中 Ｓ 为给定的由所有状态构成的搜 索空间，ｆ：Ｓ→Ｒ ＋为目标函数，一般为最大化或者最 小化；Ω 为可行解满足的约束条件集合。 一个可行 解 ｓ ∗ ∈Ｓ，如果对于最小化问题有∀ｓ∈Ｓ，ｆ（ ｓ ∗ ）≤ ｆ（ｓ），对于最大化问题有∀ｓ∈Ｓ，ｆ（ｓ ∗ ）≥ｆ（ ｓ），则称 ｓ ∗为一个全局最优解。 定义最优解集合为Ｓ ∗⊆Ｓ， 算法的目标是从优化问题的可行解集中找到最优解 ｓ ∗∈Ｓ ∗ 。 给定算法 Ａ 和优化问题 Ｐ，对于一个给定的 Ｐ 的实例 Ｉ，其最优解为 ｆ ｏｐｔ（Ｉ）。 如果算法 Ａ 能在多项 式时间内获得最优解 Ａ（Ｉ），则算法 Ａ 在问题 Ｐ 上的 近似比 ｒ 为：若为最大化问题，ｒ ＝ ｍａｘ Ｉ∈Ｐ ｆ ｏｐｔ（Ｉ） Ａ（Ｉ） ；若为最 小化问题，ｒ ＝ｍａｘ Ｉ∈Ｐ Ａ（Ｉ） ｆ ｏｐｔ（Ｉ） 。 也就是说，算法 Ａ 能获得 ｒ－近似比。 若 ｒ ＝ １，表明算法找到最优解。 蚁群算法的启发来自于一个蚂蚁群体对食物源 的搜索，是一种杰出而具有代表性的群智能算法，对 于其算法描述可以参考相关文献［１⁃５］ 。 ＡＣＯ 算法有 一些不同的变体，为了分析的方便，在当前理论分析 方面，还是主要考虑一只蚂蚁的情况。 下面给出蚁 群优化算法理论研究中用到的一个简单的 ＡＣＯ 算 法 （ １ ＋ １ ） 蚂 蚁 算 法 （（ １ ＋ １ ） Ａｎｔ Ａｌｇｏｒｉｔｈｍ， （１＋１）ＡＡ）， 其 类 似 于 演 化 算 法 理 论 分 析 中 的 （１＋１） ＥＡ。 不 失 一 般 性， 考 虑 最 小 化 问 题。 （１＋１）ＡＡ算法描述如下 Ａｌｇｏｒｉｔｈｍ １： （１＋１）ＡＡ Ｂｅｇｉｎ 初始化：参数设置，信息素值，选择一个初始解 ｓ，Ｗｈｉｌｅ（不满足终止条件） 使用构造过程构建一个新的解 ｓ′； 选择：如果 ｆ（ｓ′）＜ｆ（ｓ），则 ｓ ＝ ｓ′；更新信息素值。 Ｅｎｄ ｗｈｉｌｅ Ｅｎｄ （１＋１）ＡＡ 算法使用简单的爬山选择策略，如果 当前蚂蚁解的函数值大于新的蚂蚁解的函数值，则 当前蚂蚁解被新蚂蚁解替代。 以下两节分别介绍理 论分析中蚁群算法解的构建以及信息素更新机制。 １．２ 解的构建 对于一个给定的优化问题，其解通过蚂蚁在一 个具有信息素值的构造图（ ｃｏｎｓｔｒｕｃｔｉｏｎ ｇｒａｐｈ）的边 上随机游走获得。 另外，蚁群算法也使用启发式信 息来指导随机游走的方向。 蚂蚁从构造图的任意一 个初始状态出发，随机游走到下一个邻域结点。 这 个移动是基于概率规则，依赖于信息素和启发式 信息。 令 Ｇ ＝ （Ｖ，Ｅ）为一给定问题的构造图。 τ（ｕ，ｖ） 为 边 ｅ ＝ （ ｕ，ｖ） ∈Ｅ 上的信息素值，η（ｕ，ｖ） 为启发式信 息。 假设蚂蚁当前所在位置为顶点 ｕ，其允许访问 的后续结点为 Ｎｕ 。 蚂蚁在下一步访问结点 ｖ∈Ｎｕ 的概率由以下公式给出： ｐｕｖ ＝ τ（ｕ，ｖ） ( ) α· η（ｕ，ｖ） ( ) β ω∑∈Ｎｕ τ（ｕ，ω） ( ) α· η（ｕ，ω） ( ) β 式中：参数 α 表示蚂蚁在运动过程中所积累的信息 素在指导蚂蚁搜索路径的相对重要性；参数 β 表示 路径能见度的相对重要性，即表示启发式信息 η（ｕ，ｖ） 的重要性。 第 １ 期 夏小云，等：蚁群优化算法的理论研究进展 ·２９·

·30。 智能系统学报 第11卷 1.3信息素更新机制 定义1（适应值划分）给定一个有限的搜索空 当算法完成一次迭代之后，路径上的信息素将 间S,不失一般性，假设函数f:S→R最小化，考虑函 会更新。信息素更新的目的是使得较优路径上的信 数f的所有可能的不同的函数值A。,A1,…,4m,对于 息素增加，同时模拟一种挥发的方式削弱较差路径 Ha∈A,和b∈A,如果f代a)<fb),则记为A,<Ao 上的信息素。通常根据挥发因子p(0≤p≤1)的不 若有A。<A<A:…<A,定义 同，信息素值会减少不同的数量。假设更新之前的 A:={x∈Slfx)=f},i=0,1,2,…,m。则称{Ao,A1, 边(u,)∈E上的信息素值为Ta,在第一步，其值 …,A}为基于适应值的划分。 减少到(1-p)T。这意味着，在算法的运行过程 对于AC0,算法每次接受优于当前最好的解， 中，路径上的信息素将会有一定程度的挥发，避免信 算法每次运行都朝着最优解的方向前进，如图1所 息素的无限积累，这样也有利于算法逃脱局部最优。 示。下面给出一个简单AC0算法的期望运行时间 各路径上的信息素根据以下方式进行更新： 估计的定理，其由Gutjahr和Sebastiani提出。 n-(1-p)To +Ar 以概率p转移 式中：△r,表示蚂蚁k在边(u,v)上释放的信息素 A 浓度，m为蚂蚁的数量。 4 根据信息素更新方式的不同，也就产生具有不 同信息素更新机制的蚁群算法)。为了防止算法 图1适应值划分 的早熟，Stutzle和Hoos[)提出了最大最小蚂蚁系 Fig.1 Fitness values partition 统。在信息素的更新过程中，将其限制在一个最大 定理2给定一个适应值划分{A。,A1,…,Am。 最小信息素范围内[T,T]。根据边 令X,(t=1,2,.)为AC0算法的解序列， e=(u,v)∈E是否包含在至今最好的解x中，其信息 P,(i=1,2,…,m)为算法运行所得适应值所在集合 素更新规则如下： 从A,跳转到A-1U…UA,的概率下界，并且集合Ao |min(1-p)rao+p,rs},if(u,）∈x 包含最优解。则ACO算法求解函数∫的期望时间 (nmax{(1-p)re,ran},其他 上界为：宫（化+），其中为算法每次迭代时信息 Pi (1) 称使用上述信息素更新规则的(1+1)AA算法 素达到饱和的时间，也就是信息素值达到r或Tm。 为(1+1)MMAA。类似的(1+1)MMAA在文献[28,34] 根据文献[34]知道≤”。因此，对于AC0 中分别叫做MMAS·和MMAS p 理论分析，最关键的是计算一步转移概率P:。一般 2 理论分析方法及数学工具 来说，由该方法获得的时间上界不是紧界。 2.2期望倍增距离减少 对于一个确定的优化问题，蚁群算法找到一个 函数适应值个数非常大（指数级）的情况，适应 最优解的迭代次数用随机变量t表示。在蚁群算法 值划分技术已经不再适用。期望倍增减少距离(x- 的理论分析中通常需要估计最好情况、平均情况、最 坏情况下，以什么样的概率P(t≤T)在什么样的期 pected multiplicative distance decrease)的方法正好能 够应对函数适应值数量非常大的情况，该方法如图 望运行时间E(t)内，找到什么样的解（近似解）。本 2所示。 节介绍一些蚁群算法的理论分析方法和基本的数学 工具。不失一般性，考虑最小化问题。 从搜索点s开始，经过个可 2.1适应值划分 接受的操作后到达搜索点S S 对于给定的优化问题，感兴趣的是算法找到最 Doh/≤d. 优解的平均迭代次数。这里介绍适应值划分技术， -)D (1-I)D 该技术在演化算法的理论分析中得到了成功运用。 其原理是种群中最好的个体适应值一直都确保不会 是过1步 经过步 变差。因此通过估计最好的个体适应值变好的期望 图2期望倍增距离减少 时间界来获得优化时间。这种方法称为基于适应度 Fig.2 Expected multiplicative distance decrease 划分的方法(fitness-based partitions)或者适应度等 给定一个具有操作序列0p={叩o,叩1，叩2，… 级方法[4。 叩，…}，每一操作发生的概率相同，假设为

１．３ 信息素更新机制 当算法完成一次迭代之后，路径上的信息素将 会更新。 信息素更新的目的是使得较优路径上的信 息素增加，同时模拟一种挥发的方式削弱较差路径 上的信息素。 通常根据挥发因子 ρ (０≤ρ≤１) 的不 同，信息素值会减少不同的数量。 假设更新之前的 边（ｕ，ｖ）∈Ｅ 上的信息素值为 τ（ｕ，ｖ） ，在第一步，其值 减少到（１－ρ） τ（ｕ，ｖ） 。 这意味着，在算法的运行过程 中，路径上的信息素将会有一定程度的挥发，避免信 息素的无限积累，这样也有利于算法逃脱局部最优。 各路径上的信息素根据以下方式进行更新： τ′（ｕ，ｖ） ＝ （１ － ρ）τ（ｕ，ｖ） ＋ ∑ ｍ ｋ ＝ １ Δτ ｋ （ｕ，ｖ） 式中：Δτ ｋ （ｕ，ｖ）表示蚂蚁 ｋ 在边（ｕ，ｖ）上释放的信息素 浓度， ｍ 为蚂蚁的数量。 根据信息素更新方式的不同，也就产生具有不 同信息素更新机制的蚁群算法［８］ 。 为了防止算法 的早熟， Ｓｔüｔｚｌｅ 和 Ｈｏｏｓ ［９］ 提出了最大最小蚂蚁系 统。 在信息素的更新过程中，将其限制在一个最大 最 小 信 息 素 范 围 内 ［ τｍｉｎ ， τｍａｘ ］。 根 据 边 ｅ ＝ （ｕ，ｖ）∈Ｅ是否包含在至今最好的解 ｘ 中，其信息 素更新规则如下： τ（ｕ，ｖ） ′ ＝ ｍｉｎ｛（１ － ρ）τ（ｕ，ｖ） ＋ ρ，τｍａｘ｝，ｉｆ （ｕ，ｖ） ∈ ｘ {ｍａｘ｛（１ － ρ）τ（ｕ，ｖ） ，τｍｉｎ｝，其他 ． （１） 称使用上述信息素更新规则的（１＋１）ＡＡ 算法 为（１＋１）ＭＭＡＡ。 类似的（１＋１）ＭＭＡＡ 在文献［２８，３４］ 中分别叫做 ＭＭＡＳ ∗和 ＭＭＡＳｂｓ。 ２ 理论分析方法及数学工具 对于一个确定的优化问题，蚁群算法找到一个 最优解的迭代次数用随机变量 ｔ 表示。 在蚁群算法 的理论分析中通常需要估计最好情况、平均情况、最 坏情况下，以什么样的概率 Ｐｒ（ｔ≤Ｔ）在什么样的期 望运行时间 Ｅ（ｔ）内，找到什么样的解（近似解）。 本 节介绍一些蚁群算法的理论分析方法和基本的数学 工具。 不失一般性，考虑最小化问题。 ２．１ 适应值划分 对于给定的优化问题，感兴趣的是算法找到最 优解的平均迭代次数。 这里介绍适应值划分技术， 该技术在演化算法的理论分析中得到了成功运用。 其原理是种群中最好的个体适应值一直都确保不会 变差。 因此通过估计最好的个体适应值变好的期望 时间界来获得优化时间。 这种方法称为基于适应度 划分的方法（ ｆｉｔｎｅｓｓ⁃ｂａｓｅｄ ｐａｒｔｉｔｉｏｎｓ） 或者适应度等 级方法［１４］ 。 定义 １ （适应值划分）给定一个有限的搜索空 间 Ｓ，不失一般性，假设函数 ｆ：Ｓ→Ｒ 最小化， 考虑函 数 ｆ 的所有可能的不同的函数值 Ａ０ ，Ａ１ ，…，Ａｍ ，对于 ∀ａ∈Ａｉ 和∀ｂ∈Ａｊ，如果 ｆ（ａ）＜ｆ（ｂ），则记为 Ａｉ ＜ｆＡｊ。 若 有 Ａ０ ＜ｆＡ１ ＜ｆＡ２ ＜ｆ … ＜ｆＡｍ ， 定 义 Ａｉ ＝ ｛ｘ∈Ｓ ｜ ｆ（ｘ）＝ ｆ ｉ｝，ｉ ＝ ０，１，２，…，ｍ。 则称｛Ａ０ ，Ａ１ ， …，Ａｍ ｝为基于适应值的划分。 对于 ＡＣＯ，算法每次接受优于当前最好的解， 算法每次运行都朝着最优解的方向前进，如图 １ 所 示。 下面给出一个简单 ＡＣＯ 算法的期望运行时间 估计的定理，其由 Ｇｕｔｊａｈｒ 和 Ｓｅｂａｓｔｉａｎｉ ［３４］提出。 图 １ 适应值划分 Ｆｉｇ．１ Ｆｉｔｎｅｓｓ ｖａｌｕｅｓ ｐａｒｔｉｔｉｏｎ 定理 ２ 给定一个适应值划分｛Ａ０，Ａ１，…，Ａｍ ｝。 令 Ｘｔ （ ｔ ＝ １， ２，．．．） 为 ＡＣＯ 算 法 的 解 序 列， ｐｉ（ｉ ＝ １，２，…，ｍ）为算法运行所得适应值所在集合 从 Ａｉ 跳转到 Ａｉ－１∪…∪Ａ０ 的概率下界，并且集合 Ａ０ 包含最优解。 则 ＡＣＯ 算法求解函数 ｆ 的期望时间 上界为：∑ ｍ ｉ ＝ １ （ｔ ∗ ｉ ＋ １ ｐｉ ），其中 ｔ ∗ ｉ 为算法每次迭代时信息 素达到饱和的时间，也就是信息素值达到 τｍａｘ或 τｍｉｎ 。 根据文献［３４］知道 ｔ ∗ ｉ ≤ ｌｎｎ ρ 。 因此，对于 ＡＣＯ 理论分析，最关键的是计算一步转移概率 ｐｉ。 一般 来说，由该方法获得的时间上界不是紧界。 ２．２ 期望倍增距离减少 函数适应值个数非常大（指数级）的情况，适应 值划分技术已经不再适用。 期望倍增减少距离（ｅｘ⁃ ｐｅｃｔｅｄ ｍｕｌｔｉｐｌｉｃａｔｉｖｅ ｄｉｓｔａｎｃｅ ｄｅｃｒｅａｓｅ）的方法正好能 够应对函数适应值数量非常大的情况，该方法如图 ２ 所示。 图 ２ 期望倍增距离减少 Ｆｉｇ．２ Ｅｘｐｅｃｔｅｄ ｍｕｌｔｉｐｌｉｃａｔｉｖｅ ｄｉｓｔａｎｃｅ ｄｅｃｒｅａｓｅ 给定一个具有操作序列 Ｏｐ ＝ ｛ ｏｐ０ ，ｏｐ１ ，ｏｐ２ ，…， ｏｐｔ， …｝， 每 一 操 作 发 生 的 概 率 相 同， 假 设 为 ·３０· 智 能 系 统 学 报 第 １１ 卷

第1期 夏小云，等：蚁群优化算法的理论研究进展 ·31· P(吧，)=Pm≥α(t=1,2,….)。给定任意初始解s, 之后与目标最优解距离小于1的概率至少为1/2。 算法通过执行操作叩，∈Op,一步一步逐渐到达最优 假设函数适应值均为正整数，则算法获得最优解 解5。不失一般性，考虑最小化问题。定义优化问 (离目标最优解距离为0)的概率至少为1/2。因 题的适应值函数f(s,)(t=1,2,…),d(s,）=f八s)- 此，算法最终到达目标找到最优解的期望时间上界 f(sp)为第1代时的解s,与目标最优解sm相差的适 为2T=0(r·logD)。 应值距离。根据随机启发式算法的特点，给定不同 2.3尾概率不等式 的初始解，其求解问题的迭代次数也不一样，因此考 偏差不等式广泛应用于随机算法的分析中。在 虑的是期望迭代次数。算法找到可接受的操作，使 许多启发式搜索算法的例子中，对于分析启发式的 得s1优于s,。假定算法通过执行给定的操作使得 典型行为是非常有用的。其通常用于估计随机变量 减少的期望距离至少为 偏离期望值的概率。 d()-d(s)≥s）-fs) 2.3.1 Markov不等式 (2) 马尔可夫不等式(Markov's inequality)适用于 由(2)得 非负随机变量。对一非负的随机变量X:2→R,对 d(s)≤(1-)fs,)-fsm)） (3) 于t∈R,有P(X)sE( 当前解离目标最优解距离减少由两部分产生： 2.3.2 Chebyshev不等式 可接受的操作和不接受的操作，而不接受的操作距 切比雪夫不等式(Chebyshev's inequality)适用 离减少的贡献为0。 于任何的（可正可负）随机变量，有两种形式： 因此，如果d(s,)>0,有 1)令X为一随机变量，其中E(X)=, E[d(s)I d(s,)]=pd(s)+(1-p)d(s,) Var(X)=σ2。对于k>0, p.(1-)-》+ P(IX-l>k)=P(X)E(IX)_o (1-Pm)(f八s,)-f(s))= 2)X.~iid(independent and identically distrib- (1-P)ds,) uted),独立同分布，期望E(X)=u且Var(X)=σ2， (4) X为u的估计，则 令Y,=d(s,),有 E[Y,Iopo,0p1,…,叩-1]≤ P(Ii-u≥k)≤Var(- k2n·k2 （1-）[19,m,m1≤ 2.3.3 Chernoff界 切尔诺夫界(Chernoff bounds):X:∈{0，l}(1≤ (1-P)2E[Y,-i1opo,0p1,…,0p-3] i≤)为独立泊松分布事件，令X=三 …≤ (1-P=)'E[Y]= P(X=1)=n,u=E(X)=2P,00，P[X≥(1+8)]≤ (1-P=)'Efs)-f50)]△1 (1+8)1+6) ;对于0<8<1，P[X≤(1-6)u]≤ 考虑搜索空间中离最优搜索点s距离最远的情 e 况。如图2所示，令该最远距离D=f(s)-f(s)≤ (1-6)(1- :对于0<xl,P[X≥(1+δ)u]≤e号： dx,则有1≤(1-&)D,a为常数，且0<a<1。 对于0<8<1，P[X≤(1-6)u]≤e号：对于0<8<1， 令T=0(r·logD),当t≥T,有E[Y,Ipo,p1, P(1K-u)≥]≤2e号。 ,9m-]≤(1-号)D≤分。根据Mkom不等式算 3一些理论研究结果及问题讨论 法执行T步之后，离最优解距离至少为1的概率P 3.1参数p、a、B对算法性能影响 (≥)≤，因此P(y<)≥7。也就是说T步 到目前为止，蚁群算法中挥发因子、信息素值控 制参数、启发式信息（能见度）控制参数的设置，对

Ｐ（ｏｐｔ）＝ ｐｍ≥α（ ｔ ＝ １，２，…．）。 给定任意初始解 ｓ， 算法通过执行操作 ｏｐｔ∈Ｏｐ，一步一步逐渐到达最优 解 ｓｏｐｔ。 不失一般性，考虑最小化问题。 定义优化问 题的适应值函数 ｆ（ ｓｔ ） （ ｔ ＝ １，２，．．．），ｄ（ ｓｔ ） ＝ ｆ（ｓｔ）－ ｆ（ｓｏｐｔ）为第 ｔ 代时的解 ｓｔ 与目标最优解 ｓｏｐｔ相差的适 应值距离。 根据随机启发式算法的特点，给定不同 的初始解，其求解问题的迭代次数也不一样，因此考 虑的是期望迭代次数。 算法找到可接受的操作，使 得 ｓｔ＋１优于 ｓｔ。 假定算法通过执行给定的操作使得 减少的期望距离至少为 ｄ（ｓｔ） － ｄ（ｓｔ＋１ ） ≥ ｆ（ｓｔ） － ｆ（ｓｏｐｔ） ｒ （２） 由（２）得 ｄ（ｓｔ＋１ ） ≤ （１ － １ ｒ ）（ｆ（ｓｔ） － ｆ（ｓｏｐｔ）） （３） 当前解离目标最优解距离减少由两部分产生： 可接受的操作和不接受的操作，而不接受的操作距 离减少的贡献为 ０。 因此，如果 ｄ（ｓｔ）＞０，有 Ｅ［ｄ（ｓｔ＋１ ） ｜ ｄ（ｓｔ）］ ＝ ｐｍ ｄ（ｓｔ＋１ ） ＋ （１ － ｐｍ ）ｄ（ｓｔ） ≤ ｐｍ（１ － １ ｒ ）（ｆ（ｓｔ） － ｆ（ｓｏｐｔ）） ＋ （１ － ｐｍ ）（ｆ（ｓｔ） － ｆ（ｓｏｐｔ）） ＝ （１ － ｐｍ ｒ ）ｄ（ｓｔ） （４） 令 Ｙｔ ＝ ｄ（ｓｔ），有 Ｅ［Ｙｔ ｜ ｏｐ０ ，ｏｐ１ ，…，ｏｐｔ－１ ］ ≤ （１ － ｐｍ ｒ ）Ｅ［Ｙｔ－１ ｜ ｏｐ０ ，ｏｐ１ ，…，ｏｐｔ－２ ］ ≤ （１ － ｐｍ ｒ ） ２Ｅ［Ｙｔ－１ ｜ ｏｐ０ ，ｏｐ１ ，…，ｏｐｔ－３ ］ … ≤ （１ － ｐｍ ｒ ） ｔＥ［Ｙ０ ］ ＝ （１ － ｐｍ ｒ ） ｔＥ［ｆ（ｓ） － ｆ（ｓｏｐｔ）］ 􀰛 Ｉ 考虑搜索空间中离最优搜索点 ｓｏｐｔ距离最远的情 况。 如图 ２ 所示，令该最远距离 Ｄ ＝ ｆ（ｓ） －ｆ（ｓｏｐｔ ）≤ ｄｍａｘ，则有 Ｉ≤（１－ α ｒ ） ｔＤ，α 为常数，且０＜α＜１。 令 Ｔ ＝Ｏ（ｒ·ｌｏｇＤ），当 ｔ≥Ｔ，有 Ｅ［ Ｙｔ ｜ ｏｐ０ ，ｏｐ１ ， …，ｏｐｔ－１ ］≤（１－ α ｒ ） ｔＤ≤ １ ２ 。 根据 Ｍａｒｋｏｖ 不等式，算 法执行 Ｔ 步之后，离最优解距离至少为 １ 的概率 Ｐ （Ｙｔ≥１）≤ １ ２ ，因此 Ｐ（Ｙｔ ＜１）≥ １ ２ 。 也就是说 Ｔ 步 之后与目标最优解距离小于 １ 的概率至少为 １ ／ ２。 假设函数适应值均为正整数，则算法获得最优解 （离目标最优解距离为 ０） 的概率至少为 １ ／ ２。 因 此，算法最终到达目标找到最优解的期望时间上界 为２Ｔ ＝Ｏ（ｒ·ｌｏｇＤ）。 ２．３ 尾概率不等式 偏差不等式广泛应用于随机算法的分析中。 在 许多启发式搜索算法的例子中，对于分析启发式的 典型行为是非常有用的。 其通常用于估计随机变量 偏离期望值的概率。 ２．３．１ Ｍａｒｋｏｖ 不等式 马尔可夫不等式（Ｍａｒｋｏｖ’ ｓ ｉｎｅｑｕａｌｉｔｙ） 适用于 非负随机变量。 对一非负的随机变量 Ｘ：Ω→Ｒ ＋ ，对 于 ｔ∈Ｒ ＋ ，有 Ｐ（Ｘ＞ｔ）≤ Ｅ（Ｘ） ｔ 。 ２．３．２ Ｃｈｅｂｙｓｈｅｖ 不等式 切比雪夫不等式 （Ｃｈｅｂｙｓｈｅｖ􀆳ｓ ｉｎｅｑｕａｌｉｔｙ） 适用 于任何的（可正可负）随机变量，有两种形式： １） 令 Ｘ 为 一 随 机 变 量， 其 中 Ｅ （ Ｘ ） ＝ μ， Ｖａｒ（Ｘ）＝ σ ２ 。 对于 ｋ＞０， Ｐ（ ｜Ｘ－μ｜ ＞ｋ）＝ Ｐ（ ｜Ｘ－μ｜ ２ ＞ｋ ２ ）≤ Ｅ（ ｜Ｘ－μ｜ ２ ） ｋ ２ ＝ σ ２ ｋ ２ 。 ２）令 Ｘｉ ～ ｉｉｄ（ｉｎｄｅｐｅｎｄｅｎｔ ａｎｄ ｉｄｅｎｔｉｃａｌｌｙ ｄｉｓｔｒｉｂ⁃ ｕｔｅｄ），独立同分布，期望 Ｅ（Ｘｉ）＝ μ 且 Ｖａｒ（Ｘｉ）＝ σ ２ ， Ｘ － 为 μ 的估计，则 Ｐ（ Ｘ － － μ ≥ ｋ） ≤ Ｖａｒ（Ｘ － ） ｋ ２ ＝ σ ２ ｎ·ｋ ２ 。 ２．３．３ Ｃｈｅｒｎｏｆｆ 界 切尔诺夫界（Ｃｈｅｒｎｏｆｆ ｂｏｕｎｄｓ）： Ｘｉ ∈ ｛０，１｝（１ ≤ ｉ ≤ ｎ） 为 独 立 泊 松 分 布 事 件， 令 Ｘ ＝ ∑ ｎ ｉ ＝ １ Ｘｉ， Ｐ（Ｘｉ ＝ １） ＝ ｐｉ， μ ＝ Ｅ（Ｘ） ＝ ∑ ｎ ｉ ＝ １ ｐｉ，０ ＜ ｐｉ ＜ １。 则 对 于 δ ＞ ０，Ｐ［Ｘ ≥ （１ ＋ δ）μ］ ≤ ｅ δ （１ ＋ δ） （１＋δ） æ è ç ö ø ÷ μ ； 对于 ０ ＜δ ＜ １，Ｐ［Ｘ≤（１ －δ） μ］ ≤ ｅ －δ （１－δ） （１－δ） æ è ç ö ø ÷ μ ；对于 ０＜δ＜１，Ｐ［Ｘ≥（１＋δ）μ］≤ｅ － μδ ２ ３ ； 对于 ０＜δ＜１，Ｐ［Ｘ≤（１－δ） μ］ ≤ｅ － μδ ２ ２ ；对于 ０＜δ＜１， Ｐ（ Ｘ－μ ）≥δμ］≤２ｅ － ｕδ ２ ３ 。 ３ 一些理论研究结果及问题讨论 ３．１ 参数 ρ、α、β 对算法性能影响 到目前为止，蚁群算法中挥发因子、信息素值控 制参数、启发式信息（能见度）控制参数的设置，对 第 １ 期 夏小云，等：蚁群优化算法的理论研究进展 ·３１·

·32 智能系统学报 第11卷 于界定蚁群算法的难问题和易问题并没有从理论上 3.2从1-ANT到n-ANT 真正得以解释说明。从蚁群算法求解一些实际问题 当前对于蚁群优化算法的理论研究，研究人员 的实验效果来看，信息素挥发因子是一个比较关键 主要还是考虑一只蚂蚁的情况。不同的文献采用的 的参数。挥发因子越大，表现出的正反馈作用越强， 算法框架名称不同，主要有1-ANT9,12)、(1+1) 以往走过的路径被再次选择的可能性就越大，搜索 MMAA4S),MMAS·[2]、MMAS[B以及MMASo和 随机性变弱：相反，挥发因子越小，算法的随机性就 MMAS【等。这些算法在每次迭代之后只构造一 越大，其全局搜索能力也就变强。信息素挥发因子 个解，是一种比较简单的情况。 设置对于算法性能影响至关重要。 Neumann等人[6]研究了A-MMAS.算法求解拟 Neumann[27,29]等研究了信息素挥发因子p对蚁 布尔函数的性能。他们指出，当A=2,也即构造2 群算法性能的影响，指出如果p≥”- n-2 即当n→o, 个蚂蚁解时，该算法在挥发因子足够小的情况下，能 够在多项式时间内求解OneMax函数。 p≥1/3时，算法1-ANT的行为类似于(1+1)EA,就 Attiratanasunthron和Fakcharoenphol4]研究了 是说，1-ANT在每个函数上的期望运行时间和(1+ ACO算法求解有向无环图单源最短路径问题的多 1)EA相同。同时指出，如果取p=O(ne),e>0为 项式时间界。特别地，对于顶点数为n,边数为m的 常数，则算法1-ANT以1-2-a)的概率求解0me 有向无环图，具有n只蚂蚁的n-ANT算法能够在期 Max函数的时间为2a):如果取p=2(n1+“),e>0 望时间O(n2 nlogn./p)内求解单源最短路径问题。 为常数，则算法1-ANT以1-2)的概率求解 蚂蚁的数量决定了每次迭代构造的解的个数。 OneMax函数的时间为O(n2),给出了1-ANT算法求 在不同参数情况下，真实的多蚂蚁蚁群系统如何影 解OneMax函数的时间复杂度从指数时间到多项式 响算法性能，如何设置蚂蚁个数，以及-ANT算法 时间的相变现象。Doer等[]使用一个信息素模型 求解组合优化问题的性能，能够在什么样的时间内 简化了文献[29]的分析，进一步研究了挥发因子p 获得什么样的解，是值得进一步研究的问题。 ∈[1/n+“,1/n-]的优化时间。并指出，存在常数c3.3从拟布尔函数到NP难问题 ∈(0,1)和N∈N,使得当n≥N和p≤c,对于n个变 3.3.1拟布尔函数 元的OneMax函数，算法1-ANT以小于1/eP的概率 以下7个函数为分析演化和蚁群算法时间复杂 性的典型人工拟布尔函数： 优化时间最多为eP。Doer等2]研究了挥发因子 p对于I-ANT算法的性能影响，指出对于Leadin- 10 neMax(x)=含： gOnes和BinVal两个函数，存在一个相变现象，且阈 值为p~l/(nlog),其期望时间为指数级到多项式。 2)Leading0nes(x)=含： 蚁群算法中信息素控制参数α反映蚂蚁在行 3)Trap(x)= 含+(n+1)·(1-x): 走过程中所积累的信息素对指导蚂蚁搜索方向的相 对重要性，能见度控制参数B反映启发式信息对指 4)BinVal(x)=含2产： 导蚂蚁搜索方向的相对重要性。Zhou4s]通过构造 5)Needle( TSP实例，研究了参数a和B对算法计算时间的影 响，指出对于完全图实例，参数设置α=1，B=0到 6)NH-OneMax(x)=(,)() a=1,B=1,其期望运行时间上界也由0(n)变为 7)F(x)=召wo 0(n')。Kotzing等6通过构建一个TSP实例分析 从2006年开始，蚁群算法关于时间复杂性分析 了启发式信息对于蚁群算法的性能影响，指出对于 的理论研究也相继出现，Neumann7,等通过模拟 该实例取α=1，如果B=1,算法需要指数级运行时 (1+1)EA建立了一个简单的AC0算法1-ANT分析 间找到最优解：如果B=n,则算法以趋近于1的概率 模型，给出了1-ANT求解简单拟布尔函数OneMax 在一次迭代就能找到最优解。 平均时间复杂度为O(nlogn),并且指出挥发因子对 蚁群算法参数较多，设置也较复杂。目前理论 时间复杂度起着关键性的影响。与此同时，Gt- 分析主要通过一些构造实例来分析不同参数设置对 jahrt30]采用近似的常微分方程组估计算法时间复杂 于算法性能的影响。针对一般性的问题，参数如何 度，研究了GBAS和AS两个AC0算法的同一分析。 设置对于蚁群算法来说是有效的，还有待于进一步 Doer等[3]以I-ANT求解关于OneMax为例，分析 深入探究。 了随着挥发系数的变化，1-ANT算法时间复杂度从

于界定蚁群算法的难问题和易问题并没有从理论上 真正得以解释说明。 从蚁群算法求解一些实际问题 的实验效果来看，信息素挥发因子是一个比较关键 的参数。 挥发因子越大，表现出的正反馈作用越强， 以往走过的路径被再次选择的可能性就越大，搜索 随机性变弱；相反，挥发因子越小，算法的随机性就 越大，其全局搜索能力也就变强。 信息素挥发因子 设置对于算法性能影响至关重要。 Ｎｅｕｍａｎｎ ［２７，２９］等研究了信息素挥发因子 ρ 对蚁 群算法性能的影响，指出如果 ρ≥ ｎ－２ ３ｎ－２ ，即当ｎ→¥， ρ≥１ ／ ３ 时，算法 １⁃ＡＮＴ 的行为类似于（１＋１）ＥＡ，就 是说，１⁃ＡＮＴ 在每个函数上的期望运行时间和（１＋ １）ＥＡ 相同。 同时指出，如果取 ρ ＝Ｏ（ｎ －１－ε ），ε＞０ 为 常数，则算法 １⁃ＡＮＴ 以 １－２ －Ω（ｎ ε／ ３） 的概率求解 Ｏｎｅ⁃ Ｍａｘ 函数的时间为 ２ Ω（ｎ ε／ ３） ；如果取 ρ ＝Ω（ｎ －１＋ε ），ε＞０ 为常数，则算法 １⁃ＡＮＴ 以 １ － ２ －Ω（ｎ ε／ ２） 的概率求解 ＯｎｅＭａｘ 函数的时间为Ｏ（ｎ ２ ），给出了 １⁃ＡＮＴ 算法求 解 ＯｎｅＭａｘ 函数的时间复杂度从指数时间到多项式 时间的相变现象。 Ｄｏｅｒｒ 等［３１］使用一个信息素模型 简化了文献［２９］的分析，进一步研究了挥发因子 ρ ∈［１ ／ ｎ １＋ε ，１ ／ ｎ １－ε ］的优化时间。 并指出，存在常数 ｃ ∈（０，１）和Ｎ∈Ｎ，使得当 ｎ≥Ｎ 和 ρ≤ｃ，对于 ｎ 个变 元的 ＯｎｅＭａｘ 函数，算法 １⁃ＡＮＴ 以小于 １ ／ ｅ ｃ ρ 的概率 优化时间最多为 ｅ ｃ ρ 。 Ｄｏｅｒｒ 等［３２⁃３３］研究了挥发因子 ρ 对于 １⁃ＡＮＴ 算法的性能影响，指出对于 Ｌｅａｄｉｎ⁃ ｇＯｎｅｓ 和 ＢｉｎＶａｌ 两个函数，存在一个相变现象，且阈 值为 ρ～１ ／ （ｎｌｏｇｎ），其期望时间为指数级到多项式。 蚁群算法中信息素控制参数 α 反映蚂蚁在行 走过程中所积累的信息素对指导蚂蚁搜索方向的相 对重要性，能见度控制参数 β 反映启发式信息对指 导蚂蚁搜索方向的相对重要性。 Ｚｈｏｕ ［４５］ 通过构造 ＴＳＰ 实例，研究了参数 α 和 β 对算法计算时间的影 响，指出对于完全图实例，参数设置 α ＝ １，β ＝ ０ 到 α＝ １，β ＝ １，其期望运行时间上界也由 Ｏ（ ｎ ６ ） 变为 Ｏ（ｎ ５ ）。 Ｋöｔｚｉｎｇ 等［４６］通过构建一个 ＴＳＰ 实例分析 了启发式信息对于蚁群算法的性能影响，指出对于 该实例取 α＝ １，如果 β ＝ １，算法需要指数级运行时 间找到最优解；如果 β ＝ ｎ，则算法以趋近于 １ 的概率 在一次迭代就能找到最优解。 蚁群算法参数较多，设置也较复杂。 目前理论 分析主要通过一些构造实例来分析不同参数设置对 于算法性能的影响。 针对一般性的问题，参数如何 设置对于蚁群算法来说是有效的，还有待于进一步 深入探究。 ３．２ 从 １⁃ＡＮＴ 到 ｎ⁃ＡＮＴ 当前对于蚁群优化算法的理论研究， 研究人员 主要还是考虑一只蚂蚁的情况。 不同的文献采用的 算法框架名称不同，主要有 １⁃ＡＮＴ ［２９，３１⁃３２］ 、 （ １ ＋ １） ＭＭＡＡ ［４５］ 、ＭＭＡＳ ∗ ［２８］ 、ＭＭＡＳｂｓ ［３４］ 以及 ＭＭＡＳ ∗ Ｏｒｄ 和 ＭＭＡＳ ∗ Ａｒｂ ［４６］等。 这些算法在每次迭代之后只构造一 个解，是一种比较简单的情况。 Ｎｅｕｍａｎｎ 等人［３６］研究了 λ⁃ＭＭＡＳＩＢ算法求解拟 布尔函数的性能。 他们指出，当 λ ＝ ２，也即构造 ２ 个蚂蚁解时，该算法在挥发因子足够小的情况下，能 够在多项式时间内求解 ＯｎｅＭａｘ 函数。 Ａｔｔｉｒａｔａｎａｓｕｎｔｈｒｏｎ 和 Ｆａｋｃｈａｒｏｅｎｐｈｏｌ ［４１］ 研究了 ＡＣＯ 算法求解有向无环图单源最短路径问题的多 项式时间界。 特别地，对于顶点数为 ｎ，边数为 ｍ 的 有向无环图，具有 ｎ 只蚂蚁的 ｎ⁃ＡＮＴ 算法能够在期 望时间 Ο（ｎ ２ｍｌｏｇｎ ／ ρ）内求解单源最短路径问题。 蚂蚁的数量决定了每次迭代构造的解的个数。 在不同参数情况下，真实的多蚂蚁蚁群系统如何影 响算法性能，如何设置蚂蚁个数，以及 ｎ⁃ＡＮＴ 算法 求解组合优化问题的性能，能够在什么样的时间内 获得什么样的解，是值得进一步研究的问题。 ３．３ 从拟布尔函数到 ＮＰ 难问题 ３．３．１ 拟布尔函数 以下 ７ 个函数为分析演化和蚁群算法时间复杂 性的典型人工拟布尔函数： １）ＯｎｅＭａｘ（ｘ）＝ ∑ ｎ ｉ ＝ １ ｘｉ； ２）ＬｅａｄｉｎｇＯｎｅｓ（ｘ）＝ ∑ ｎ ｉ ＝ １ ∏ ｉ ｊ ＝ １ ｘｊ； ３）Ｔｒａｐ（ｘ）＝ ∑ ｎ ｉ ＝ １ ｘｉ ＋（ｎ＋１）·∏ ｎ ｉ ＝ １ （１－ｘｉ）； ４）ＢｉｎＶａｌ（ｘ）＝ ∑ ｎ ｉ ＝ １ ２ ｎ－ｉ ｘｉ； ５）Ｎｅｅｄｌｅ（ｘ）＝ ∏ ｎ ｉ ＝ １ ｘｉ； ６）ＮＨ⁃ＯｎｅＭａｘ（ｘ）＝ ∏ ｋ ｉ ＝ １ ｘｉ ( ) ∑ ｎ ｉ ＝ｋ＋１ ｘｉ ( ) ； ７） Ｆ（ｘ）＝ ∑ ｎ ｉ ＝ １ ｗｉ ｘｉ。 从 ２００６ 年开始，蚁群算法关于时间复杂性分析 的理论研究也相继出现， Ｎｅｕｍａｎｎ ［２７，２９］ 等通过模拟 （１＋１）ＥＡ 建立了一个简单的 ＡＣＯ 算法 １⁃ＡＮＴ 分析 模型，给出了 １⁃ＡＮＴ 求解简单拟布尔函数 ＯｎｅＭａｘ 平均时间复杂度为 Ｏ（ｎｌｏｇｎ），并且指出挥发因子对 时间复杂度起着关键性的影响。 与此同时，Ｇｕｔ⁃ ｊａｈｒ ［３０］采用近似的常微分方程组估计算法时间复杂 度，研究了 ＧＢＡＳ 和 ＡＳ 两个 ＡＣＯ 算法的同一分析。 Ｄｏｅｒｒ 等［３１］ 以 １⁃ＡＮＴ 求解关于 ＯｎｅＭａｘ 为例，分析 了随着挥发系数的变化，１⁃ＡＮＴ 算法时间复杂度从 ·３２· 智 能 系 统 学 报 第 １１ 卷

第1期 夏小云，等：蚁群优化算法的理论研究进展 ·33 指数时间到多项式时间的相位转移。Doer等[2] 顶点数，m为边数)。Neumann和Witt[9]分析了 研究了1-ANT算法信息素更新机制对时间复杂度 ACO算法求解最小生成树问题的时间复杂度，其蚂 的影响，指出如果挥发因子设置过小，算法很容易陷 蚁解的构建是基于两种不同的构造图，Broder-based 入停滞状态。对于拟布尔函数LeadingOnes和Bin- 和Kruskal-based,并证明了最大最小蚂蚁系统求解 Vl,找到最优解的期望时间也是指数级的。相反， 最小生成树问题的期望时间上界为O(mnlogn)。 如果参数设置合理，期望时间也从指数级降低到多 最小割(minimum cut)问题是图论中经典的组 项式时间。 合优化问题，其存在一些多项式求解算法。跟最小 学者们也研究了最大最小蚂蚁系统(max-min 割相关的问题如最小k-割和multiway割等问题都是 ant system,MMAS)[9算法的性能。该算法是蚁群 NP难问题[6)。Kotzing等[o分析了AC0算法在求 优化的一个变体，其使用Best-So-Far更新机制。对 解经典的最小割问题的时间复杂度，并研究了参数 于一些优化问题，最大最小蚂蚁系统能够有效地避 设置对于不同实例的运行时行为的影响。若参数α 免停滞，并能获得一个更有效的运行时间界。Gu =0,B=1,对于任意给定的带权图，算法MMAS·找 jahr和Sebastiani3]分析了MMAS在求解Needle-in- 到一个最小割的期望时间上界为O(n2):若参数 a-Haystack和LeadingOnes两个拟布尔函数的时间 =1,B=1,则算法的优化时间为 复杂度，并基于演化算法中适应值划分技术的基础 (n-2+2cn)！ ,其中cn=h/l,h和l为最大、最 上提出了一种ACO的时间复杂度理论分析框架，将 (n-2)！(2c.) 作为一般分析的一个非常有用的工具。2007年， 小蚂蚁算法的信息素边界值：若cn=k为常数，则期 Neumann等[3]将ACO算法扩展到单峰函数和高原 望时间变为O(n)。 函数的期望运行时分析上，并使用非齐次过程估计 最短路径问题的目标是搜索图中两结点之间的 了信息素边界的首达时间，进一步研究了1-ANT算 最短路径。D冰sra算法是求解该问题的典型路由 法关于LeadingOnes,Needle等其他拟布尔函数的时 算法，用于计算一个节点到其他所有节点的最短路 间复杂度；Kotzing等)也进一步研究了两种MMAs 径。文献[41-43]研究了最短路径问题，并分别分析 算法求解线性拟布尔函数的时间复杂度，并给出了 了AC0算法求解无环、有环、带有噪声情况下最短 求解所有线性函数的一般时间上界O(nlogn/,p)。 路径问题的计算时间。Attiratanasunthron和Fakcha- Neumann、Sudholt和Wit8]研究了ACO与局部搜 roenphol研究了AC0算法求解有向无环图单目标 索混合算法的影响，他指出对于一些人工构造的函 最短路径问题(single destination shortest path,SD- 数，ACO算法结合局部搜索能够以较高的概率将指 SP)的多项式时间界。对于顶点数为n边数为m的 数时间转为多项式时间。对于另外一些函数，情况 有向无环图，具有n只蚂蚁的n-ANT算法能够在期 则相反。 望时间O(n'mlog n/p)内求解单源最短路径问题。 以上所有研究分析使用的方法和工具为组合优 在此基础上，Horoba和Sudholt4将结果扩充 化问题的更深层次的分析奠定了坚实的基础。 到最大最小蚂蚁系统(MMAS),得到MMASSDSP关于 3.3.2P问题 单目标最短路径(SDSP)问题和MMASAPSP关于全部 一些确定性的算法能够在多项式时间内求解P 顶点对的最短路径问题(all-pairs shortest path,AP- 类的组合优化问题，实验表明AC0算法进行求解也 SP)的计算时间上界分别为O(lm+n/p)和 显示出了其优越性。ACO算法在一些简单函数上的 O(nlog n+log llog(△l)/p),后者为目前元启发式算 分析所使用的方法和工具，也进一步推广到实际的 法(meta-heuristic)关于APSP问题最好的界。进一 组合优化问题上的分析中。目前ACO算法针对多 步，Sudholt和Thyssen(讨论了边权数带噪声随机 项式可求解问题的理论分析也获得了一些结果。我 最短路径问题，给出了噪声强度、近似保证以及平均 们并不期望蚁群优化算法在这些优化问题上能够优 时间复杂度之间的权衡关系。 于那些最好的算法，而关键是对于其理论分析能够 最近，Lissovoi和Witt4]研究了入只蚂蚁的最 更深入地了解蚁群算法工作机制，更好指导算法的 大最小蚂蚁系统A-MMAS算法在动态SDSP问题上 设计及应用。 的时间复杂度。他们指出每个顶点上放一定数量的 最小生成树(minimum spanning trees)问题是数 蚂蚁甚至是常数只蚂蚁就能有效地求解动态SDSP 据结构与算法设计中一个经典的图论问题。两个著 问题，给出了蚂蚁数量、挥发因子及计算时间之间的 名的确定性算法Kruskal和Pim分别有最坏情况下 关系。此外，他们还研究了MMAS算法在动态 的时间复杂度O((m+n)logn)和O(nlogn+m)(n为 MAZE函数上的性能[47]

指数时间到多项式时间的相位转移。 Ｄｏｅｒｒ 等［３２⁃３３］ 研究了 １⁃ＡＮＴ 算法信息素更新机制对时间复杂度 的影响，指出如果挥发因子设置过小，算法很容易陷 入停滞状态。 对于拟布尔函数 ＬｅａｄｉｎｇＯｎｅｓ 和 Ｂｉｎ⁃ Ｖａｌ，找到最优解的期望时间也是指数级的。 相反， 如果参数设置合理，期望时间也从指数级降低到多 项式时间。 学者们也研究了最大最小蚂蚁系统（ ｍａｘ⁃ｍｉｎ ａｎｔ ｓｙｓｔｅｍ ，ＭＭＡＳ） ［９］ 算法的性能。 该算法是蚁群 优化的一个变体，其使用 Ｂｅｓｔ⁃Ｓｏ⁃Ｆａｒ 更新机制。 对 于一些优化问题，最大最小蚂蚁系统能够有效地避 免停滞，并能获得一个更有效的运行时间界。 Ｇｕｔ⁃ ｊａｈｒ 和 Ｓｅｂａｓｔｉａｎｉ ［３４］分析了 ＭＭＡＳ 在求解 Ｎｅｅｄｌｅ⁃ｉｎ⁃ ａ⁃Ｈａｙｓｔａｃｋ 和 ＬｅａｄｉｎｇＯｎｅｓ 两个拟布尔函数的时间 复杂度，并基于演化算法中适应值划分技术的基础 上提出了一种 ＡＣＯ 的时间复杂度理论分析框架，将 作为一般分析的一个非常有用的工具。 ２００７ 年， Ｎｅｕｍａｎｎ 等［３５］将 ＡＣＯ 算法扩展到单峰函数和高原 函数的期望运行时分析上，并使用非齐次过程估计 了信息素边界的首达时间，进一步研究了 １⁃ＡＮＴ 算 法关于 ＬｅａｄｉｎｇＯｎｅｓ、Ｎｅｅｄｌｅ 等其他拟布尔函数的时 间复杂度；Ｋöｔｚｉｎｇ 等［３７］也进一步研究了两种 ＭＭＡＳ 算法求解线性拟布尔函数的时间复杂度，并给出了 求解所有线性函数的一般时间上界Ο（ｎ ３ ｌｏｇｎ ／ ρ）。 Ｎｅｕｍａｎｎ、Ｓｕｄｈｏｌｔ 和 Ｗｉｔｔ ［３８］ 研究了 ＡＣＯ 与局部搜 索混合算法的影响，他指出对于一些人工构造的函 数，ＡＣＯ 算法结合局部搜索能够以较高的概率将指 数时间转为多项式时间。 对于另外一些函数，情况 则相反。 以上所有研究分析使用的方法和工具为组合优 化问题的更深层次的分析奠定了坚实的基础。 ３．３．２ Ｐ 问题 一些确定性的算法能够在多项式时间内求解 Ｐ 类的组合优化问题，实验表明 ＡＣＯ 算法进行求解也 显示出了其优越性。 ＡＣＯ 算法在一些简单函数上的 分析所使用的方法和工具，也进一步推广到实际的 组合优化问题上的分析中。 目前 ＡＣＯ 算法针对多 项式可求解问题的理论分析也获得了一些结果。 我 们并不期望蚁群优化算法在这些优化问题上能够优 于那些最好的算法，而关键是对于其理论分析能够 更深入地了解蚁群算法工作机制，更好指导算法的 设计及应用。 最小生成树（ｍｉｎｉｍｕｍ ｓｐａｎｎｉｎｇ ｔｒｅｅｓ）问题是数 据结构与算法设计中一个经典的图论问题。 两个著 名的确定性算法 Ｋｒｕｓｋａｌ 和 Ｐｒｉｍ 分别有最坏情况下 的时间复杂度Ο（（ｍ＋ｎ）ｌｏｇｎ）和 Ο（ｎｌｏｇｎ＋ｍ） （ｎ 为 顶点数， ｍ 为边数）。 Ｎｅｕｍａｎｎ 和 Ｗｉｔｔ ［３９］ 分析了 ＡＣＯ 算法求解最小生成树问题的时间复杂度，其蚂 蚁解的构建是基于两种不同的构造图，Ｂｒｏｄｅｒ⁃ｂａｓｅｄ 和 Ｋｒｕｓｋａｌ⁃ｂａｓｅｄ，并证明了最大最小蚂蚁系统求解 最小生成树问题的期望时间上界为 Ο（ｍｎｌｏｇｎ）。 最小割 （ｍｉｎｉｍｕｍ ｃｕｔ） 问题是图论中经典的组 合优化问题，其存在一些多项式求解算法。 跟最小 割相关的问题如最小 ｋ⁃割和 ｍｕｌｔｉｗａｙ 割等问题都是 ＮＰ 难问题［６］ 。 Ｋöｔｚｉｎｇ 等［４０］ 分析了 ＡＣＯ 算法在求 解经典的最小割问题的时间复杂度，并研究了参数 设置对于不同实例的运行时行为的影响。 若参数 α ＝ ０，β ＝ １，对于任意给定的带权图，算法 ＭＭＡＳ ∗ 找 到一个最小割的期望时间上界为 Ο（ ｎ ２ ）；若参数 α ＝ １， β ＝ １， 则 算 法 的 优 化 时 间 为 Ｏ （ｎ－２＋２ｃｎ ）！ （ｎ－２）！ （２ｃｎ ）！ æ è ç ö ø ÷ ，其中 ｃｎ ＝ ｈ ／ ｌ，ｈ 和 ｌ 为最大、最 小蚂蚁算法的信息素边界值；若 ｃｎ ＝ ｋ 为常数，则期 望时间变为 Ο（ｎ ２ｋ ）。 最短路径问题的目标是搜索图中两结点之间的 最短路径。 Ｄｉｊｋｓｔｒａ 算法是求解该问题的典型路由 算法，用于计算一个节点到其他所有节点的最短路 径。 文献［４１⁃４３］研究了最短路径问题，并分别分析 了 ＡＣＯ 算法求解无环、有环、带有噪声情况下最短 路径问题的计算时间。 Ａｔｔｉｒａｔａｎａｓｕｎｔｈｒｏｎ 和 Ｆａｋｃｈａ⁃ ｒｏｅｎｐｈｏｌ ［４１］研究了 ＡＣＯ 算法求解有向无环图单目标 最短路径问题（ ｓｉｎｇｌｅ ｄｅｓｔｉｎａｔｉｏｎ ｓｈｏｒｔｅｓｔ ｐａｔｈ， ＳＤ⁃ ＳＰ）的多项式时间界。 对于顶点数为 ｎ 边数为 ｍ 的 有向无环图，具有 ｎ 只蚂蚁的 ｎ⁃ＡＮＴ 算法能够在期 望时间 Ο（ｎ ２ｍｌｏｇ ｎ ／ ρ）内求解单源最短路径问题。 在此基础上，Ｈｏｒｏｂａ 和 Ｓｕｄｈｏｌｔ ［４２］ 将结果扩充 到最大最小蚂蚁系统（ＭＭＡＳ），得到 ＭＭＡＳＳＤＳＰ关于 单目标最短路径（ＳＤＳＰ）问题和 ＭＭＡＳＡＰＳＰ关于全部 顶点对的最短路径问题（ ａｌｌ⁃ｐａｉｒｓ ｓｈｏｒｔｅｓｔ ｐａｔｈ， ＡＰ⁃ ＳＰ） 的 计 算 时 间 上 界 分 别 为 Ο （ ｌｍ ＋ ｎ ／ ρ ） 和 Ο（ｎｌｏｇ ｎ＋ｌｏｇ ｌｌｏｇ（Δｌ） ／ ρ），后者为目前元启发式算 法（ｍｅｔａ⁃ｈｅｕｒｉｓｔｉｃ）关于 ＡＰＳＰ 问题最好的界。 进一 步，Ｓｕｄｈｏｌｔ 和 Ｔｈｙｓｓｅｎ ［４３］ 讨论了边权数带噪声随机 最短路径问题，给出了噪声强度、近似保证以及平均 时间复杂度之间的权衡关系。 最近，Ｌｉｓｓｏｖｏｉ 和 Ｗｉｔｔ ［４４］ 研究了 λ 只蚂蚁的最 大最小蚂蚁系统 λ⁃ＭＭＡＳ 算法在动态 ＳＤＳＰ 问题上 的时间复杂度。 他们指出每个顶点上放一定数量的 蚂蚁甚至是常数只蚂蚁就能有效地求解动态 ＳＤＳＰ 问题，给出了蚂蚁数量、挥发因子及计算时间之间的 关系。 此 外， 他 们 还 研 究 了 ＭＭＡＳ 算 法 在 动 态 ＭＡＺＥ 函数上的性能［４７］ 。 第 １ 期 夏小云，等：蚁群优化算法的理论研究进展 ·３３·

·34 智能系统学报 第11卷 3.3.3NP难问题 个更好的计算时间界。对于一些实例，算法容易 旅行商问题(traveling salesman problem,TSP) 陷入局部最优，计算时间为指数级。然而，当启发式 是组合优化中著名的NP难问题，也是蚁群算法的 因子足够大时，很快就能够找到最优解。 首个成功的测试问题。Zhou4首次分析了蚁群算 实际上，许多经典的组合优化问题都为NP难 法求解两个TSP实例的计算时间，从理论上首次证 解问题[)。由复杂性理论可知对于这类问题，不存 实了蚁群算法求解NP难问题的有效性，是蚁群算 在多项式时间的确定性算法除非P=NP。蚁群优化 法关于NP难问题时间复杂性分析的首项工作。作 算法求解更多的NP难问题的性能目前还未知，这 者首次提出AC0求解TSP的严格计算时间分析，构 方面的工作才刚开始，对于更深入的了解蚁群算法 造了完全图和非完全图的两个TSP实例，分析和估 的运行机理，求解NP难问题的性能，以及指导算法 计了(1+1)MAX-MIN Ant Algorithm求解TSP实例 设计及应用有重要的现实意义。 的平均计算时间上界：同时讨论了算法中关于能见 表1列举了近十年来蚁群优化算法理论研究的 度和信息素值等控制参数的变化对算法计算时间的 些典型研究成果，包括从简单的拟布尔函数到NP 影响。Kotzing等人[的在文献[45]的基础上进行了 难问题，不同的信息素更新机制，以及参数设置对算 有效的扩展，使用了一种新的蚂蚁解的构造图的方 法性能影响等方面的理论研究成果。 式，表明其具有更强的局部属性，并证明了能够得到 表1蚊群优化算法计算复杂性理论成果 Table 1 The list of theoretical results of Ant Colony Optimization 问题 说明 算法模型 时间复杂度 相关文献 OneMax Onclla() 1-ANT O(nlogn) Neumann(27.2) LeadingOnes LeadingOnes(x)= MMAS O(n2+(nlogn)/p) Neumann等(] Linear function F(x)= MMAS/MMAS O((n'logn)/p) Kotzing等[] Minimum 最小生成树问题 1-ANT O(mn(logn+logwm)） Neumann和Wit[] spanning tree 0(n2)(a=0,B=1): 最小割问题（带权图）：信息素 Minimum cut o（a-2+21 MMAS （(n-2)！(2c.)1 problem 的界为[L月6，=片 Kotzing等[s0 若c=k为常数， 0(n)(ax=1,β=1)： 其中m为给定图的边数，△为 Single Destination 最大出度，1为所有最短路径 Shortest Path, 0(m4Mog(4) (如果不止一条)的最大边数，p n-ANT p Attiratanasunthron SDSP 为AC0算法的挥发因子 All-pairs Shortest MMASAPSP Path(APSP) O(△I'+/p) Horoba和Sudholt【4a O(1+In(T)/p)(A= Dynamic SDSP A-MMAS 2e/Tin) Lissovoi和Wit4 O(n+(1/p)nlnn)(a=1.B= TSP 完全图实例 (1+1)MMAA 0):O(n3+(1/p)nlnn) Zhou[i] (a=1,B=1) TSP G MMASk.O(n'logn+nlogn/p)(a=1,B=1) Kotzing等[o阿

３．３．３ ＮＰ 难问题 旅行商问题（ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ， ＴＳＰ） 是组合优化中著名的 ＮＰ 难问题，也是蚁群算法的 首个成功的测试问题。 Ｚｈｏｕ ［４５］ 首次分析了蚁群算 法求解两个 ＴＳＰ 实例的计算时间，从理论上首次证 实了蚁群算法求解 ＮＰ 难问题的有效性，是蚁群算 法关于 ＮＰ 难问题时间复杂性分析的首项工作。 作 者首次提出 ＡＣＯ 求解 ＴＳＰ 的严格计算时间分析，构 造了完全图和非完全图的两个 ＴＳＰ 实例，分析和估 计了（１＋１） ＭＡＸ⁃ＭＩＮ Ａｎｔ Ａｌｇｏｒｉｔｈｍ 求解 ＴＳＰ 实例 的平均计算时间上界；同时讨论了算法中关于能见 度和信息素值等控制参数的变化对算法计算时间的 影响。 Ｋöｔｚｉｎｇ 等人［４６］在文献［４５］的基础上进行了 有效的扩展，使用了一种新的蚂蚁解的构造图的方 式，表明其具有更强的局部属性，并证明了能够得到 一个更好的计算时间界。 对于一些实例，算法容易 陷入局部最优，计算时间为指数级。 然而，当启发式 因子足够大时，很快就能够找到最优解。 实际上，许多经典的组合优化问题都为 ＮＰ 难 解问题［７］ 。 由复杂性理论可知对于这类问题，不存 在多项式时间的确定性算法除非 Ｐ ＝ＮＰ。 蚁群优化 算法求解更多的 ＮＰ 难问题的性能目前还未知，这 方面的工作才刚开始，对于更深入的了解蚁群算法 的运行机理，求解 ＮＰ 难问题的性能，以及指导算法 设计及应用有重要的现实意义。 表 １ 列举了近十年来蚁群优化算法理论研究的 一些典型研究成果，包括从简单的拟布尔函数到 ＮＰ 难问题，不同的信息素更新机制，以及参数设置对算 法性能影响等方面的理论研究成果。 表 １ 蚁群优化算法计算复杂性理论成果 Ｔａｂｌｅ １ Ｔｈｅ ｌｉｓｔ ｏｆ ｔｈｅｏｒｅｔｉｃａｌ ｒｅｓｕｌｔｓ ｏｆ Ａｎｔ Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ 问题 说明 算法模型 时间复杂度 相关文献 ＯｎｅＭａｘ ＯｎｅＭａｘ（ｘ）＝ ∑ ｎ ｉ＝ １ ｘｉ １⁃ＡＮＴ Ο（ｎｌｏｇｎ） Ｎｅｕｍａｎｎ ［２７，２９］ ＬｅａｄｉｎｇＯｎｅｓ ＬｅａｄｉｎｇＯｎｅｓ（ｘ）＝ ∑ ｎ ｉ＝ １ ∏ ｉ ｊ＝ １ ｘｊ ＭＭＡＳ∗ Ο（ｎ ２＋（ｎｌｏｇｎ） ／ ρ） Ｎｅｕｍａｎｎ 等［３５］ Ｌｉｎｅａｒ ｆｕｎｃｔｉｏｎ Ｆ（ｘ）＝ ∑ ｎ ｉ＝ １ ｗｉ ｘｉ ＭＭＡＳ ／ ＭＭＡＳ∗ Ο（（ｎ ３ ｌｏｇｎ） ／ ρ） Ｋöｔｚｉｎｇ 等［３７］ Ｍｉｎｉｍｕｍ ｓｐａｎｎｉｎｇ ｔｒｅｅ 最小生成树问题 １⁃ＡＮＴ Ο（ｍｎ（ｌｏｇｎ＋ｌｏｇｗｍａｘ）） Ｎｅｕｍａｎｎ 和 Ｗｉｔｔ ［３９］ Ｍｉｎｉｍｕｍ ｃｕｔ ｐｒｏｂｌｅｍ 最小割问题（带权图）；信息素 的界为［ｌ，ｈ］，ｃｎ ＝ ｈ ｌ ， ＭＭＡＳ∗ Ο（ｎ ２ ）（α＝ ０，β ＝ １）； Ｏ （ｎ－２＋２ｃｎ ）！ （ｎ－２）！ （２ｃｎ ）！ æ è ç ö ø ÷ ， 若 ｃｎ ＝ ｋ 为常数， Ο（ｎ ２ｋ ）（α＝ １，β ＝ １）； Ｋöｔｚｉｎｇ 等［４０］ Ｓｉｎｇｌｅ Ｄｅｓｔｉｎａｔｉｏｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ， ＳＤＳＰ 其中 ｍ 为给定图的边数，Δ 为 最大出度， ｌ 为所有最短路径 （如果不止一条）的最大边数，ρ 为 ＡＣＯ 算法的挥发因子 ｎ⁃ＡＮＴ Ο（ ｍΔｌｌｏｇ（Δｌ） ρ ） Ａｔｔｉｒａｔａｎａｓｕｎｔｈｒｏｎ 等［４１］ Ａｌｌ⁃ｐａｉｒｓ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ（ＡＰＳＰ） ＭＭＡＳＡＰＳＰ Ο（Δｌｌ ∗ ＋ｌ ／ ρ） Ｈｏｒｏｂａ 和 Ｓｕｄｈｏｌｔ ［４２］ Ｄｙｎａｍｉｃ ＳＤＳＰ λ⁃ＭＭＡＳ Ο（ｌ＋ｌｌｎ（τｍａｘ ／ τｍｉｎ ） ／ ρ）（λ＝ ２ｅ ／ τｍｉｎ ） Ｌｉｓｓｏｖｏｉ 和 Ｗｉｔｔ ［４４］ ＴＳＰ 完全图实例 （１＋１）ＭＭＡＡ Ο（ｎ ６＋（１ ／ ρ）ｎｌｎｎ）（α＝ １，β ＝ ０）；Ο（ｎ ５＋（１ ／ ρ）ｎｌｎｎ） （α＝ １，β ＝ １） Ｚｈｏｕ ［４５］ ＴＳＰ Ｇ１ ＭＭＡＳ ∗ Ａｒｂ Ο（ｎ ３ ｌｏｇｎ＋ｎｌｏｇｎ ／ ρ）（α＝ １，β ＝ １） Ｋöｔｚｉｎｇ 等［４６］ ·３４· 智 能 系 统 学 报 第 １１ 卷

第1期 夏小云，等：蚁群优化算法的理论研究进展 ·35. 4 结束语 [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 algo- 理论研究中的若干问题进行了分析讨论。当前蚁群 rithm:survey and prospect[].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 Hei- 1)蚁群算法理论分析工具还非常有限，这也是 delberg: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]STUTZLE T,HOOS HH.MAX-MIN ant system[J].Future 2)当前蚁群优化算法理论研究局限于一些简 generation computer systems,2000,16(8):889-914. 化的算法模型，基于种群的、更加复杂的构造过程还 [10]GUTJAHR W J.Mathematical runtime analysis of ACO al- 有待于进一步深入研究。对于n-ANT算法的有效 gorithms:survey on an emerging issue[J].Swarm intelli- gence,2007,1(1):59-79. 性如何，是否蚂蚁的数量与算法的时间复杂度存在 [11]DROSTE S,JANSEN T,WEGENER I.On the analysis of 某种关系还未知。通过研究群体规模、构造过程、算 the (1+1)evolutionary algorithm[].Theoretical comput- 法参数等对算法性能的影响，深入挖掘蚁群优化算 er science,2002,276(1-2):51-81. [12]WEGENER I,WITT C.On the analysis of a simple evolu- 法的潜能，更好地指导算法设计及应用。对于一个 tionary algorithm on quadratic pseudo-boolean functions NP难解组合优化问题，蚁群算法能否获得比已有算 [J].Journal of discrete algorithms,2005,3(1):61-78. 法更好的近似比？如何获得更紧的时间界等，这些 [13]WEGENER I.Towards a theory of randomized search heu- 问题都有待于深入研究。 ristics[M]//ROVAN B,VOJTAS P.Mathematical Foun- 3)将现有蚁群优化算法的理论分析结果扩展 dations of computer science 2003.Berlin Heidelberg: Springer,2003:125-141. 到更多的智能算法中。目前在差分进化算法、分布 [14]WEGENER I.Methods for the analysis of evolutionary al- 评估算法、粒子群算法以及Memetic算法等随机启 gorithms 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[.Theoretical computer 步扩充。通过对更多算法、更多问题的研究，从中找 science,2002,287(1):101-130. 出一些共性的东西，进一步丰富和增强群智能搜索 [16]HE J,YAO X.Towards an analytic framework for analy- 算法的理论基础。 sing 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 a- nalysis of the first hitting time of population-based evolu- 参考文献： tionary algorithms[J].IEEE transactions on evolutionary computation,2002,6(5):495-511. [1]DORIGO M,MANIEZZO V,COLORNI A.Theantsystem: [19]GUTJAHR W J.A graph-based ant system and its conver- An autocatalytic optimizing process Technical Report 91-016 gence[J].Future generation computer systems,2000,16 [R].Milan,Italy:Dipartimento di Elettronica,Politecnico (8):873-888. di Milano,1991. [20]STUTZLE T,DORIGO M.A short convergence proof for a [2]DORIG0M,STUTZLE T.蚁群优化[M].张军，胡晓敏， class of ACO algorithms[J].IEEE transactions on evolu- 罗旭耀，译.北京：清华大学出版社，2007：110-246. tionary computation,2002,6(4):358-365

４ 结束语 本文从蚁群算法框架、理论分析方法以及理论 研究结果等方面出发，对蚁群优化算法的理论研究 进展进行了归纳和介绍。 此外，还对蚁群优化算法 理论研究中的若干问题进行了分析讨论。 当前蚁群 算法的理论研究成果仍然有限，其理论分析方法和 数学工具有待进一步完善和探索。 蚁群算法理论研 究中还有许多亟待解决的问题。 １）蚁群算法理论分析工具还非常有限，这也是 阻碍其向前发展的一个主要因素。 现有的理论分析 方法主要是马尔可夫链理论、适应值划分技术及漂 移分析等方法。 这些工具或者本身比较复杂，或者 只是适应一些特殊情形的分析，甚至还需要满足一 些严格的条件才能使用。 因此寻求新的方法和工具 也是未来的一个方向。 ２）当前蚁群优化算法理论研究局限于一些简 化的算法模型，基于种群的、更加复杂的构造过程还 有待于进一步深入研究。 对于 ｎ⁃ＡＮＴ 算法的有效 性如何，是否蚂蚁的数量与算法的时间复杂度存在 某种关系还未知。 通过研究群体规模、构造过程、算 法参数等对算法性能的影响，深入挖掘蚁群优化算 法的潜能，更好地指导算法设计及应用。 对于一个 ＮＰ 难解组合优化问题，蚁群算法能否获得比已有算 法更好的近似比？ 如何获得更紧的时间界等，这些 问题都有待于深入研究。 ３）将现有蚁群优化算法的理论分析结果扩展 到更多的智能算法中。 目前在差分进化算法、分布 评估算法、粒子群算法以及 Ｍｅｍｅｔｉｃ 算法等随机启 发式搜索的理论研究还非常有限，可以尝试将现有 的理论分析结论进行有效扩展。 此外，当前蚁群算 法主要关注离散空间优化，可以向连续优化做进一 步扩充。 通过对更多算法、更多问题的研究，从中找 出一些共性的东西，进一步丰富和增强群智能搜索 算法的理论基础。 蚁群优化算法理论研究中涉及到的问题很多， 本文不可能做到面面俱到，希望能够起到一个抛砖 引玉的作用，对于今后更加深入的研究能够有所帮 助和启发。 参考文献： ［１］ＤＯＲＩＧＯ Ｍ， ＭＡＮＩＥＺＺＯ Ｖ， ＣＯＬＯＲＮＩ Ａ． Ｔｈｅａｎｔｓｙｓｔｅｍ： Ａｎ ａｕｔｏｃａｔａｌｙｔｉｃ ｏｐｔｉｍｉｚｉｎｇ ｐｒｏｃｅｓｓ Ｔｅｃｈｎｉｃａｌ Ｒｅｐｏｒｔ ９１⁃０１６ ［Ｒ］． Ｍｉｌａｎ， Ｉｔａｌｙ： Ｄｉｐａｒｔｉｍｅｎｔｏ ｄｉ Ｅｌｅｔｔｒｏｎｉｃａ， Ｐｏｌｉｔｅｃｎｉｃｏ ｄｉ Ｍｉｌａｎｏ， １９９１． ［２］ＤＯＲＩＧＯ Ｍ， ＳＴＵＴＺＬＥ Ｔ． 蚁群优化［Ｍ］． 张军， 胡晓敏， 罗旭耀， 译． 北京： 清华大学出版社， ２００７： １１０⁃２４６． ［３］ ＤＯＲＩＧＯ Ｍ， ＢＬＵＭ Ｃ． Ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ｔｈｅｏｒｙ： ａ ｓｕｒｖｅｙ［ Ｊ］． Ｔｈｅｏｒｅｔｉｃａｌ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２００５， ３４４ （ ２⁃ ３）： ２４３⁃２７８． ［４］段海滨， 王道波， 于秀芬． 蚁群算法的研究现状及其展 望［Ｊ］． 中国工程科学， ２００７， ９（２）： ９８⁃１０２． ＤＵＡＮ Ｈａｉｂｉｎ， ＷＡＮＧ Ｄａｏｂｏ， ＹＵ Ｘｉｕｆｅｎ． Ａｎｔ ｃｏｌｏｎｙ ａｌｇｏ⁃ ｒｉｔｈｍ： ｓｕｒｖｅｙ ａｎｄ ｐｒｏｓｐｅｃｔ［Ｊ］． Ｅｎｇｉｎｅｅｒｉｎｇ ｓｃｉｅｎｃｅ， ２００７， ９（２）： ９８⁃１０２． ［５］ＮＯＣＥＤＡＬ Ｊ， ＷＲＩＧＨＴ Ｓ Ｊ． Ｎｕｍｅｒｉｃａｌ ｏｐｔｉｍｉｚａｔｉｏｎ［ Ｍ］． Ｎｅｗ Ｙｏｒｋ： Ｓｐｒｉｎｇｅｒ， ２０００． ［６］ＶＡＺＩＲＡＮＩ Ｖ Ｖ． Ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ［Ｍ］． Ｂｅｒｌｉｎ Ｈｅｉ⁃ ｄｅｌｂｅｒｇ： Ｓｐｒｉｎｇｅｒ， ２００３． ［７］ＧＡＲＥＹ Ｍ Ｒ， ＪＯＨＮＳＯＮ Ｄ Ｓ． Ｃｏｍｐｕｔｅｒｓ ａｎｄ Ｉｎｔｒａｃｔａｂｉｌｉｔｙ⁃ Ａ Ｇｕｉｄｅ ｔｏ ｔｈｅ Ｔｈｅｏｒｙ ｏｆ ＮＰ⁃Ｃｏｍｐｌｅｔｅｎｅｓｓ［Ｍ］． Ｎｅｗ Ｙｏｒｋ： Ｆｒｅｅｍａｎ Ｗ Ｈ ａｎｄ Ｃｏｍｐａｎｙ， １９７９． ［８］ＣＯＬＯＲＮＩ Ａ， ＤＯＲＩＧＯ Ｍ， ＭＡＮＩＥＺＺＯ Ｖ． Ａｎ ｉｎｖｅｓｔｉｇａｔｉｏｎ ｏｆ ｓｏｍｅ ｐｒｏｐｅｒｔｉｅｓ ｏｆ ａｎ “Ａｎｔ ａｌｇｏｒｉｔｈｍ”［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｐａｒａｌｌｅｌ Ｐｒｏｂｌｅｍ Ｓｏｌｖｉｎｇ ｆｒｏｍ Ｎａｔｕｒｅ ＩＩ （ ＰＰＳＮ ９２）． Ｂｒｕｓｓｅｌｓ， Ｂｅｌｇｉｕｍ， １９９２： ５１５⁃５２６． ［９］ＳＴÜＴＺＬＥ Ｔ， ＨＯＯＳ Ｈ Ｈ． ＭＡＸ⁃ＭＩＮ ａｎｔ ｓｙｓｔｅｍ［Ｊ］． Ｆｕｔｕｒｅ ｇｅｎｅｒａｔｉｏｎ ｃｏｍｐｕｔｅｒ ｓｙｓｔｅｍｓ， ２０００， １６（８）： ８８９⁃９１４． ［１０］ＧＵＴＪＡＨＲ Ｗ Ｊ． Ｍａｔｈｅｍａｔｉｃａｌ ｒｕｎｔｉｍｅ ａｎａｌｙｓｉｓ ｏｆ ＡＣＯ ａｌ⁃ ｇｏｒｉｔｈｍｓ： ｓｕｒｖｅｙ ｏｎ ａｎ ｅｍｅｒｇｉｎｇ ｉｓｓｕｅ［ Ｊ］． Ｓｗａｒｍ ｉｎｔｅｌｌｉ⁃ ｇｅｎｃｅ， ２００７， １（１）： ５９⁃７９． ［１１］ＤＲＯＳＴＥ Ｓ， ＪＡＮＳＥＮ Ｔ， ＷＥＧＥＮＥＲ Ｉ． Ｏｎ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ｔｈｅ （１＋１） ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍ［Ｊ］． Ｔｈｅｏｒｅｔｉｃａｌ ｃｏｍｐｕｔ⁃ ｅｒ ｓｃｉｅｎｃｅ， ２００２， ２７６（１⁃２）： ５１⁃８１． ［１２］ＷＥＧＥＮＥＲ Ｉ， ＷＩＴＴ Ｃ． Ｏｎ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ａ ｓｉｍｐｌｅ ｅｖｏｌｕ⁃ ｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍ ｏｎ ｑｕａｄｒａｔｉｃ ｐｓｅｕｄｏ⁃ｂｏｏｌｅａｎ ｆｕｎｃｔｉｏｎｓ ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｄｉｓｃｒｅｔｅ ａｌｇｏｒｉｔｈｍｓ， ２００５， ３（１）： ６１⁃７８． ［１３］ＷＥＧＥＮＥＲ Ｉ． Ｔｏｗａｒｄｓ ａ ｔｈｅｏｒｙ ｏｆ ｒａｎｄｏｍｉｚｅｄ ｓｅａｒｃｈ ｈｅｕ⁃ ｒｉｓｔｉｃｓ［Ｍ］ ／ ／ ＲＯＶＡＮ Ｂ， ＶＯＪＴÁŠ Ｐ． Ｍａｔｈｅｍａｔｉｃａｌ Ｆｏｕｎ⁃ ｄａｔｉｏｎｓ ｏｆ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ ２００３． Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ： Ｓｐｒｉｎｇｅｒ， ２００３： １２５⁃１４１． ［１４］ＷＥＧＥＮＥＲ Ｉ． Ｍｅｔｈｏｄｓ ｆｏｒ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ｅｖｏｌｕｔｉｏｎａｒｙ ａｌ⁃ ｇｏｒｉｔｈｍｓ ｏｎ ｐｓｅｕｄｏ⁃ｂｏｏｌｅａｎ ｆｕｎｃｔｉｏｎｓ ［ Ｍ］ ／ ／ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｏｐｔｉｍｉｚａｔｉｏｎ． Ｄｏｒｄｒｅｃｈｔ： Ｋｌｕｗｅｒ Ａｃａｄｅｍｉｃ Ｐｕｂｌｉｓｈｅｒｓ， ２００２， ４８： ３４９⁃３６９． ［１５］ＢＥＹＥＲ Ｈ Ｇ， ＳＣＨＷＥＦＥＬ Ｈ Ｐ， ＷＥＧＥＮＥＲ Ｉ． Ｈｏｗ ｔｏ ａｎａｌｙｓｅ ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍｓ ［ Ｊ］． Ｔｈｅｏｒｅｔｉｃａｌ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２００２， ２８７（１）： １０１⁃１３０． ［１６］ＨＥ Ｊ， ＹＡＯ Ｘ． Ｔｏｗａｒｄｓ ａｎ ａｎａｌｙｔｉｃ ｆｒａｍｅｗｏｒｋ ｆｏｒ ａｎａｌｙ⁃ ｓｉｎｇ ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎ ｔｉｍｅ ｏｆ ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍｓ ［ Ｊ］． Ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００３， １４５（１⁃２）： ５９⁃９７． ［１７］ＨＥ Ｊ， ＹＡＯ Ｘ． Ｄｒｉｆｔ ａｎａｌｙｓｉｓ ａｎｄ ａｖｅｒａｇｅ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍｓ ［ Ｊ ］． Ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００１， １２７（１）： ５７⁃８５． ［１８］ＨＥ Ｊ， ＹＡＯ Ｘ． Ｆｒｏｍ ａｎ ｉｎｄｉｖｉｄｕａｌ ｔｏ ａ ｐｏｐｕｌａｔｉｏｎ： ａｎ ａ⁃ ｎａｌｙｓｉｓ ｏｆ ｔｈｅ ｆｉｒｓｔ ｈｉｔｔｉｎｇ ｔｉｍｅ ｏｆ ｐｏｐｕｌａｔｉｏｎ⁃ｂａｓｅｄ ｅｖｏｌｕ⁃ ｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍｓ ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｅｖｏｌｕｔｉｏｎａｒｙ ｃｏｍｐｕｔａｔｉｏｎ， ２００２， ６（５）： ４９５⁃５１１． ［１９］ＧＵＴＪＡＨＲ Ｗ Ｊ． Ａ ｇｒａｐｈ⁃ｂａｓｅｄ ａｎｔ ｓｙｓｔｅｍ ａｎｄ ｉｔｓ ｃｏｎｖｅｒ⁃ ｇｅｎｃｅ［Ｊ］． Ｆｕｔｕｒｅ ｇｅｎｅｒａｔｉｏｎ ｃｏｍｐｕｔｅｒ ｓｙｓｔｅｍｓ， ２０００， １６ （８）： ８７３⁃８８８． ［２０］ＳＴÜＴＺＬＥ Ｔ， ＤＯＲＩＧＯ Ｍ． Ａ ｓｈｏｒｔ ｃｏｎｖｅｒｇｅｎｃｅ ｐｒｏｏｆ ｆｏｒ ａ ｃｌａｓｓ ｏｆ ＡＣＯ ａｌｇｏｒｉｔｈｍｓ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｅｖｏｌｕ⁃ ｔｉｏｎａｒｙ ｃｏｍｐｕｔａｔｉｏｎ， ２００２， ６（４）： ３５８⁃３６５． 第 １ 期 夏小云，等：蚁群优化算法的理论研究进展 ·３５·

·36. 智能系统学报 第11卷 [21]GUTJAHR W J.On the finite-time dynamics of ant colony of Genetic and Evolutionary Computation Conference optimization[].Methodology and computing in applied (GECCO'2010).Portland,USA,2010:63-70. probability,2006,8(1):105-133. [37]KOTZING T,NEUMANN F,SUDHOLT D,et al.Simple 「22]黄翰，郝志峰，吴春国，等.蚁群算法的收敛速度分析 Max-Min ant systems and the optimization of linear pseudo- [J].计算机学报，2007,30(8)：1344-1353. Boolean functions[C]//Proceedings of the 11th Work-shop HUANG Han,HAO Zhifeng,WU Chunguo,et al.The on Foundations of Genetic Algorithms (FOGA 2011).New convergence speed of ant colony optimization[].Chinese York,NY,USA,2011:209-218. journal of computers,2007,30(8):1344-1353. [38]NEUMANN F,SUDHOLT D,WITT C.Rigorous analyses [23]BIRATTARI M,Dicaro G,DORIGO M.Toward the formal for the combination of ant colony optimization and local foundation of ant programming M ]//DORIGO M,DI search[C]//Proceedings of the 6th International Confer- CARO G.SAMPELS M.Ant Algorithms.Berlin Heidel- ence on Ant Colony Optimization and Swarm Intelligence berg:Springer-Verlag,2002,2463:188-201. (ANTS08).Brussels,Belgium,2008:132-143. [24]MEULEAU N,DORIGO M.Ant colony optimization and [39]NEUMANN F,WITT C.Ant colony optimization and the stochastic gradient descent[.Artificial life,2002,8 minimum spanning tree problem[J].Theoretical computer (2)：103-121. science,2010,411(25):2406-2413. [25]ZLOCHIN M.BIRATTARI M,MEULEAU N,et al.Mod- [40]KOTZING T,LEHRE P K.OLIVETO P S,et al.Ant col- el-based search for combinatorial optimization:a critical ony optimization and the minimum cut problem[C]//Pro- survey[J].Annals of operations research,2004,131(1- ceedings of the 12th Annual Conference on Genetic and 4)：373-395. Evolutionary Computation Conference (GECCO'10).New [26]GUTJAHR W J.A generalized convergence result for the York,NY,USA,2010:1393-1400 graph-based ant system metaheuristic[J].Probability in [41]ATTIRATANASUNTHRON N,FAKCHAROENPHOL J.A the engineering and informational sciences,2003,17(4): running time analysis of an ant colony optimization algo- 545.569. rithm for shortest paths in directed acyclic graphs[J].In- [27]NEUMANN F,WITT C.Runtime analysis of a simple ant formation processing letters,2008,105(3):88-92. colony optimization algorithm C//Proceedings of the 17th [42]SUDHOLT D,THYSSEN C.Running time analysis of Ant International Symposium on Algorithms,ISAAC 2006. Colony Optimization for shortest path problems[J].Journal Kolkata,India,2006,4288:618-627. of discrete algorithms,2012,10:165-180. [28]NEUMANN F,SUDHOLT D,Wit C.Comparing variants [43]SUDHOLT D.THYSSEN C.A simple ant colony optimizer of MMAS ACO algorithms on pseudo-Boolean functions for stochastic shortest path problems [J].Algorithmica, [C]//Proceedings of International Workshop,SLS 2007. 2012,64(4):643-672. Brussels,Belgium,2007:61-75. [44]LISSOVOI A,WITT C.Runtime analysis of ant colony op- [29]NEUMANN F,WITT C.Runtime analysis of a simple ant timization on dynamic shortest path problems[J.Theoreti- colony optimization algorithm[].Algorithmica,2009,54 cal computer science,2015,561:73-85 (2):243-255. [45]ZHOU Y R.Runtime analysis of an ant colony optimization [30]GUTJAHR W J.First steps to the runtime complexity anal- algorithm for TSP instances[J].IEEE transactions on evo- ysis of ant colony optimization[J].Computers&operations lutionary computation,2009,13(5):1083-1092. research,2008,35(9):2711-2727. [46]KOTZING T,NEUMANN F,ROGLIN H,et al.Theoreti- [31]DOERR B,JOHANNSEN D.Refined runtime analysis of a cal analysis of two ACO approaches for the traveling sales basic ant colony optimization algorithm[C]//Proceedings man problem[J].Swarm intelligence,2012,6(1):1-21. of the IEEE Congress on Evolutionary Computation (CEC [47]LISSOVOI A,WITT C.MMAS versus population-based 2007).Singapore,2007:501-507. EA on a family of dynamic fitness functions[J.Algorith- [32]DOERR B,NEUMANN F,SUDHOLT D,et al.On the mica,2015,doi:10.1007/s00453-015-9975-z. runtime analysis of the 1-ANT ACO algorithm[C]//Pro- 作者简介： ceedings of Genetic and Evolutionary Computation Confer- 夏小云，男，1982年生，博士研究 ence (GECCO'2007).London,England,2007:33-40. 生，主要研究方向为计算智能与机器 [33]DOERR B,NEUMANN F,SUDHOL D,et al.Runtime a- 学习。 nalysis 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, 周育人，男，1965年生，教授，博士 10(3):409-433. 生导师，博士，主要研究方向为计算智 [35]NEUMANN F,SUDHOLT D,WITT C.Analysis of differ- 能、数据挖掘及社会网络。主持国家 ent MMAS ACO algorithms on unimodal functions and plat- 省部级项目多项，发表学术论文50 eaus[J].Swarm intelligence,2009,3(1):35-68. 余篇。 [36]NEUMANN F,SUDHOLT D,WITT C.A few ants are e- nough:ACO with Iteration-best update[C]//Proceedings

［２１］ＧＵＴＪＡＨＲ Ｗ Ｊ． Ｏｎ ｔｈｅ ｆｉｎｉｔｅ⁃ｔｉｍｅ ｄｙｎａｍｉｃｓ ｏｆ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ［ Ｊ］． Ｍｅｔｈｏｄｏｌｏｇｙ ａｎｄ ｃｏｍｐｕｔｉｎｇ ｉｎ ａｐｐｌｉｅｄ ｐｒｏｂａｂｉｌｉｔｙ， ２００６， ８（１）： １０５⁃１３３． ［２２］黄翰， 郝志峰， 吴春国，等． 蚁群算法的收敛速度分析 ［Ｊ］． 计算机学报， ２００７， ３０（８）： １３４４⁃１３５３． ＨＵＡＮＧ Ｈａｎ， ＨＡＯ Ｚｈｉｆｅｎｇ， ＷＵ Ｃｈｕｎｇｕｏ， ｅｔ ａｌ． Ｔｈｅ ｃｏｎｖｅｒｇｅｎｃｅ ｓｐｅｅｄ ｏｆ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ［ Ｊ］． Ｃｈｉｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒｓ， ２００７， ３０（８）： １３４４⁃１３５３． ［２３］ＢＩＲＡＴＴＡＲＩ Ｍ， Ｄｉｃａｒｏ Ｇ， ＤＯＲＩＧＯ Ｍ． Ｔｏｗａｒｄ ｔｈｅ ｆｏｒｍａｌ ｆｏｕｎｄａｔｉｏｎ ｏｆ ａｎｔ ｐｒｏｇｒａｍｍｉｎｇ ［ Ｍ ］ ／ ／ ＤＯＲＩＧＯ Ｍ， ＤＩ ＣＡＲＯ Ｇ， ＳＡＭＰＥＬＳ Ｍ． Ａｎｔ Ａｌｇｏｒｉｔｈｍｓ． Ｂｅｒｌｉｎ Ｈｅｉｄｅｌ⁃ ｂｅｒｇ： Ｓｐｒｉｎｇｅｒ⁃Ｖｅｒｌａｇ， ２００２， ２４６３： １８８⁃２０１． ［２４］ ＭＥＵＬＥＡＵ Ｎ， ＤＯＲＩＧＯ Ｍ． Ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ ｓｔｏｃｈａｓｔｉｃ ｇｒａｄｉｅｎｔ ｄｅｓｃｅｎｔ ［ Ｊ］． Ａｒｔｉｆｉｃｉａｌ ｌｉｆｅ， ２００２， ８ （２）： １０３⁃１２１． ［２５］ＺＬＯＣＨＩＮ Ｍ， ＢＩＲＡＴＴＡＲＩ Ｍ， ＭＥＵＬＥＡＵ Ｎ， ｅｔ ａｌ． Ｍｏｄ⁃ ｅｌ⁃ｂａｓｅｄ ｓｅａｒｃｈ ｆｏｒ ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ： ａ ｃｒｉｔｉｃａｌ ｓｕｒｖｅｙ［ Ｊ］． Ａｎｎａｌｓ ｏｆ ｏｐｅｒａｔｉｏｎｓ ｒｅｓｅａｒｃｈ， ２００４， １３１（ １⁃ ４）： ３７３⁃３９５． ［２６］ ＧＵＴＪＡＨＲ Ｗ Ｊ． Ａ ｇｅｎｅｒａｌｉｚｅｄ ｃｏｎｖｅｒｇｅｎｃｅ ｒｅｓｕｌｔ ｆｏｒ ｔｈｅ ｇｒａｐｈ⁃ｂａｓｅｄ ａｎｔ ｓｙｓｔｅｍ ｍｅｔａｈｅｕｒｉｓｔｉｃ ［ Ｊ］． Ｐｒｏｂａｂｉｌｉｔｙ ｉｎ ｔｈｅ ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ ｉｎｆｏｒｍａｔｉｏｎａｌ ｓｃｉｅｎｃｅｓ， ２００３， １７（４）： ５４５⁃５６９． ［２７］ＮＥＵＭＡＮＮ Ｆ， ＷＩＴＴ Ｃ． Ｒｕｎｔｉｍｅ ａｎａｌｙｓｉｓ ｏｆ ａ ｓｉｍｐｌｅ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １７ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ａｌｇｏｒｉｔｈｍｓ， ＩＳＡＡＣ ２００６． Ｋｏｌｋａｔａ， Ｉｎｄｉａ， ２００６， ４２８８： ６１８⁃６２７． ［２８］ＮＥＵＭＡＮＮ Ｆ， ＳＵＤＨＯＬＴ Ｄ， Ｗｉｔ Ｃ． Ｃｏｍｐａｒｉｎｇ ｖａｒｉａｎｔｓ ｏｆ ＭＭＡＳ ＡＣＯ ａｌｇｏｒｉｔｈｍｓ ｏｎ ｐｓｅｕｄｏ⁃Ｂｏｏｌｅａｎ ｆｕｎｃｔｉｏｎｓ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ， ＳＬＳ ２００７． Ｂｒｕｓｓｅｌｓ， Ｂｅｌｇｉｕｍ， ２００７： ６１⁃７５． ［２９］ＮＥＵＭＡＮＮ Ｆ， ＷＩＴＴ Ｃ． Ｒｕｎｔｉｍｅ ａｎａｌｙｓｉｓ ｏｆ ａ ｓｉｍｐｌｅ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ［ Ｊ］． Ａｌｇｏｒｉｔｈｍｉｃａ， ２００９， ５４ （２）： ２４３⁃２５５． ［３０］ＧＵＴＪＡＨＲ Ｗ Ｊ． Ｆｉｒｓｔ ｓｔｅｐｓ ｔｏ ｔｈｅ ｒｕｎｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ａｎａｌ⁃ ｙｓｉｓ ｏｆ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］． Ｃｏｍｐｕｔｅｒｓ ＆ ｏｐｅｒａｔｉｏｎｓ ｒｅｓｅａｒｃｈ， ２００８， ３５（９）： ２７１１⁃２７２７． ［３１］ＤＯＥＲＲ Ｂ， ＪＯＨＡＮＮＳＥＮ Ｄ． Ｒｅｆｉｎｅｄ ｒｕｎｔｉｍｅ ａｎａｌｙｓｉｓ ｏｆ ａ ｂａｓｉｃ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ Ｃｏｎｇｒｅｓｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ （ＣＥＣ ２００７）． Ｓｉｎｇａｐｏｒｅ， ２００７： ５０１⁃５０７． ［３２］ＤＯＥＲＲ Ｂ， ＮＥＵＭＡＮＮ Ｆ， ＳＵＤＨＯＬＴ Ｄ， ｅｔ ａｌ． Ｏｎ ｔｈｅ ｒｕｎｔｉｍｅ ａｎａｌｙｓｉｓ ｏｆ ｔｈｅ １⁃ＡＮＴ ＡＣＯ ａｌｇｏｒｉｔｈｍ［Ｃ］ ／ ／ Ｐｒｏ⁃ ｃｅｅｄｉｎｇｓ ｏｆ Ｇｅｎｅｔｉｃ ａｎｄ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ Ｃｏｎｆｅｒ⁃ ｅｎｃｅ （ＧＥＣＣＯ’２００７）． Ｌｏｎｄｏｎ， Ｅｎｇｌａｎｄ， ２００７： ３３⁃４０． ［３３］ＤＯＥＲＲ Ｂ， ＮＥＵＭＡＮＮ Ｆ， ＳＵＤＨＯＬ Ｄ， ｅｔ ａｌ． Ｒｕｎｔｉｍｅ ａ⁃ ｎａｌｙｓｉｓ ｏｆ ｔｈｅ １⁃ＡＮＴ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚｅｒ［ Ｊ］． Ｔｈｅｏｒｅｔｉｃａｌ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２０１１， ４１２（１７）： １６２９⁃１６４４． ［３４］ＧＵＴＪＡＨＲ Ｗ Ｊ， ＳＥＢＡＳＴＩＡＮＩ Ｇ． Ｒｕｎｔｉｍｅ ａｎａｌｙｓｉｓ ｏｆ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ｗｉｔｈ ｂｅｓｔ⁃ｓｏ⁃ｆａｒ ｒｅｉｎｆｏｒｃｅｍｅｎｔ ［ Ｊ ］． Ｍｅｔｈｏｄｏｌｏｇｙ ａｎｄ ｃｏｍｐｕｔｉｎｇ ｉｎ ａｐｐｌｉｅｄ ｐｒｏｂａｂｉｌｉｔｙ， ２００８， １０（３）： ４０９⁃４３３． ［３５］ＮＥＵＭＡＮＮ Ｆ， ＳＵＤＨＯＬＴ Ｄ， ＷＩＴＴ Ｃ． Ａｎａｌｙｓｉｓ ｏｆ ｄｉｆｆｅｒ⁃ ｅｎｔ ＭＭＡＳ ＡＣＯ ａｌｇｏｒｉｔｈｍｓ ｏｎ ｕｎｉｍｏｄａｌ ｆｕｎｃｔｉｏｎｓ ａｎｄ ｐｌａｔ⁃ ｅａｕｓ［Ｊ］． Ｓｗａｒｍ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００９， ３（１）： ３５⁃６８． ［３６］ＮＥＵＭＡＮＮ Ｆ， ＳＵＤＨＯＬＴ Ｄ， ＷＩＴＴ Ｃ． Ａ ｆｅｗ ａｎｔｓ ａｒｅ ｅ⁃ ｎｏｕｇｈ： ＡＣＯ ｗｉｔｈ Ｉｔｅｒａｔｉｏｎ⁃ｂｅｓｔ ｕｐｄａｔｅ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｇｅｎｅｔｉｃ ａｎｄ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ （ＧＥＣＣＯ’２０１０）． Ｐｏｒｔｌａｎｄ， ＵＳＡ， ２０１０： ６３⁃７０． ［３７］ＫÖＴＺＩＮＧ Ｔ， ＮＥＵＭＡＮＮ Ｆ， ＳＵＤＨＯＬＴ Ｄ， ｅｔ ａｌ． Ｓｉｍｐｌｅ Ｍａｘ⁃Ｍｉｎ ａｎｔ ｓｙｓｔｅｍｓ ａｎｄ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｌｉｎｅａｒ ｐｓｅｕｄｏ⁃ Ｂｏｏｌｅａｎ ｆｕｎｃｔｉｏｎｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １１ｔｈ Ｗｏｒｋ⁃ｓｈｏｐ ｏｎ Ｆｏｕｎｄａｔｉｏｎｓ ｏｆ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍｓ （ＦＯＧＡ ２０１１）． Ｎｅｗ Ｙｏｒｋ， ＮＹ， ＵＳＡ， ２０１１： ２０９⁃２１８． ［３８］ＮＥＵＭＡＮＮ Ｆ， ＳＵＤＨＯＬＴ Ｄ， ＷＩＴＴ Ｃ． Ｒｉｇｏｒｏｕｓ ａｎａｌｙｓｅｓ ｆｏｒ ｔｈｅ ｃｏｍｂｉｎａｔｉｏｎ ｏｆ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ ｌｏｃａｌ ｓｅａｒｃｈ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ６ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒ⁃ ｅｎｃｅ ｏｎ Ａｎｔ Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ Ｓｗａｒｍ Ｉｎｔｅｌｌｉｇｅｎｃｅ （ＡＮＴＳ０８）． Ｂｒｕｓｓｅｌｓ， Ｂｅｌｇｉｕｍ， ２００８： １３２⁃１４３． ［３９］ ＮＥＵＭＡＮＮ Ｆ， ＷＩＴＴ Ｃ． Ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ ｔｈｅ ｍｉｎｉｍｕｍ ｓｐａｎｎｉｎｇ ｔｒｅｅ ｐｒｏｂｌｅｍ［ Ｊ］． Ｔｈｅｏｒｅｔｉｃａｌ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２０１０， ４１１（２５）： ２４０６⁃２４１３． ［４０］ＫÖＴＺＩＮＧ Ｔ， ＬＥＨＲＥ Ｐ Ｋ， ＯＬＩＶＥＴＯ Ｐ Ｓ， ｅｔ ａｌ． Ａｎｔ ｃｏｌ⁃ ｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ ｔｈｅ ｍｉｎｉｍｕｍ ｃｕｔ ｐｒｏｂｌｅｍ［Ｃ］ ／ ／ Ｐｒｏ⁃ ｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １２ｔｈ Ａｎｎｕａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｇｅｎｅｔｉｃ ａｎｄ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ （ＧＥＣＣＯ’ １０）． Ｎｅｗ Ｙｏｒｋ， ＮＹ， ＵＳＡ， ２０１０： １３９３⁃１４００． ［４１］ＡＴＴＩＲＡＴＡＮＡＳＵＮＴＨＲＯＮ Ｎ， ＦＡＫＣＨＡＲＯＥＮＰＨＯＬ Ｊ． Ａ ｒｕｎｎｉｎｇ ｔｉｍｅ ａｎａｌｙｓｉｓ ｏｆ ａｎ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏ⁃ ｒｉｔｈｍ ｆｏｒ ｓｈｏｒｔｅｓｔ ｐａｔｈｓ ｉｎ ｄｉｒｅｃｔｅｄ ａｃｙｃｌｉｃ ｇｒａｐｈｓ［ Ｊ］． Ｉｎ⁃ ｆｏｒｍａｔｉｏｎ ｐｒｏｃｅｓｓｉｎｇ ｌｅｔｔｅｒｓ， ２００８， １０５（３）： ８８⁃９２． ［４２］ＳＵＤＨＯＬＴ Ｄ， ＴＨＹＳＳＥＮ Ｃ． Ｒｕｎｎｉｎｇ ｔｉｍｅ ａｎａｌｙｓｉｓ ｏｆ Ａｎｔ Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ ｆｏｒ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｐｒｏｂｌｅｍｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｄｉｓｃｒｅｔｅ ａｌｇｏｒｉｔｈｍｓ， ２０１２， １０： １６５⁃１８０． ［４３］ＳＵＤＨＯＬＴ Ｄ， ＴＨＹＳＳＥＮ Ｃ． Ａ ｓｉｍｐｌｅ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚｅｒ ｆｏｒ ｓｔｏｃｈａｓｔｉｃ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｐｒｏｂｌｅｍｓ ［ Ｊ ］． Ａｌｇｏｒｉｔｈｍｉｃａ， ２０１２， ６４（４）： ６４３⁃６７２． ［４４］ＬＩＳＳＯＶＯＩ Ａ， ＷＩＴＴ Ｃ． Ｒｕｎｔｉｍｅ ａｎａｌｙｓｉｓ ｏｆ ａｎｔ ｃｏｌｏｎｙ ｏｐ⁃ ｔｉｍｉｚａｔｉｏｎ ｏｎ ｄｙｎａｍｉｃ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｐｒｏｂｌｅｍｓ［Ｊ］． Ｔｈｅｏｒｅｔｉ⁃ ｃａｌ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２０１５， ５６１： ７３⁃８５． ［４５］ＺＨＯＵ Ｙ Ｒ． Ｒｕｎｔｉｍｅ ａｎａｌｙｓｉｓ ｏｆ ａｎ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ＴＳＰ ｉｎｓｔａｎｃｅｓ［Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｅｖｏ⁃ ｌｕｔｉｏｎａｒｙ ｃｏｍｐｕｔａｔｉｏｎ， ２００９， １３（５）： １０８３⁃１０９２． ［４６］ＫÖＴＺＩＮＧ Ｔ， ＮＥＵＭＡＮＮ Ｆ， ＲÖＧＬＩＮ Ｈ， ｅｔ ａｌ． Ｔｈｅｏｒｅｔｉ⁃ ｃａｌ ａｎａｌｙｓｉｓ ｏｆ ｔｗｏ ＡＣＯ ａｐｐｒｏａｃｈｅｓ ｆｏｒ ｔｈｅ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓ ｍａｎ ｐｒｏｂｌｅｍ［Ｊ］． Ｓｗａｒｍ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０１２， ６（１）： １⁃２１． ［４７］ ＬＩＳＳＯＶＯＩ Ａ， ＷＩＴＴ Ｃ． ＭＭＡＳ ｖｅｒｓｕｓ ｐｏｐｕｌａｔｉｏｎ⁃ｂａｓｅｄ ＥＡ ｏｎ ａ ｆａｍｉｌｙ ｏｆ ｄｙｎａｍｉｃ ｆｉｔｎｅｓｓ ｆｕｎｃｔｉｏｎｓ［Ｊ］． Ａｌｇｏｒｉｔｈ⁃ ｍｉｃａ， ２０１５， ｄｏｉ： １０．１００７ ／ ｓ００４５３⁃０１５⁃９９７５⁃ｚ． 作者简介： 夏小云，男，１９８２ 年生，博士研究 生，主要研究方向为计算智能与机器 学习。 周育人，男，１９６５ 年生，教授，博士 生导师，博士，主要研究方向为计算智 能、数据挖掘及社会网络。 主持国家、 省部级 项 目 多 项， 发 表 学 术 论 文 ５０ 余篇。 ·３６· 智 能 系 统 学 报 第 １１ 卷