基于精英策略改进的自适应布谷鸟搜索算法

李 锐，龙文高，原可欣

（1 湖南科技大学 数学与计算科学学院，湖南 湘潭 411201；2 太原理工大学 文法学院，太原 030024）

0 引 言

布谷鸟搜索算法（Cuckoo Search，CS）是Xin－She Yang与Suash Deb 于2009 年提出的一种新型的群体智能算法［1］。该算法主要通过对生物界中布谷鸟寄生雏鸟的仿生行为，解决现实中的优化问题。

在自然界中，大部分鸟类的育雏习性是自筑巢自育雏，而布谷鸟则是寄生巢异育雏。布谷鸟会在其生活区域内寻找合适的巢穴快速产卵，同时布谷幼鸟会本能地模仿宿主幼鸟的叫声以得到宿主鸟的哺育，这样就实现了寄生巢。而且根据相关学者的研究表明，布谷鸟寻巢过程满足于Levy 分布［2］。不妨将布谷鸟找到的每个巢穴都看作一个可行解，由其Levy 飞行过程中产生替补解，按照一定的概率，遵循“新解更替，旧解淘汰”的规则，从而实现全局寻优，这就是传统的布谷鸟搜索算法和思想［3］。

传统的CS 具有仿生能力强、参数少、操作简单的特点，因而被广泛的应用于组合优化、电力调度以及机械工程等多个工程领域［4－6］。但在传统的CS 中，由于步长因子与发现概率是固定不变的，这就导致布谷鸟容易出现过早成熟的情况，寻优解的精确度较差，甚至找不到全局最优值以及收敛速度慢的情况。目前，学术界内主要通过调整参数与混合算法两种途径来解决这些缺陷。如：文献［7］中提出的一种参数动态更新的布谷鸟搜索算法，通过以一定概率下保留次优解及双向随机搜索策略，避免陷入局部最优；文献［8］提出的基于免疫进化改进的布谷鸟算法，通过结合两种算法的优点来作出改进与提高。

综上所述，改进算法虽然相较于传统CS 的性能有一定程度的提升，但改进后布谷鸟种群的全局寻优能力并没有得到明显的提高，且忽略了仿生性。因此，本文提出了一种基于精英策略改进的布谷鸟搜索算法（ESCS）。本文将布谷鸟群体进行分类，精英布谷鸟与普通布谷鸟执行不同的飞行策略，从而避免整个布谷鸟群体陷入局部最优而无法跳出；同时，布谷鸟群体的发现概率会基于迭代次数自适应变化，加快了算法后期的收敛速度，且保证布谷鸟会在全局最优值附近进一步搜索寻优。实验结果表明，本文提出的ESCS 相较于ICS 等一些改进算法具有较强的鲁棒性与较优的精确性。

1 传统的布谷鸟搜索算法（CS）

1.1 仿生学原理

在自然界中，大部分的鸟类会选择自筑巢和自哺育雏鸟，但有30%～40%的布谷鸟会选择异巢寄生幼鸟，这是一种特殊且少见的繁殖方式。在布谷鸟的繁殖期，布谷鸟会在一定范围内寻找合适的巢穴（寄主与布谷鸟生活习性相类同）进行产卵寄生，而寄主的哺育能力是有限的，布谷鸟为了增加其幼鸟的存活概率，会随机把寄主的一枚或多枚蛋推出巢穴。布谷幼鸟在破壳后，会本能的模仿寄主幼鸟的叫声，从而得到寄主的哺育。此外，布谷幼鸟在发育一段时间后，会把寄主巢穴中的蛋全部推出，从而进一步增大其生存几率。但随着进化过程，寄主也逐渐提高了辨认布谷鸟的能力，在识别出布谷鸟后，会进行攻击，布谷鸟只能放弃此处巢穴，再次搜索附近合适的巢穴。

1.2 参数定义

依据布谷鸟的生育特性进行仿生，在传统的CS中，以向量x＝［x1，x2，…，xn］ 代表布谷鸟，即为可行解。其中，xi为每个解分量，n为待求问题的维度。其它参数定义见表1。

表1 CS 中的参数定义Tab.1 Parameter definitions in CS

1.3 更新公式

在传统的CS 中，布谷鸟在寄巢生中有两种途径进行解的更新。一种是在寻找巢穴的过程中，基于Levy 飞行产生新的解：

式中，xb为历史最优解。

而另一种就是寄主发现布谷鸟的过程中产生新一代解：

式中，xi、xj、xk为随机选择的互异可行解。

2 基于精英策略改进的自适应布谷鸟搜索算法（ESCS）

2.1 自适应发现概率

