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