第3期 吴一全，等：布谷鸟搜索算法研究及其应用进展 ·437· 局部极值点。文献[13]在PS0优化算法中引入 1.3CS算法的实现步骤 Levy飞行，克服了易收敛到局部最优的缺陷，取 综合CS算法上述2种更新方式，可得到CS 得了令人满意的效果。Levy飞行能较大地提高 算法的以下实现步骤： 不确定环境下的资源搜索效率。 1)初始化算法的基本参数：鸟巢数目，发现 1.2CS算法的基本模型 概率P。,搜索精度ε或最大迭代次数T,并以随 针对布谷鸟的寄巢产卵习性，CS算法假定如 机方式生成n个鸟巢的初始位置X(i=1,2,…,n), 下3个条件： 这里X=[x2,…x,d为待求解问题的维数，求 1)布谷鸟每次仅仅产一只卵，孵化时鸟巢的 解初始鸟巢位置的适应度函数值，并得到初始最 选取是随机的： 优适应度函数值； 2)在每组鸟巢中，最好的鸟巢可以被保留到 2)根据式(2)(4)更新当前鸟巢位置； 下一代； 3)求出当前全部鸟巢的适应度函数值，若在 3)可以选择的鸟巢数目一定，鸟巢主人察觉 适应度函数值上新鸟巢优于原鸟巢，则替换原鸟 布谷鸟卵的概率为P.。 巢位置； CS算法的鸟巢坐标位置与解空间中的解一 4)根据式（⑤）更新鸟巢的位置，依然采用适应 一对应，在以上3个假定基础上，CS算法利用 度函数值较好的鸟巢位置替换原鸟巢位置： Levy飞行随机行走方式和偏好随机行走方式更 5)得到当代最优的适应度函数值，且和上一 新鸟巢位置。 代最优适应度函数值比较，保留一组最佳适应度 1)Ley飞行随机行走。利用式(I)产生新解。 函数值的鸟巢位置，迭代次数加1： x1=x+a⊕L(),i=1,2,,n (1) 6)如果未满足搜索精度要求或未达到最大迭 式中：x和x分别表示第t代和第t+1代第i个 代次数，那么回到2)，反之继续： 鸟巢的位置；α表示步长控制量；⊕为点对点乘 7)得到全局最优位置。 法；n为鸟巢个数，即可行解个数；L()为Levy随 机搜索路径，且L()~(1<d≤3)，其中u表示 2布谷鸟搜索算法研究现状 由Levy飞行得到的随机步长。 CS算法自从2009年发表后就受到许多重 由于对Levy分布进行积分运算比较困难，文 视，并得到大量的研究。目前关于C$算法的研 献[l4提出了使用Mantegana算法来进行计算，即 究主要分为两个方面：算法的改进和算法的应用。 =+stepsize randn(),i=1,2....n (2) 2.1CS算法的改进 式中：randn(为满足高斯分布的随机函数：stepsize= 1)基于P.和a的改进 aS⊕(x-xe),a通常取0.01，xa为第t代最优 在CS算法中，发现概率P.和步长控制量a 鸟巢位置。S通过式(3)求得： 作为关键的两个参数，在迭代过程中通常保持不 S=·IN0,v~N0,） (3) 变。但在寻优过程中，若P。一直较大，α较小，会 式中：c,=1,B=1.5,m按式(4)计算： 缩短算法收敛时间，但是易收敛到局部最优；而 r1+B)·sin(/2) 若P。较小，α较大，则会使收敛速度变慢。因此 .={T0+/2B-29-r (4) 可对P。和α进行调整以改进CS算法。 2)偏好随机行走。仿照寄主察觉布谷鸟的卵 文献[15]使P.和α随迭代次数变化： 后将其丢弃的想法和原理。具体操作如下：得到 Pa(t)=Pamin+(Pa.max -Pa.min) (N-t)" (6) 一个满足[0,1]均匀分布的随机数r,并与发现概 率P。∈0,1]进行比较，若r>P。,则按式（⑤）得到 a(t)=amin+(amax-amin). N-t)": N (7 新解： 式中：t为当前迭代次数；W表示总迭代次数； x=x+r(x-x),i=1,2,…,n (5) Pamx、Pamin表示P。的最大值与最小值；ams、amn 式中x与表示第t代的随机解。反之，若r≤P, 表示α的最大值与最小值；m,和m2为非线性因 则保持不变，即x1=xo 子，取值大于0，用来控制P。和α的下降速率，m 通过上述2种方式所得新解均采用贪婪选择 应小于1，相反m2应大于1。实验证明了改进的 操作，即得到新解后，将新解和原解的适应度函 CS算法能减少时间并提升精度。 数值进行比较，与原解相比，如果新解较优，那么 文献[I6]按照Rechenberg原则，即将“所有变 将新解取代原解，反之保持原解不变。 异的成功比例应该保持在1/5原则”作为调整策局部极值点。文献 [13] 在 PSO 优化算法中引入 Levy 飞行，克服了易收敛到局部最优的缺陷，取 得了令人满意的效果。Levy 飞行能较大地提高 不确定环境下的资源搜索效率。 1.2 CS 算法的基本模型 针对布谷鸟的寄巢产卵习性，CS 算法假定如 下 3 个条件： 1) 布谷鸟每次仅仅产一只卵，孵化时鸟巢的 选取是随机的； 2) 在每组鸟巢中，最好的鸟巢可以被保留到 下一代； Pα 3) 可以选择的鸟巢数目一定，鸟巢主人察觉 布谷鸟卵的概率为 。 CS 算法的鸟巢坐标位置与解空间中的解一 一对应，在以上 3 个假定基础上，CS 算法利用 Levy 飞行随机行走方式和偏好随机行走方式更 新鸟巢位置。 1) Levy 飞行随机行走。利用式 (1) 产生新解。 x t+1 i = x t i +α⊕ L(λ), i = 1,2,· · ·,n (1) x t i x t+1 i t t+1 i α ⊕ n L(λ) L(λ) ∼ u −λ (1 < λ ⩽ 3) u 式中： 和 分别表示第 代和第 代第 个 鸟巢的位置； 表示步长控制量； 为点对点乘 法； 为鸟巢个数，即可行解个数； 为 Levy 随 机搜索路径，且 ，其中 表示 由 Levy 飞行得到的随机步长。 由于对 Levy 分布进行积分运算比较困难，文 献 [14] 提出了使用 Mantegana 算法来进行计算，即 x t+1 i = x t i +stepsize⊕randn(), i = 1,2,· · ·,n (2) randn() stepsize = α· S ⊕(x t i − x t best) α x t best t S 式中： 为满足高斯分布的随机函数； ， 通常取 0.01， 为第 代最优 鸟巢位置。 通过式 (3) 求得： S = u |v| 1/β , u ∼ N(0,σ2 u ), v ∼ N(0,σ2 v ) (3) 式中：σv = 1， β = 1.5，σu 按式 (4) 计算： σu = { Γ(1+β)·sin(πβ/2) Γ [ (1+β)/2 ] · β · 2 (β−1)/2 }1/β (4) [0,1] r Pα ∈ [0,1] r > Pa 2) 偏好随机行走。仿照寄主察觉布谷鸟的卵 后将其丢弃的想法和原理。具体操作如下：得到 一个满足 均匀分布的随机数 ，并与发现概 率 进行比较，若 ，则按式 (5) 得到 新解： x t+1 i = x t i +r(x t j − x t k ), i = 1,2,· · ·,n (5) x t j x t k t r ⩽ Pa x t+1 i = x t i 式中 与 表示第 代的随机解。反之，若 ， 则保持不变，即 。 通过上述 2 种方式所得新解均采用贪婪选择 操作，即得到新解后，将新解和原解的适应度函 数值进行比较，与原解相比，如果新解较优，那么 将新解取代原解，反之保持原解不变。 1.3 CS 算法的实现步骤 综合 CS 算法上述 2 种更新方式，可得到 CS 算法的以下实现步骤： n Pa ε T n Xi(i = 1,2,· · ·,n) Xi = [x1 x2,··· xd] T d 1) 初始化算法的基本参数：鸟巢数目 ，发现 概率 ，搜索精度 或最大迭代次数 ，并以随 机方式生成 个鸟巢的初始位置 ， 这里 ， 为待求解问题的维数，求 解初始鸟巢位置的适应度函数值，并得到初始最 优适应度函数值； 2) 根据式 (2)~(4) 更新当前鸟巢位置； 3) 求出当前全部鸟巢的适应度函数值，若在 适应度函数值上新鸟巢优于原鸟巢，则替换原鸟 巢位置； 4) 根据式 (5) 更新鸟巢的位置，依然采用适应 度函数值较好的鸟巢位置替换原鸟巢位置； 5) 得到当代最优的适应度函数值，且和上一 代最优适应度函数值比较，保留一组最佳适应度 函数值的鸟巢位置，迭代次数加 1； 6) 如果未满足搜索精度要求或未达到最大迭 代次数，那么回到 2)，反之继续； 7) 得到全局最优位置。 2 布谷鸟搜索算法研究现状 CS 算法自从 2009 年发表后就受到许多重 视，并得到大量的研究。目前关于 CS 算法的研 究主要分为两个方面：算法的改进和算法的应用。 2.1 CS 算法的改进 1) 基于 Pa 和 α 的改进 Pa α Pa α Pa α Pa α 在 CS 算法中，发现概率 和步长控制量 作为关键的两个参数，在迭代过程中通常保持不 变。但在寻优过程中，若 一直较大， 较小，会 缩短算法收敛时间，但是易收敛到局部最优；而 若 较小， 较大，则会使收敛速度变慢。因此 可对 和 进行调整以改进 CS 算法。 文献 [15] 使 Pa 和 α 随迭代次数变化： Pa(t) = Pa,min +(Pa,max − Pa,min)· (N −t N )m1 (6) α(t) = αmin +(αmax −αmin)· (N −t N )m2 (7) t N Pa,max Pa,min Pa αmax αmin α m1 m2 Pa α m1 m2 式中： 为当前迭代次数； 表示总迭代次数； 、 表示 的最大值与最小值； 、 表示 的最大值与最小值； 和 为非线性因 子，取值大于 0，用来控制 和 的下降速率， 应小于 1，相反 应大于 1。实验证明了改进的 CS 算法能减少时间并提升精度。 1/5 文献 [16] 按照 Rechenberg 原则，即将“所有变 异的成功比例应该保持在 原则”作为调整策 第 3 期 吴一全，等：布谷鸟搜索算法研究及其应用进展 ·437·