多策略调和的布谷鸟搜索算法

彭 虎，李源汉，邓长寿，吴志健

（1.九江学院 计算机与大数据科学学院，江西 九江 332005；2.武汉大学 计算机学院，武汉 430072）

0 概述

群智能算法是模拟自然界生物群体行为而设计的算法，能有效解决现实世界中的复杂问题。随着学者们对群智能算法研究的深入，在其基础上提出了蚁群优化（Ant Colony Optimization，ACO）［1］、粒子群优化（Particle Swarm Optimization，PSO）［2］、人工蜂群（Artificial Bee Colony，ABC）［3］、萤火虫算法（Firefly Algorithm，FA）［4］、布谷鸟搜索（Cuckoo Search，CS）［5］等多种优化算法。这些算法不仅能够解决复杂函数优化问题，而且适用于控制工程［6］、生产调度［7］、图像处理［8］等领域。

CS 算法是受布谷鸟的寄生育雏行为启发而提出的，与其他群智能算法相比，一方面具有参数少、运算简单、寻优能力强等优点，另一方面存在勘探能力与开采能力不平衡以及容易陷入局部最优解的缺陷。近年来，国内外学者们提出了很多新的CS 改进算法。RAKHSHANI 等［9］提出捕捉和漂移布谷鸟搜索算法（SDCS），利用2 种学习模式，一种倾向于增强全局搜索，另一种倾向于增强局部搜索，同时引入新的交叉和变异搜索算子，提高SDCS 的搜索能力。PENG 等［10］提出一种新的高斯布谷鸟搜索算法（GBCS），以随机的方式选择Lévy 分布和高斯分布，防止算法的过早收敛以及增强算法的搜索能力。PENG 等［11］还提出一种多策略串行布谷鸟搜索算法（MSSCS），通过对布谷鸟寻巢行为、驱逐行为和乞求行为的观察，设计3 种新的学习策略以及一种多策略串行框架来提高算法的性能。LI等［12］提出一种自适应参数方法的改进布谷鸟算法（SACS），将2 种新的变异规则通过线性递减概率规则进行组合以平衡算法的勘探与开发，再根据两个新参数的相对成功率，引入自适应参数作为均匀随机值，以增强种群的多样性。刘景森等［13］提出一种具有动态步长和发现概率的布谷鸟搜索算法（DCS），通过引入步长调整因子动态约束Lévy 飞行移动步长，还使用具有均匀分布和F 分布特性的随机惯性权重增强算法的多样性。周诗源等［14］提出一种基于布谷鸟搜索优化算法的多文档摘要方法，将经过数据预处理后的多文档句子信息作为CS 算法的输入，再基于多目标函数生成包含原始文档重要信息的句子以组成最终的摘要。向庭立等［15］提出一种基于布谷鸟搜索的覆盖优化策略，将混合传感器节点随机部署在目标区域，利用CS 算法初步确定移动传感器节点的候选目标位置，通过位置优化方案得到移动传感器节点的最佳目标位置以完成覆盖优化。AGARWAL 等［16］提出一种基于布谷鸟搜索算法的任务调度方法，有助于在可用的虚拟机之间有效地分配任务，并保持总体响应时间最小。

通过分析CS 算法Lévy 飞行和随机游走的特性，发现在迭代过程中CS 算法存在勘探能力与开采能力不平衡以及易陷入局部最优的缺陷。为解决此问题，本文提出一种多策略调和的布谷鸟搜索（Multi-Strategy Reconciled Cuckoo Search，MSRCS）算法。该算法设计基于自适应步长和改进解更新方法的调和策略，并利用线性递减概率规则对调和策略进行选择，实现多策略调和以平衡算法的勘探能力与开采能力，并在不同迭代过程中调节全局搜索和局部搜索。

1 布谷鸟搜索算法

2009 年，YANG 等［5］受布谷鸟的孵化寄生行为启发，提出布谷鸟搜索算法。在自然界中，布谷鸟寻找适合产卵的巢穴的行为是随机的。因此，为了模拟布谷鸟找到巢穴的方式，设置以下简化规则：

1）每只布谷鸟一次只下一颗蛋，并随机选择一个鸟巢下蛋。

