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