在传统的CS 中，布谷鸟被寄主鸟发现的概率是固定不变的，通常设定Pa＝0.35。但这往往会导致在搜索寻优后期，布谷鸟群会跳过全局最优值而无法收敛于其邻域。

本文将布谷鸟被发现概率基于迭代次数进行自适应降低，遵循公式（3）：

在实际的优化问题中，如果减小布谷鸟被发现的概率，那么布谷鸟群就会趋向“当前最优值”不断靠近并继续搜索寻优，这就保证了算法的收敛速度与寻优解的精度；但如果发现概率过小，则很容易导致算法陷入局部最优解而无法跳出。因此，设置发现概率的下限为Pa／100，即便在后期，布谷鸟也有一定的概率跳出局部最优情况，间接确保布谷鸟在后期的搜索寻优能力不会退化。

2.2 精英策略

在传统的CS 中，布谷鸟群中离散程度较大，布谷鸟个体之间均视为同一等级。在进行搜索巢穴与寄生时，可以视为独立分工完成，这与实际的生物群体特性是不相符的。在对CS 进行初始化时，nestnum往往是大于50 的，这就要考虑群体效应。

无论是像狼群与狮群，存在等级制度的生物种群；还是像蚁群与蜂群，存在不同分工任务的生物种群；以及像鱼群一样只是简单的聚群生物，这些群体中总会有精英个体。精英个体无论是搜寻食物能力，还是御敌能力，都极大程度地优于种群中普通的个体，而且精英个体往往具有领导能力，即带领种群得到更好的食物、空间等资源，使得种群得以更好的生存。

本文参考生物种群的这一特性，将布谷鸟群进行分类：

式中，μ为黄金分割比。

对于普通布谷鸟来说，按照公式（1）与公式（2）进行解的更新；而对于任意一精英布谷鸟xnow，其需要考虑到整个种群的状态而进行相适应解的更新：

而对于其他精英布谷鸟xelse，其也会进行更新：

基于精英策略对布谷鸟群体进行划分，确保布谷鸟群始终保持着高强度的搜索能力与活跃度，提高了算法的准确度与寻优效率。

2.3 算法流程

（1）初始化参数；

（2）布谷鸟群基于Lvey 飞行进行搜索巢穴，可行解进行更新；

（3）判断是否被寄主发现：若是，则精英布谷鸟按照式（7）、式（8）更新解，普通布谷鸟按照式（2）更新解；否则均按照式（1）更新解；

（4）更新记录牌；

（5）判断是否达到最大迭代次数；若是则结束迭代；否则返回步骤（2）；

（6）输出历史最优值。

流程如图1 所示。

图1 ESCS 算法流程Fig.1 ESCS algorithm flow

3 仿真实验

3.1 仿真实验环境

本次仿真实验环境设置：操作系统Windows 10、CPU 为Intel（R）Core（TM）i7－7500U CPU、主频2.70Ghz、内存为4GB、仿真软件Matlab2020a。

3.2 实验参数初始化设定

该文参考了文献［9］、文献［10］以及文献［13］中参数的初始设定，并选取nestnum、Pa以及maxgen作为通用参数；对3 组通用参数进行等权平均化：

得到参数组合PM*，再借助专家意见，最终确定了针对于ESCS 的一组较优的参数组合，见表2。

表2 ESCS 参数设定Tab.2 ESCS parameter settings

3.3 测试函数

为了验证ESCS 的高效性与准确性，探究其实际的性能表现，该文选用ICS［8］与MCCS［12］进行横向对比，并选用表3 所列的6 个标准测试函数［11］进行仿真对比实验。

表3 标准测试函数Tab.3 Standard test functions

需要特别说明的是，为了更好检验ESCS 的全局搜索能力，该文将自变量的范围设定为［－5，5］。

3.4 实验结果分析

为了避免单次实验的偶然性而导致的实验误差，所有算法依次对6 个测试函数进行了20 次的重复实验。

该文选取最优测试值（Optimun results，OR）、方差（Variance，Var）以及正确率（Accuracy，AC）作为算法性能表现的评定指标，实验结果见表4。

表4 基于标准测试函数的对比结果Tab.4 Comparison results based on standard test functions

OR与AC反映了算法求解的准确性，而VAR与AC反映了算法求解的鲁棒性与效率。

对表4 的实验结果进行对比分析可知，在6 个标准测试函数的20 次重复试验中，MCCS 仅在f3中AC为100%，ICS在f3与f4中AC为100%，而对于ESCS，除了f5外，在其它5 个标准测试函数中的AC均为100%。

