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