2）在随机选择的鸟巢中，最好的鸟巢将被保存到下一代。

3）鸟巢的数量是恒定的。鸟巢的主人抛弃外来蛋的概率为pa∈（0，1）。

CS 算法中每一个鸟巢代表问题的一个解，携带着鸟蛋的布谷鸟会通过Lévy 飞行随机地移动到一个寄主鸟的巢中产卵。通过评价函数，对替换后的巢进行评价。因此，许多更好的解将被发现和更新。同时布谷鸟的蛋如果被寄主鸟发现，则寄主鸟抛弃布谷鸟的蛋以及放弃自己的蛋和巢，并再建新巢。

原始的CS算法主要包括Lévy飞行和随机游走2种重要策略。每一代布谷鸟都通过Lévy 飞行寻找更好的巢来产卵。因此，布谷鸟的移动由Lévy飞行主导，即：

其中：μ和ν是服从均匀分布的随机数；β为1.5。φ的表示方法如下：

布谷鸟通过式（1）的Lévy 飞行寻找到新的寄主鸟巢并将蛋放置于巢后，若寄主鸟发现布谷鸟的蛋，则会按概率pa抛弃部分巢，并使用随机游走策略新建与被抛弃巢数量相等的新巢，公式如下：

CS 算法流程如下：

2 多策略调和的CS 算法

2.1 自适应步长

自适应步长是提高CS 搜索效率的有效方法。张永韡等［17］根据布谷鸟每次迭代成功更新解的改善率调整步长大小，提出动态适应布谷鸟搜索算法（DACS）。若改善率较大，说明搜索空间相对单调，算法找到更优解的概率较高，故适当增大步长增加种群的探索性和搜索范围；若改善率较小，说明搜索空间相对复杂，找到更优解的概率较低，以适当减小步长来提高算法局部开发性。

Lévy 飞行是原始CS 算法中一种重要的随机搜索策略，以随机的小步长或偶然的大步长控制布谷鸟移动。在原始CS 算法迭代过程的前期，Lévy 飞行搜索范围较小，效益较低，迭代次数增加从而导致算法收敛性较差。在迭代过程的中后期，算法逐渐靠近最优解，全局搜索减弱并逐渐转至局部搜索，易使算法陷入局部极值。

基于以上分析，本文提出一种新的自适应步长策略以提高CS 算法的搜索效率，即自适应步长随迭代次数的增加而减小。在迭代前期，MSRCS 的大步长扩大了其搜索范围，提高算法的全局搜索能力，有利于算法更快找到更优解，加快收敛速度；在迭代后期，小步长有利于算法的局部搜索。步长的规律变化对布谷鸟的搜索起引导作用，即在整体上从全局搜索逐渐过渡到局部搜索。该策略主要是由线性递减的自适应步长控制因子α0决定，公式如下：

其中：η是控制步长变化范围的调和因子，并决定步长的初值。根据余弦函数在范围内呈递减变化的特性，将步长与迭代次数进行关联，使步长也随着迭代次数的增加而减小。自适应α0为近似一条直线的曲线，为整个搜索过程提供了轻微的缓冲作用，α0的取值范围为［0.00，0.25］。

2.2 解更新方法

由于原始CS 算法具有参数少、操作简单的特点，因此单策略CS 算法的可操作性有限，布谷鸟的行动相似，且对于求解复杂的高维优化问题，若一只布谷鸟陷入局部极值，则无法靠邻域内相同情况的其他布谷鸟跳出局部极值。GAO 等［18］为了解决这些问题，提出一种多策略自适应布谷鸟算法（MSACS），采用自适应参数控制5 种新的搜索策略进行相互协作，以提高算法的搜索效率。由此证明多策略CS 算法能够针对迭代过程的不同阶段采用不同策略，相比灵活性较差的单策略，不仅能增加算法的多样性，还能增强算法应对不同场景的搜索能力。LIU 等［19］对BSO 算法的多策略改进也取得了显著成效。因此，本文提出CS-current、CS-best和CS-rand 3 种不同的解更新方法。

