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