布谷鸟搜索算法是由剑桥大学学者Yang和拉曼工程大学Deb于2009年基于对布谷鸟寻窝寄生幼卵行为的模拟，提出的一种新的全局优化算法，即Cuckoo Search(CS)算法^[1]。由于其具有控制参数少、寻优能力强和简单易实施等特点，现已成功应用于解决函数优化问题^[2]、工程结构优化问题^[3]、TSP问题^[4]和PID控制器调整^[5]等多个领域。此外，通过改进算法参数提高算法性能也成为一个重要的研究领域。Walton对布谷鸟搜索算法的步长进行改进，增加了个体间的信息交流^[6]。Zheng在鸟窝位置选择更新方式中加入了高斯扰动项，进而提出基于高斯扰动的布谷鸟搜索算法^[7]。苏芙华等通过引入动态局部搜索技术，进一步提高了布谷鸟搜索算法的性能^[8]。针对算法在求解复杂函数时，后期收敛精度不高、迭代次数多、运算时间长等问题，本文提出一种基于函数优化的具有动态惯性权重的布谷鸟(cuckoo search with dynamic inertia weight，简称WCS)算法，通过加入动态惯性权重对鸟窝位置进行更新，有效平衡局部搜索和全局搜索之间的关系。实验结果表明，WCS算法能够有效提高算法的收敛精度，减少算法的运行时间，具有较好的优化性能。

布谷鸟算法源于对布谷鸟繁育行为的模拟，是新型有效的全局优化算法。其原理是将布谷鸟所选宿主的鸟窝映射为空间中的解，用宿主鸟巢所在位置的优劣表示解的适应度值，布谷鸟搜索和选择鸟窝的过程就是算法的搜索和优化过程^[9]。

布谷鸟算法基于3个理想规则^[1]：

规则1 每只布谷鸟每次产一个卵，并随机选择鸟巢孵化它；

规则2 在随机选择的一组鸟巢中，最好的鸟巢被保留至下一代；

规则3 可选择的寄生巢的数量是固定的，寄生巢主人发现外来鸟蛋的概率为P_a，其中0≤P_a≤1。

基于这3个理想规则，Yang等^[1]采用式(1)对下一代鸟巢位置X^(t+1)进行更新:

基本布谷鸟搜索算法，按照更新式(1)对下一代的鸟窝位置进行更新，并且计算目标函数的适应度值，如果优于上一代适应度值，则保留到下一代，否则保持原来位置不变。随机产生的数值r服从0到1均匀分布，并将其与鸟巢主人发现外来鸟蛋的概率P_a相比较，若r>P_a，则重新产生一组初始解向量，否则保持不变。

动态惯性改进策略是一种控制种群探索能力和开发能力的机制，能够有效提高算法的搜索能力，平衡局部搜索和全局搜索之间的关系。Shi和Eberhart^[12]将惯性权重引入粒子群算法，作为一种取代速度钳制操作的控制机制，通过惯性权重的调整来控制算法的局部和全局寻优能力。

动态变化惯性权重主要有以下几类：

线性递减 w的取值从较大值线性递减到一个较小的值^[13]：

非线性递减 w从较大值非线性递减到一个较小值^[14]:

模糊调整 由Eberhart和Shi(1998)采用模糊系统提出的具有动态调整特征的自适应惯性权重^[15]，但其参数较多，增加了算法的复杂度和实现难度。

随机调整 Eberhart等^[16]提出一种动态惯性权重的方法，每次迭代都随机选取高斯分布中的一个惯性权重值，较大的惯性权重和较小的惯性权重随机出现。较大的惯性权重可以避免算法在初期陷入局部最优，同时较小的惯性权重可以解决后期收敛精度不高等问题^[17]。

基于以上分析，本文选取动态惯性权重中的随机调整惯性权重对布谷鸟算法进行改进。随机调整的惯性权重服从高斯分布即：w~N(θ,σ)。较大的惯性权重和较小的惯性权重都会随机出现，使得算法能够实现局部搜索和全局搜索的平衡。随机惯性策略w的更新公式为

因此，具有动态惯性权重的布谷鸟搜索算法采用动态惯性权重中的随机调整的惯性权重改进鸟窝位置更新方式，WCS算法实现流程如下：

1)确定目标函数f(X)，设置优化函数的定义域[-L,L]，维度d，发现概率P_a和种群数量n。初始化种群，随机并产生d维向量，即X=(x₁,x₂,…,x_d)T，n个鸟窝的初始位置为：X_i(i=1,2,…,n)；

2)计算每个鸟窝的目标函数值，并记录当前鸟窝位置的最优解；

3)保留上代最优鸟窝位置，产生随机动态惯性权重w~N(θ,σ)，采用加入动态惯性权重策略的位置更新公式(2)对一代鸟窝位置进行更新；

5)用一个随机数r，作为鸟窝主人发现外来鸟蛋的可能性，与发现概率P_a进行比较，若r≤ P_a，则记录当前最优值；若r>P_a，则返回2)，随机改变鸟窝位置，得到一组新的鸟窝位置；