CS-current 解更新方法以布谷鸟自身当前位置为中心，在其邻域内搜索潜在更优解，并加入Xtbest控制寻优方向，防止布谷鸟在其他方向上进行无效的搜索和评价次数的浪费。如图1 所示，黑点表示布谷鸟个体，虚线表示布谷鸟的邻域范围，此时布谷鸟个体分布较分散，每个个体邻域内都可能存在更优解，布谷鸟以自身为学习目标，尝试在自身邻域内搜索更优解，增强局部搜索能力有助于寻找解周围的潜在更优解。CS-current 解更新方法的表达式如下：

图1 CS-current 解更新方法示意图Fig.1 Schematic diagram of the solution-update method of CS-current

CS-best 解更新方法以当前最优解为引导，使当前布谷鸟向着当前最优解的方向移动。彭虎等［20］在ELDDE 算法中设计的精英区域学习策略，通过对精英个体的学习显著提高了算法性能。如图2 所示，灰点表示当代最优解虚线箭头表示布谷鸟的移动方向，此时布谷鸟种群密度较大，且大部分布谷鸟个体集中在周围，但仍有少部分分散在密集种群外，在密集种群外的布谷鸟以为学习目标，向其所在种群密度大的方向移动，有利于加快算法的收敛速度。CS-best 解更新方法的表达式如下：

图2 CS-best 解更新方法示意图Fig.2 Schematic diagram of the solution-update method of CS-best

CS-rand 解更新方法通过学习两个随机个体各维度的不同信息，生成一个新的随机个体。如图3所示，白点表示随机选取的两个布谷鸟个体，灰点表示以两个随机个体为学习目标产生的新个体，新个体在密集种群范围之外，且有可能优于当代最优解，有助于算法跳出局部极值以寻找到更优解。CS-rand 解更新方法的表达式如下：

图3 CS-rand 解更新方法示意图Fig.3 Schematic diagram of the solution-update method of CS-rand

基于以上分析发现，3 种新的解更新方法能够从多方面寻找算法更优解，根据算法在迭代过程中的缺陷使用不同的解更新方法在搜索空间中进行寻优，不仅能在迭代过程中加快收敛速度，而且有效克服算法收敛停滞，提高了算法跳出局部极值的能力。

2.3 多策略调和

为适应算法在不同阶段的需求，使策略的选择更加有效，对自适应步长和3 种改进的解更新方法组成的调和策略进行选择，以调和算法的勘探与开采。

在SACS［8］算法中的线性递减概率规则(1-t/G)利用一个随机值与该规则产生的调和值进行比较，使算法能够在不同阶段对策略进行自适应选择。相比于原始CS 算法，该规则使用动态变化的值有效地从前期向后期自适应过渡。在MSRCS 算法中，使用了线性递减规则作为多策略调和的框架，对调和策略进行概率选择。在迭代前期，调和值较大，选择调和策略1 的概率也更大，但随着迭代次数的增加，调和值逐渐减小，则概率逐渐向调和策略2 偏移。当t=G/2 时，选择两个调和策略的概率相等。之后选择调和策略2 的概率逐渐增加。

调和策略1 将自适应步长和CS-current 结合，并设置调和因子p1=0.8 来调节选择概率。

调和策略1 的流程如下：

1.If r

2.使用自适应Lévy 飞行更新个体；

3.Else

4.使用CS-current 方法更新个体；

在迭代前期，算法的最优解不明显，且解较为分散，适度使用CS-current 有利于算法更快地找到自身邻域内的潜在最优解，在迭代前期对算法的勘探与开采起调和作用。

调和策略2 将自适应步长和CS-best、CS-rand 结合。自适应步长和解更新方法的概率调和因子p2=0.5，对2 种解更新方法的概率调和因子为p1。

调和策略2 的流程如下：

1.If r

2.使用自适应Lévy 飞行更新个体；

3.Else

4.If r

5.使用CS-best 方法更新个体；

6.Else

7.使用CS-rand 方法更新个体；

8.End

9.End

在迭代中后期，自适应步长逐渐减小，全局搜索逐渐过渡至局部搜索，解向当前最优解逐步收敛。若目标函数值与全局最优解近似，自适应的小步长或者CS-best 则有利于向最优解收敛。若目标函数值与全局最优解相差较大，或陷入局部极值，则基于随机思想，算法有小概率使用CS-rand 尝试寻找更优解或尝试跳出局部极值，且适当增大选择CS-best 和CS-rand 的概率，在迭代后期使算法的收敛性、多样性和解的精度得以提升。

