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