综合对比OR与VAR，ESCE 的性能表现最佳，ICS 次之，MCCS最差。在实际的工程项目中，对算法的准确性与鲁棒性有很高要求。假定算法准确性与鲁棒性同样重要，结合3 个指标，可以得出以下结论：ESCS 相较于ICS 和MCCS，在鲁棒性与准确性方面均有较大的提升。

3.5 补充对比实验

3.5.1 测试函数

为了进一步验证ESCS 的全局寻优能力与寻优解的精确度，本文选用了文献［8］、文献［15］以及MCCS 算法与ESCS 进行对比实验，并选取3 类高精度的测试函数：

其中，自变量的取值范围均为［－1，1］，全局最大值为2.118 8。

其中，自变量的取值范围均为［－10，10］，全局最大值为210.482 3。

其中，自变量的取值范围均为［－5，5］，全局最优值为1.031 628 453 489 88。

3.5.2 参数设定

为保证各算法的性能，在测试函数F1～F3中，分别对算法的一些基本公共参数［14］进行初始设定，见表5～表7。

表5 F1中的基本参数设定Tab.5 Basic parameter settings in F1

表6 F2中的基本参数设定Tab.6 Basic parameter settings in F2

表7 F3中的基本参数设定Tab.7 Basic parameter settings in F3

3.5.3 实验结果

第一轮性能对比实验，选取了“最佳适应度值变化趋势”作为对比指标，该指标可以很好的体现出算法之间收敛速度与准确度的差异，实验结果如图2～图4 所示。

图2 F1—最佳适应度值对比Fig.2 F1－comparison of optimal fitness values

图3 F2—最佳适应度值对比Fig.3 F2－comparison of optimal fitness values

图4 F3—最佳适应度值对比Fig.4 F3－comparison of optimal fitness values

其次，为了对比不同算法下种群之间搜索能力与全局寻优能力的差异，选取了“平均适应度值变化趋势”作为第二个对比指标，实验结果如图5～图7 所示。

图5 F1—平均适应度值对比Fig.5 F1－comparison of average fitness values

图6 F2—平均适应度值对比Fig.6 F2－comparison of average fitness values

图7 F3—平均适应度值对比Fig.7 F3－comparison of average fitness values

为避免单次实验因偶然性导致的实验误差，设置30 次的重复实验进一步验证ESCS 算法的性能。

本次实验选取最优测试值（optimum results）和最差测试值（worst results）为对比指标，实验结果见表8。

表8 仿真对比实验结果Tab.8 Experimental results of simulation

3.5.4 实验结果分析

由图2～图4 可知，ESCS 算法在迭代10 次后，收敛于全局最优值，收敛速度仅次于MCCS，且寻优解的准确度高于其它对比算法；MCCS 算法总体算法收敛速度最快，但在F1与F3中所得寻优解的准确度为最低；文献［8］的算法收敛速度在F1中呈现明显的断层状，在F2与F3中以近似对数递增趋势，因而其总体收敛速度是较为优异的，同时寻优解的准确度也是较高的；文献［15］算法的收敛速度与寻优解的准确度的综合表现仅次于MCCS。另外，由图5～图7 可知，在种群寻优搜索能力方面，ESCS与MCCS 不相上下，文献［8］次之，文献［15］最差。

由表8 对平均实验结果进行分析可得，针对于最优测试值（OR），ESCS 的精确度最高，文献［8］与文献［15］的精确度次之，MCCS 的精确度最差（尤其是在F2中）；而针对于最差测试值（WR），ESCS在F3中表现一般，但在F1与F2中表现最为优异，文献［15］在F3中表现最佳，在F1与F2中表现也较为满意，MCCS 的综合表现次之，文献［8］的综合表现最差。

结合以上分析，表明ESCS在收敛速度、寻优解的精度以及全局搜索能力等方面的综合表现优于其它参与实验的改进算法，验证了ESCS 的高效性与可行性。

4 结束语

针对传统的布谷鸟搜索算法存在过早成熟、寻优解的精确度与准确度差，以及收敛速度慢等问题，本文提出了一种基于精英策略改进的自适应布谷鸟搜索算法。ESCS在参数初始化阶段，将布谷鸟分为精英布谷鸟与普通布谷鸟，两种布谷鸟在被寄主鸟发现时会执行不同的飞行策略。精英策略可以避免算法陷入局部最优导致过早成熟。此外，再对布谷鸟被发现概率进行自适应改进，加快了算法后期的收敛速度。最后设置6 种标准测试函数与纵向对比实验，进一步验证ESCS 的综合性能表现，仿真结果表明ESCS 具有较好的鲁棒性与寻优性能。