调和策略的选择建立在线性递减概率规则的框架下，根据迭代次数动态更新选择概率，达到调和策略之间从前期向后期的自适应过渡，以及调和算法的勘探和开采能力。

MSRCS 算法的流程如下：

1.初始化个体Xi(i=1，2，…，n)，计算其适应度值；

2.While t

3.If r<(1 −t/G)

4.使用调和策略1 更新个体Xi；

5.Else

6.使用调和策略2 更新个体Xi；

7.End if

9.根据抛弃概率pa和随机游走式（5）更新个体；

11.End While

2.4 算法复杂度

为证明MSRCS 不会增加CS 的时间复杂度，对CS 和MSRCS 进行复杂度分析。假设在CS 流程中，初始化阶段生成解的时间为t1，计算d维问题的目标函数时间为f(d)，种群规模为n，则整个初始化阶段的时间复杂度为O(n(t1d+f(d)))≈O(d+f(d))。迭代阶段采用式（1）计算Lévy 飞行生成新解的时间为t2，比较产生的新解与旧解的时间为t3，新解替换旧解的时间为t4，且记录该过程最优解的时间为t5，则Lévy飞行阶段的时间复杂度为O(n(t2d+f(d)+t3+t4d+t5d))≈O(d+f(d))。采用式（5）计算随机游走生成新解的时间为t6，比较新解与旧解，替换旧解及记录最优解的时间与Lévy 飞行阶段相同，随机游走阶段的时间复杂度为O(n(t2d+f(d)+t3+t4d+t5d))≈O(d+f(d))。最后比较当代最优解与当前最优解的时间为t7，替换当前最优解的时间为t8，更新当前最优解的时间复杂度为O(n(t7+t8d))≈O(d)。假设最大迭代次数为G，CS 算法总时间复杂度为T(n)=G∙(3O(n(d+f(d)))+O(d))≈O(G∙n(d+f(d)))。

MSRCS 仅在Lévy 飞行阶段进行改进，其他部分与CS 相同。假设调和策略1 产生新解的时间为t9，调和策略2 产生新解的时间为t10，该阶段的时间复杂度为O(n(t9d+f(d)+t3+t4d+t5d)) 或O(n(t10d+f(d)+t3+t4d+t5d))。MSRCS总的时间复杂 度为T(n)=O(G∙n(t1d+f(d)))+O(G∙pa∙n(t9d+f(d)+t3+t4d+t5d))+O(G∙(1-pa)∙n(t10d+f(d)+t3+t4d+t5d)+t8d))≈O(G∙n(d+f(d)))。

由此可见，在各参数相同的情况下，MSRCS 与CS 的算法时间复杂度一致。同时MSRCS 未使用额外的存储空间存放数据，空间复杂度也相同。因此，MSRCS 的改进并未增加算法的复杂度。

3 实验与结果分析

3.1 实验设置

为了验证MSRCS 的性能，在广泛使用的CEC2013［21］测试集上进行实验。CEC2013 包含28个测试函数，其中f1～f5为单峰函数，f6～f20为多峰函数，f21～f28为组合函数，函数的求解约束范围为[-100,100]d。为了探究MSRCS 的准确性和收敛性，将其与原始CS 及其7 种改进算法进行对比分析，这7 种CS 改进算法分别为ACS［22］、DACS［17］、SACS［8］、GBCS［10］、GCS［23］、NACS［24］和SDCS［9］，表1 给出了各算法的具体参数设置，其中CS、ACS、DACS、SACS、GBCS、GCS、NACS 和SDCS 参数遵循相应文献中的设置。通过显著性水平为0.05 的Wilcoxon 秩和检验与Friedman 检验对实验结果进行统计分析。Wilcoxon 秩和检验通过将两组的值排秩次，比较两组的秩次总和来判断是否存在统计学差异。Friedman 检验利用秩分析多组相关样本之间是否存在统计学差异。MSRCS 及其他比较算法在Matlab R2016a 上编程实现。MSRCS 的Matlab 代码可从https：//whuph.github.io/index.html 下载。