6)输出全局最优值。

本文参考文献[18]对动态惯性权重范围的划分进行取值，使用表 2中函数f₁和函数f₂观察不同惯性权重的变化范围对优化效果的影响。参数设置：种群大小为25，每次运行最大迭代次数为50，对每个函数优化50次。实验结果如表 1所示。表中，1表示惯性权重范围0~0.2，2表示0.2~0.9，3表示0.9~1.2。实验结果表明，当取值在0.9~1.2时，算法找到最优结果的次数较少；当取值在0.2~0.9之间时，算法能够找到最优结果，但是找到最优解的概率不稳定；当取值在0~0.2时，算法能够找到最优结果，准确率较高。因此，随机调整的惯性权重服从高斯分布，且θ取值为0~0.2，σ取值足够小以确保w不会显著大于1。

算法的时间复杂性可以从侧面反映算法收敛速度的快慢，如果一个算法收敛，但需要无穷的迭代时间，那么这个算法不具有有效性。基本布谷鸟算法输入的种群规模为N，求解目标函数为f(x),最大迭代次数为n，根据基本布谷鸟算法的流程，假设产生均匀分布随机数的时间为ξ₁，下一代鸟窝位置由上代鸟窝位置和Levy飞行机制得到，计算目标函数的时间复杂度为O(N(ξ₁n+ f(n)))= O(n+f(n))，更新式(1)产生一组新解的时间为ξ₂，新的位置与上代位置进行比较的执行时间为ξ₃，若新位置较好，替换上代位置的执行时间为ξ₄，在第1个新解产生阶段，时间复杂度为O(N(ξ₂n+f(n)+ξ₃+ξ₄n) )=O(n+ f(n))。在第2个新解阶段，生成新解的执行时间为ξ₅，时间复杂度为O(N(ξ₅n+f(n)+ξ₃+ξ₄n)=O(n+f(n))。记录最优鸟巢位置的时间复杂度为O(N(ξ₃+ξ₄n) =O(n)，则对于每一代找到最优解的总的时间复杂度为T(n)=3O(n+f(n))+O(n)=O(n+ f (n))^[19]。

同理，分析改进布谷鸟算法的流程，位置更新公式中加入动态惯性权重，设产生动态惯性权重w的执行时间为ξ，种群数量、目标函数和最大迭代次数不变。在第1个新解阶段，时间复杂度为O(N(ξ₁n+ξ₂n+f(n)+ξ₃+ξ₄n))=O(n+ f(n))，第2个新解阶段，时间复杂度为O(N(ξ₁n+ξ₅n+f(n)+ξ₃+ξ₄n))= O(n+f(n))。因此，更新下一代鸟窝位置的最终时间复杂度不变，仍为T(n)=O(n+f(n))，与基本布谷鸟算法一致，改进后的算法没有增加时间复杂度。

标准布谷鸟算法是一种随机算法，文献[20]通过建立Markov链模型，利用随机算法收敛的条件证明了标准CS算法的收敛性，为CS算法全局收敛提供了理论依据。

文献[21]和[22]利用差分方程分别对蝙蝠算法和粒子群算法的收敛性进行了深入分析，本文采取同样的方法，通过建立差分方程对改进的布谷鸟算法进行收敛性分析。改进布谷鸟算法采用式(2)进行下一代鸟窝位置更新，式(2)表示第i个鸟巢在t+1时刻的位置，α为步长控制量，Levy(λ)是随机搜索步长，即

λ²+(1+w－r₁)λ+w－r₁=0

(a)当△=(w-r₁-1)²=0时，即w-r₁-1=0。λ₁和λ₂为特征方程的2个根，若λ₁和λ₂为实数，‖λ₁‖、‖λ₂‖分别表示λ₁和λ₂的绝对值，若为复数，则表示λ₁和λ₂的模值。

由△=0得：λ₁=λ₂=-1。此时X^(t)=(A₀+A₁t)λ^t，A₀、A₁为待定系数，计算可得：

(b)当△>0时，此时X^(t)=A₀+A₁λ₁^t+ A₂λ₂^t，A₀、A₁和A₂为待定系数,计算得到：

当t→∞时，有极限且趋向于有限值，表示迭代收敛，由此可知，若上面2种情况中X^(t)收敛，则需满足条件‖λ₁‖<1,‖λ₂‖<1^[19]。当max(‖λ₁‖,‖λ₂‖)=1,则有：

因此，当△=0时，收敛区域为w-r₁-1=0；当△>0时，收敛区域需要满足： -1<r₁-w<1。综合上面2种情况，收敛区域为-1≤r₁-w<1。

为评估WCS算法的性能，采用5个典型的测试函数进行验证。运行环境：CPU为B940@2.00 GHz，内存2 GB，Matlab R2013a编程环境。其中，函数f₁~f₅的最优值分别为1、3 600、0、0和-3，测试函数f₁~f₅的数学表达式和自变量的取值范围如下:

算法参数设置为：种群规模n=25，发现概率P_a=0.25。惯性权重从高斯分布中取值并随机调整。每个函数分别进行30次独立仿真实验，平均时间为算法找到最优解所用时间的平均值，其单位为秒。平均迭代次数为算法收敛到最优解的代数的平均值。进化代数为算法找到最优解的最大迭代次数的最小值。准确率为算法找到最优解的次数与运行总次数的百分比。WCS算法与CS算法比较，如图 1~6所示，仿真运算结果如表 2所示。

图 1 f1图像Fig. 1 Image of f1

图选项

1)Schaffer函数

图 2 f1算法收敛状态对比图Fig. 2 Convergence state of CS and WCS on f1

图选项

2)Needle-in-haystack函数

