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

第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,0<n,<1 则对于6>0，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步 到目前为止，蚁群算法中挥发因子、信息素值控 制参数、启发式信息（能见度）控制参数的设置，对

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