表1 算法参数设置Table 1 Parameter setting of algorithms

为了保证实验的公平性，设置种群数量n为20、问题维度d为30、发现概率pa为0.25、总评价次数Fmax为1E6、最大迭代次数Gmax为25 000。步长控制因子通过对比不同η值的实验结果，选出其中结果最好的η值作为最终的η值。每个测试函数在相同环境下运行30次，并记录下其平均误差值与标准误差值。

3.2 与原始CS 及其改进算法的比较

将MSRCS 与原始CS 以及7 种CS 改进算法进行性能对比。表2 和表3 给出了d=30 时MSRCS 与其他8 种CS 算法在CEC2013 测试函数上的实验结果，其中，加粗的字体表示最好结果，Avg 和Std 分别表示平均误差值和标准误差值，rank 表示Friedman检验的平均排名结果，Wilcoxon 秩和检验结果中的“+”表示对比算法结果优于MSRCS，“−”表示对比算法结果差于MSRCS，“≈”表示对比算法和MSRCS 结果相差不大。

表2 d=30 时CS、ACS、DACS、SACS、MSRCS 算法的CEC2013 测试函数实验结果Table 2 Experimental results of CEC2013 test functions for CS，ACS，DACS，SACS，MSRCS algorithms when d=30

续表

表3 d=30 时GBCS、GCS、NACS、SDCS、MSRCS 算法的CEC2013 测试函数实验结果Table 3 Experimental results of CEC2013 test functions of GBCS，GCS，NACS，SDCS，MSRCS algorithms when d=30

从表2可以看出，MSRCS 在f4、f7、f8、f9、f12、f15、f16、f18、f20、f23、f24、f25上有较 好的结果。在单峰函数中，MSRCS 在f4上效果明显优于其他算法，在f2上仅劣于DACS，在f1、f3上各算法的性能趋于一致。在多峰函数f7、f8、f9、f12、f15、f16、f18、f20上的结果优于其他算法，在f19上仅劣于SACS。在组合函数f23、f24、f25上MSRCS 的结果较好。通过表2 和表3 底部的Friedman 检验与Wilcoxon 秩和检验的结果可以看出，MSRCS 在28 个测试函数上的平均排名为3.321 4，排名第一，相比于GBCS 有12 个函数更优，相比于其他算法至少有14 个函数更优。可见，MSRCS 在处理不同类型的问题时均具有更好的稳定性和收敛性。

为了更直观地显示表2 和表3 结果的排名情况，整理总结每个函数的平均误差值（最小化问题）排名，绘制了基于排名统计情况的堆叠直方图。如图4所示，每个排名用一个彩色块表示，从第一到第五分别为棕色、粉色、橘色、蓝色和绿色，含棕色块越多的算法性能越强，反之绿色块越多算法性能越差，彩色效果见《计算机工程》官网HTML 版。图4（a）表示CS、ACS、DACS、SACS 和MSRCS的排名情况，图4（b）表示GBCS、GCS、NACS、SDCS 和MSRCS 的排名情况。由图4 可知，排名第一的棕色块在MSRCS 中的比例最多，说明MSRCS 与其他算法相比表现最佳。

图4 在CEC2013 测试函数上各算法的排名堆叠直方图Fig.4 Stacked histograms of the ranks of the algorithms on CEC2013 test function

为进一步说明MSRCS 的收敛能力和寻优精度，选取原始CS 以及4 种具有代表性的CS 改进算法，分别从CEC2013 测试集的单峰函数、多峰函数和组合函数中挑选具有代表性的f5、f9、f13、f20、f24、f25函数，其中f5为单峰函数，f9、f13、f20为多峰函数，f24、f25为组合函数，并在图5 中绘制了其收敛曲线。从图5（a）中可以看出，MSRCS 在单峰函数f5的整个迭代过程中收敛速度相比于其他算法是最快的，在18 000 次迭代时已经收敛到了最优值。这证明了MSRCS 中的CS-best 解更新方法在单峰函数问题上有利于算法更快地 收敛于 最优解。在f13、f24、f25函数中，CS、ACS、DACS、SACS、GCS 都存在着陷入局部极值从而停止收敛的情况，在其他算法都陷入局部极值时，MSRCS 跳出局部最优达到了更高的精度值，说明MSRCS 算法中的CS-rand 解更新方法尝试跳出局部极值并寻找更优解。对于f9、f20函数，MSRCS 优势较为明显，由于其根据概率选择不同调和策略来平衡勘探与开采，因此收敛曲线并非阶段性断层而是呈逐步寻优状，以靠近全局最优解。根据上述分析，MSRCS 的调和策略在各种类型的测试函数上均具有较好的收敛速度、较强的寻优能力以及跳出局部极值的能力。