图 3 f2算法收敛对比图Fig. 3 Convergence state of CS and WCS on f2

图选项

图 4 f3算法收敛对比图Fig. 4 Convergence state of CS and WCS on f3

图选项

图 5 f4算法收敛对比图Fig. 5 Convergence state of CS and WCS on f4

图选项

图 6 f5算法收敛对比图Fig. 6 Convergence state of CS and WCS on f5

图选项

以上函数收敛图表明，改进后的算法和基本算法相比，迭代次数更少，收敛速度更快，收敛精度更高，具有更好的优化性能。

表 2运算结果表明，对于5个测试函数，改进后的算法找到最优解的次数更多，时间更短，相比于基本算法找到最优解的准确率更高。当基本CS算法面对较为复杂的函数优化问题时，如f₁，增加迭代次数为2 500，基本算法运行时间是改进后算法的58.7倍，收敛到最优解的迭代次数是改进后算法的2.4倍，准确率只有改进后算法的83%。因此，改进后的算法可以更好地解决函数优化问题。

用以上函数对WCS算法与CS算法、粒子群算法(PSO)、蚁群算法(ACO)、引力搜索算法(GSA)和蝙蝠算法(BA)进行性能测试，运算结果如表 3所示。

其中，为了更加公平地测试算法性能，每个算法独立运行50次，种群数量都为50，迭代次数1 000。CS算法和WCS算法参数设置为：发现概率P_a=0.25。PSO参数设置为w=0.729，c₁=c₂=1.494 45^[23] 。蚁群算法参数设置为：α=β=1，r=0.5，ρ=0.7，Q=1^[24]。引力搜索算法参数设置为：T=1 000，G₀=100，α=50。蝙蝠算法参数设置为：A_i=0.25，r_i=0.5，α=r=0.9^[25]。

实验结果表明,对于函数f₁~f₅，相比于其他算法，WCS算法能够很快找到最优解。蚁群算法表现次之，对于f₁~f₄可以收敛到最优解，但对f₅求解精度不够。CS算法求解的稳定性不高。对于函数f₁和f₂，WCS算法和蚁群算法都有很好的收敛性，能快速找到最优解；对于函数f₃，WCS算法和蚁群算法性能明显优于其他算法；对于函数f₄，WCS算法和蚁群算法能够收敛到最优解；对于函数f₅，CS算法、WCS算法和新型蝙蝠算法优化性能明显优于其他算法。

算法参数的选择可能对算法性能产生重要影响，本文重点讨论种群大小对算法性能的影响。种群规模由25增加至100，最大迭代次数为300，其他参数设置不变，每个函数独立运行50次，1、2和3分别表示惯性权重的取值范围0~0.2、0.2~0.9和0.9~1.2，4表示基本布谷鸟算法。在n为25和100两种情况下，函数f₁~f₃找到最优解的达优率如表 4所示。

由表 4可得，种群规模增大后，CS算法优化性能基本不变，函数2在种群规模增大后的达优率甚至出现减少的情况；惯性权重范围在0.2~0.9和0.9~1.2两个区间的算法优化性能并没有得到明显改善，最佳惯性权重范围仍然是0~0.2，说明种群规模的改变，对算法收敛效果的影响不显著。

针对布谷鸟算法在求解函数最优化问题中存在的收敛度不高、收敛速度慢等问题，本文提出了一种改进方法：通过引入动态惯性权重改进鸟窝位置的更新方式，对动态惯性权重的取值范围进行分析，找到求解最优的惯性权重取值范围。并利用差分方程对改进算法进行了收敛性分析。研究发现改进后的算法通过动态惯性权重控制种群探索能力和开发能力，能够有效平衡局部搜索能力和全局搜索能力之间的关系。仿真实验结果表明，与基本布谷鸟算法相比，WCS算法可以显著减少迭代次数，缩短运行时间；与其他算法相比，WCS算法也有较强的收敛性和鲁棒性。最后，对算法参数进行了讨论，当种群规模增大后，仍需惯性权重的调节，且惯性权重的选择范围不变，进一步说明，加入动态惯性权重后的算法具有更好的优化性能。