图5 CS、ACS、DACS、SACS、GCS、MSRCS 算法在部分测试函数上的收敛曲线Fig.5 Convergence curves of CS，ACS，DACS，SACS，GCS，MSRCS algorithms on the sectional test functions

3.3 多策略调和的有效性分析

为了验证多策略调和的有效性，本文提出了MSRCS-1、MSRCS-2、MSRCS-3 这3 种MSRCS 改进算法，分别为只使用自适应步长、不使用线性递减规则（将迭代过程分为前期和后期）以及单独使用调和策略公式，测试结果如表4 所示，实验参数设置与3.1 节一致。从表4可以看出：在Wilcoxon检验结果中，由于MSRCS分别有12、14、19 个函数比MSRCS-1、MSRCS-2 和MSRCS-3 更好，因此MSRCS 中的调和策略应用在测试函数上的效果相比于其他单独使用策略的改进算法更好；在Friedman 检验的平均排名（rank）中，数据显示MSRCS为1.982 1，MSRCS-1为2.303 6，MSRCS-2 为2.678 6，MSRCS-3 为3.035 7。可见，在多策略调和的作用下MSRCS 效果最佳。

表4 d=30 时MSRCS 算法在CEC2013 测试函数上单独使用不同策略的实验结果Table 4 Experimental results of MSRCS algorithm by using different strategy on the CEC2013 test functions when d=30

在此基础上，进一步对多策略调和MSRCS 的收敛性及稳定性进行验证。图6 给出了MSRCS 和3 种改进算法在函数f11、f12、f13、f14上的收敛曲线图。由图6 可知，含多策略调和的MSRCS 在解的精度方面要优于其他改进算法，且在其他改进算法都陷入局部极值时能够达到更高的精度，由此证明了MSRCS 的多策略调和跳出局部极值和持续寻优的能力较好。此外，还证明了多策略调和相比于其他改进算法的单策略更加有效。

图6 MSRCS-1、MSRCS-2、MSRCS-3、MSRCS 算法在f11、f12、f13、f14函数上的收敛曲线Fig.6 Convergence curves of MSRCS-1，MSRCS-2，MSRCS-3，MSRCS algorithms on f11，f12，f13，f14 functions

3.4 与群智能优化算法的比较

差分进化（Differential Evolution，DE）算法［25］、人工蜂群（ABC）算法［3］和萤火虫算法（FA）［4］是被广泛研究与使用的群智能优化算法。为进一步验证MSRCS的性能，选取DE、ABC 和FA 的改进算法进行比较，分别为CUDE［26］、MEABC［27］和NSRaFA［28］。

鉴于实验的公平性，对这些算法设置种群数量n为20、问题维度d为30 及评价次数Fmax为1E6，且每个测试函数独立运行30 次，CUDE、MEABC 和NSRaFA 参数遵循相应文献中的设置，MSRCS 参数设置与表1 一致。CEC2013 测试集的实验结果如表5 所示，其中加粗的字体表示最好结果。从表5 可以看出：MSRCS 有11 个函数优于其他算法；对于单峰函数f2、f3、f4，CUDE相比于其他3 种算法具有更好的结果，MSRCS 在f1上找 到了最优值；在多峰函数f7、f8、f10、f12、f13、f16、f18上MSRCS 有相对优势，说明其在解决多峰函数问题时有着比其他算法更好的效果；MEABC 在组合函数f21、f22、f26、f28上的结果较好；在Wilcoxon 值和检验结果中，MSRCS 相比于其他3 种改进算法，至少有12 个函数有更优结果。可见，MSRCS 在解决单峰和多峰问题时相对于其他算法具有更强的寻优能力。

表5 d=30 时CUDE、MEABC、NSRaFA、MSRCS 算法在CEC2013 测试函数上的实验结果Table 5 Experimental results of CUDE，MEABC，NSRaFA，MSRCS algorithms on the CEC2013 test functions when d=30

续表

图7 给出了CUDE、MEABC、NSRaFA 和MSRCS在f1、f5、f6、f7、f10、f28函数上的收敛曲线图，其中包含单峰函数、多峰函数以及组合函数。

图7 CUDE、MEABC、NSRaFA、MSRCS 算法在f1、f5、f6、f7、f10、f28函数上的收敛曲线Fig.7 Convergence curves of CUDE，MEABC，NSRaFA，MSRCS algorithms on f1，f5，f6，f7，f10，f28 functions

从图7 可以看出，在f1收敛图中，MSRCS 前期寻找到的最优解与CUDE 相差不大，但是在后期MSRCS 寻找到了比CUDE 更优的最优解，由此可见MSRCS 中的CS-rand 解更新方法跳出局部极值到达了更高的精度。MSRCS 除了在解的精度方面较其他改进算法更优外，在整个迭代过程中的收敛速度也相比于其他算法更快。综上所述，MSRCS 相比于其他算法有着相对更好的收敛能力、寻优能力以及跳出局部极值的能力。

3.5 自适应参数分析

布谷鸟步长控制因子的大小决定其搜索范围。步长控制因子越大，搜索范围越广，算法的全局搜索能力和种群多样性增强；反之，步长越小，算法的局部搜索能力和收敛性增强。在改进的自适应步长式（6）中，调和因子η控制布谷鸟的搜索范围大小，因此η的大小决定步长的变化范围。

为了测试自适应步长对MSRCS 性能的提升效果，本文对参数η进行基于CEC2013 测试集的Friedman 检验并筛选出效果最好的η值。实验选择无自适应、η=0.3、η=0.5 和η=0.7 这4 种情况，得 到MSRCS 在CEC2013 测试集的28 个函数中的平均排名结果如表6 所示。从表6 可以看出，无自适应的排名为3.160 7、η=0.3 时的排名为2.625 0、η=0.5 时的排名为1.964 3、η=0.7 时的排名为2.250 0。由于当η=0.5 时对MSRCS 的性能提升最明显，因此选取η=0.5，自适应步长的变化范围为［0.00，0.25］。

表6 不同η 值的MSRCS 平均排名Table 6 Average rank of MSRCS with the different η value

3.6 MSRCS 计算时间分析

根据MSRCS 算法流程可以看出，MSRCS 仅改变了算法对策略的选择机制，有概率选择新的解更新方法代替Lévy 飞行，减少了对Lévy 飞行随机步长的计算。使用单一的Lévy 飞行成效有限，对于平衡算法的勘探与开采，多策略调和对每个时期的策略选择相对更加有效。

MSRCS 和CS 在不同维度下计算CEC2013 测试集上28 个测试函数的运行时间，如表7 所示。从表7可以看出，无论是在问题维度d为30、50 或100 时，CS 和MSRCS 的运行时间并无显著差异。由此再次验证了CS 和MSRCS 的复杂度分析，MSRCS 和CS在计算复杂度上并无显著差异。

表7 CS和MSRCS算法在CEC2013测试集上的运行时间Table 7 Runtime of CS and MSRCS algorithms on CEC2013 test set 103 s

4 结束语

本文提出一种多策略调和的布谷鸟搜索（MSRCS）算法，在多策略框架下根据迭代阶段的不同需求进行策略选择，有效加快算法的收敛速度以及丰富种群学习的多样性。但由于调和策略基于随机思想，无法准确感知布谷鸟的状态并做出决策，因此MSRCS 算法对CEC2013 测试集的28 个函数进行实验和统计分析，并与原始CS 和其7 种改进算法以及3 种经典群智能优化算法进行比较，还对自适应步长参数以及策略有效性进行研究，结果表明MSRCS 算法性能优于对比算法，同时证明了调和策略的可操作性。后续可将MSRCS 算法应用于车间调度、旅行商等复杂组合优化问题，进一步扩大其适用范围。