交互信息的动态选择布谷鸟算法

杨荣莹，何 庆，王 茜 ，林 杰

1(贵州大学 大数据与信息工程学院，贵阳 550025) 2(贵州省公共大数据重点实验室，贵阳 550025)

1 引 言

随着科学技术的发展，传统优化机制不能满足实际优化问题中精度高、速度快、稳定性强等需求.由此，长期以来，众学者致力于发掘适合各种应用场景的优化策略，开发了多种群体仿生智能优化算法.如萤火虫算法(Firefly Algorithm，FA)[1]、人工蜂群算法(Artificial Bee Colony，ABC)[2]、粒子群算法(Particle Swarm Optimization，PSO)[3]、蝙蝠算法(Bat Algorithm，BA)[4]；灰狼优化算法(Grey Wolf Optimization，GWO)[5]等等.

布谷鸟搜索算法(Cuckoo Search，CS)于2009年提出，是模拟布谷鸟育雏行为和莱维飞行机制的仿生优化算法[6]，现已被广泛应用于实际优化问题中.刘等人[7]在优化配送路径时，提出了基于定向变异的布谷鸟算法；孙等人[8]提出多种群并行CS算法对防空火力分配进行优化；张等人[9]将改进的多目标CS算法应用于气动优化问题中；文献[10]在K均值聚类中利用CS进行优化，旨在Twitter的情感内容中寻找最优簇头.

然而，当面对NP难、适应度函数复杂且高维度的实际优化环境时，因CS易早熟、收敛速度慢、勘测开发不平衡、种群多样性低等缺陷遭遇瓶颈.于此，许多学者对CS算法进行改进.Lian等[11]将PSO的位置更新方式嵌入莱维机制中，提出了新布谷鸟算法(New Cuckoo Search，NCS)，结果表明，通过NCS得到的解均优于PSO和CS，但该算法鲁棒性弱、求解精度低；张等人[12]在CS中运用交互学习方式融合蚁群算法构造学习模型，动态更新步长和发现概率，然而该算法无法有效提升CS的种群多样性(1)http://kns.cnki.net/kcms/detail/11.2127.TP.20190409.1706.028.html. 2 https://doi.org/10.19734/j.issn.10013695.2018.10.0725.；黄等人[13]在CS中引进逐维处理和反向学习策略，以降低维间干扰，但该机制增加了算法的时间复杂度2；文献[14]在CS中构建3组更新策略，采用Snap-drift机制改进发现概率，但此算法随机性较强；为增强CS的局部开发能力，文献[15]融合Powell方法提出Powell Cuckoo Search(PCS)，从结果看，该混合算法的求解精度和收敛速度已不能满足现在寻优需求；张燕[16]利用Cubic混沌算子改进位置更新机制并引入自适应策略，既提高算法的求解质量，也扩大种群多样性.

统计发现，大部分改进CS算法中，位置更新策略固定，寻优搜索采用的鸟巢信息片面，缺乏多类别的种群个体信息；仅锁定迭代次数与发现概率的关系，忽略了适应度变化对发现概率的影响.而采用具有单一信息的个体搜索种群，会降低种群多样性、限制算法搜索活力[17].因此，本文提出一种信息交互的动态选择布谷鸟算法(dynamic selection cuckoo search algorithm of information interaction，II-DSCS).首先，改进更新策略，在伪随机因子扰动下，从样本整体(既种群整体N1)、当代最优(N2)、自身个体(N3)中采集鸟巢信息，构建N1、N2、N3彼此间的交互信息，建立3组位置更新模式.交互信息反映了种群的寻优情况，依据交互信息可调整算法的搜索方向使算法向最优解靠近，增加算法寻优速度，在搜索时，采用交互信息可增强搜索空间多样性.其次，对随机游走策略进行双向扰动，利用扰动因子构建两组游走机制.此外，为提升寻优收敛效率，利用鸟巢解的差异度自适应地更新发现概率.最终结果表明II-DSCS可以提高算法的求解精度，增强算法的搜索活力，加快算法的收敛速度.

2 标准布谷鸟搜索算法

布谷鸟算法起源于布谷鸟寄生育雏的繁衍模式，布谷鸟将自己的蛋放入其他鸟巢，由该巢主进行孵化，为保证幼雏存活率，布谷鸟必须找到最优鸟巢.基于此原理，将优化问题的解映射为巢穴，巢的优劣代表优化问题中解质量的高低，寻优既找寻优质鸟巢的过程，其遵照莱维机制和偏好随机游走策略来更新种群中鸟巢的位置.CS有3项理想准则：

a)一鸟一蛋，把蛋随机放入宿主鸟的鸟巢中；

b)每进化一次，都将最优质的鸟巢保存至下一次进化；

c)种群中鸟巢数量固定，巢主以概率Pa发现布谷鸟放入的蛋并丢弃该蛋.

在CS中，以莱维飞行机制更新鸟巢的位置，其表达式如下：

(1)

(2)

巢穴更新后，计算巢的优劣度，用一个均匀分布的随机数与发现概率比较，发现概率小于随机数则丢弃劣质的巢，重新构造鸟巢位置，更新公式如下所示：

(3)

3 II-DSCS

3.1 莱维机制改进

在标准CS中，莱维飞行虽然能有效探索全局空间，但只利用当前解与最优解更新鸟巢位置，种群信息受限，更新方式单调.这使算法在迭代前期无法猎获更多样的种群信息，限制算法的搜索范围，群间多样性差，算法搜索活力低；在迭代中后期，个体间相似度较高，算法陷入局部极值的概率增大；此外，更新方式单一，采集的个体信息片面，综合性、实时性的种群寻优数据在搜索过程中被忽略.因此，在保留莱维特性的基础下，引进新的个体信息，将多类别交互信息融入位置更新策略中，利用该信息扩展搜索空间多样性，开辟新的搜索领域.交互信息反映种群内个体之间适应度的差异，根据差异可及时调整算法进化方向，加快搜索速度，即使在高维复杂环境下，算法也能快速向最优解靠近.基于上述，改进的莱维机制表达式如式(4)所示：

(4)

(5)

cauchy的数学表示为：

(6)

上式中，g=1为尺度参数.

式(4)中，构建3组位置更新策略.通过“减法”构建信息的交互机制，分别从种群整体(N1)、当代最优(N2)、当前个体(N3)获取鸟巢交互信息，将此信息实时嵌入位置更新中，及时掌握鸟巢内适应度的优劣状况，再利用随机策略选择位置更新方式.为确保交互信息的全面性和总体性，采用Cauchy算子对随机鸟巢进行扰动，柯西算子可以无重复地遍历种群中每个个体，使算法更大限度地收集种群个体信息，延展交互信息领域[18].

采用更新策略1时，在柯西算子扰动下，利用种群内两个随机鸟巢的差值来衡量所有个体的差异度(构建N1与N1的交互信息)，在N1&N1(种群整体)领域进行全局寻优；在更新策略2中，依据柯西算子选择一个随机鸟巢，并评价N1与N2的适应度差异(构建N1与N2的交互信息)，在N1&N2维度上来更新鸟巢位置(进行以N2为核心的局部搜索)；更新策略3中，构建N1与N3的交互信息，考量N1与N3的差异，在N1&N3内寻优搜索(进行以N3为主干的局部搜索).该改进策略，依据N1、N2、N3的交互信息进行多方位的位置更新，全面评估种群差异与寻优情况，充分拓展算法的搜索范围；随机选择位置更新策略，使算法在全局与局部之间动态寻优，克服勘测开发不均衡问题；基于柯西算子引入实时个体信息，最大化地增加种群多样性.

3.2 偏好随机游走策略改进

标准CS算法经发现概率丢弃劣解后对鸟巢位置进行更新，并采用精英策略保留最优值至下一代，随着算法迭代加深，鸟巢信息相似度升高，搜索空间多样降低，陷入局部极值概率增大，寻优能力受到干扰.因此，依据3.1节理论，将动态选择、信息交互思想与偏好随机游走策略融合，以提高算法种群多样性和搜索性能，消除局部极值的约束.对式(3)做改进，表达式如式(7)所示：

(7)

式(7)中，M=0.5，A=rand(1，ps)，P∈(-1，1)为随机数.

式(7)中，利用“减法”交互机制，构建扰动鸟巢(受缩放因子P扰动)与随机鸟巢的交互信息，组成一个新的位置更新策略；保留原始的偏好随机游走策略(既P扰动两个随机鸟巢的交互信息)作为另一组位置更新方式；此外，将标准CS中R∈(0，1)变成P∈(-1，1)，将单向(正向)扰动扩展成正反双向扰动.该位置更新模型由两组携带不同交互信息的更新机制组成，克服了单一的更新方式，动态选择机制将利用更多样的鸟巢信息解锁新的搜索空间，既提高算法种群多样性，又改善算法寻优效率.

3.3 发现概率改进

在CS算法中，发现概率Pa是平衡全局探索和局部开发的重要指标，其大小影响着算法的收敛速度和寻优精度.而传统CS的Pa是固定值，无法自适应变化，在迭代过程中可能会丢弃过多的鸟巢导致多样性降低，算法求解能力受限.针对以上问题，对发现概率做自适应动态改进，在Pa中融合迭代、种群适应度信息，依据迭代程度动态选择丢弃概率，改进的发现概率为：

(8)

m=fmax-fmin

(9)

(10)

式(8)中，iter为当前迭代次数，Maxiter为最大迭代次数，式(9)中，fmax、fmin、avgen(iter)分别为每一轮迭代时适应度的最大值、最小值、平均值.

以上3个式子中，以携带迭代信息的Pa1作为控制参数操纵Pa，将每轮迭代时适应度的平均值和最大差异值作为发现概率的选择指标.若差异值大于平均适应度，种群内个体之间的差距过大，算法表现较弱，此时应增大丢弃的可能性，降低发现概率；若差异小于或等于平均适应度，表明个体向最优解聚拢，应保留更多优质解，减小丢弃可能性，增加发现概率.此策略组合适应度与迭代次数的信息，更精准地估量进化程度并调整发现概率，提高进化与收敛速度，平衡局部开发与全局探索.

3.4 II-DSCS算法实现流程

交互信息的动态选择布谷鸟算法的主要步骤为：

a)设置种群规模、迭代次数、初始位置等初始参数；

b)计算种群中所有个体的适应度，并保留最优解；

c)根据式(4)进行位置更新，并计算所有个体的适应度，保留最优解至下一代.

d)利用式(10)计算发现概率，比较Pa与随机数K，若K>Pa，丢弃劣质巢穴，利用式(7)进行位置的更新；反之，保持当前鸟巢位置不变；

e)计算经过步骤d)变化后每个鸟巢适应度，并保留最优鸟巢进行下一轮的进化；

f)判断算法终止条件，若满足，则输出最后结果；反之，返回步骤c)继续进化，直到满足结束条件为止.

该改进算法的流程图如图1所示.

图1 II-DSCS算法流程图Fig.1 Schematic diagram of II-DSCS algorithm

4 实验与分析

为检验II-DSCS算法的有效性，选取12个具有不同特征的经典基准函数进行仿真实验，将该算法与PSO[3]、CS[6]以及CS的3个变体NCS[11]、DA-DOCS[13]、SDCS(Snap-drift cuckoo search)[14]进行比较.该仿真实验在MATLAB R2015b、corei5、32位windows7操作系统下进行.

4.1 函数与参数设置

12种基准函数如表1所示，包括6个单模态函数(F1-F6)和6个多模态函数(F7-F12)，F1在搜索空间下，极值唯一，用于检验算法的寻优能力；F7的全局最优点位于一个平滑、狭长的抛物线形峰谷内，算法提供的有限信息使其在寻优时很难辨别搜索方向，搜索难度大；F5与F9用来检测算法的收敛性能，与F5不同的是，F9在多维空间下，其顺着梯度的寻优方向是多向散射的；F11震荡性较强，具有无数个极小值点，很难找到全局最优值；F12是典型的非线性多模态函数，寻优空间广泛，局部极小值数量与求解维度相关，很难处理高维环境的优化问题.这些函数在高维下，求解难度较高，将其运用于仿真实验中，以测试在高维、适应度函数复杂、搜寻方向多变等环境下算法的寻优效率、求解精度、收敛速度等性能.

表1 测试函数Table 1 Test functions

4.2 寻优结果分析

为保证比较的公正性、可比性，选取的3个CS变体都对CS位置更新进行改进.

将平均值、最小值作为求解精度的评价参数.表2-表4中，PSO、CS、NCS均不能在12个函数下同时得到min和avg的最优值，只能在F6中得到min的最优解.其中， DA-DOCS只能在F6下满足求解精度最优要求.SDCS在5个函数中寻到精度评价参数的理论最优值.而II-DSCS获得8个函数的精度评价指标的理论最优，寻优成功率100%；且在F3、F10中，avg的寻优效果已达百个数量级，min已得理论最优解，若增加迭代次数，II-DSCS将会搜索到F3、F10的avg的全局最优解.由于多模态函数F7的极值点位置偏僻，求解难度较大，PSO、CS、NCS、DA-DOCS、SDCS在该函数中均无法收敛，而II-DSCS在该函数下已能收敛，精度指标高于前5种算法.结果表明，II-DSCS获得极具压倒性的寻优能力，引入的信息交互机制多角度采集种群个体并及时用于更新策略中，增强了局部寻优和全局搜索性能，提升了搜索精准性.

标准差大小反映了算法鲁棒性的强弱，鲁棒性越强，标准差越小；反之，鲁棒性越差.由表2、表3、表4的std可知，PSO、CS、NCS几乎无法得到12个函数下std的最优解，稳定性极差；DA-DOCS只在个别函数下具有一定的稳定性；SDCS在8个函数的std中寻到最优(在F1/F5中，SDCS的avg、min劣于II-DSCS)；除F7外，II-DSCS在11个函数的中，std均为理论最优值，且F7的std小于其他5种算法.其表明，改进的II-DSCS以全局为视角，综合性勘测种群寻优情况，使得算法鲁棒性显著提升.

统计数据可知，3种维度下，II-DSCS搜索能力不受影响，维度之间寻优精度差异均控制在1-4个数量级内.差异较明显的是DA-DOCS，其在F1-F3、F5、F9、F12六个函数中，搜索性能随着维度的升高而降低；PSO在处理F4时，求解能力随着维度增加呈指数下降，当维度升到100，解的质量比30维的增长了100多个数量级；观察II-DSCS，3个维度下，寻优性能几乎保持不变，其余算法的求解性能随着维度的增加几乎均有所衰弱.由此可得，改进的II-DSCS的维度敏感性强于其余算法，求解性能对维度不敏感，能有效处理高维问题，具有较强的维度敏感性.

表2 30维的寻优精度结果Table 2 Optimization accuracy values of 30 dimensions

表3 50维的寻优精度结果Table 3 Optimization accuracy values of 50 dimensions

表4 100维的寻优精度结果Table 4 Optimization accuracy values of 100 dimensions

4.3 收敛性分析

为了更直观地观察算法的寻优进程与求解性能，图2给出了6种算法在1000次迭代下的进化曲线.为保证进化曲线的清晰度与可视度，降低重合度与模糊度，将纵轴设置为适应度值取对数(log10)，横轴为迭代次数，每个函数的纵轴取值不同，且纵坐标为对数值，当算法收敛到0时，此时的寻优曲线在图上无法显示.

单模态函数中，CS、PSO、NCS、DA-DOCS的求解能力显著低与SDSC与II-DSCS；特别地，F3、F4函数下，CS、PSO、NCS、DA-DOCS的收敛曲线几乎与横轴平行； NCS跳出局部极值能力高于PSO、CS，但其陷入局部极值的时间与迭代次数成正比；SDCS的寻优性能强于前4种算法，进化曲线波动小； F6中，II-DSCS 的收敛曲线几乎垂直于纵轴，能在30代内收敛到最优值.

多模态函数下，所对比的5种算法收敛能力均有所降低，寻优结果与理论最优值差距变大.F7中6个算法都没有收敛到理论最优值，SDCS从约40次迭代开始陷入极值区域无法跳出，而 II-DSCS迭代初期收敛能力更强，进化过程中跳出局部极值的概率更高；F8、F10、F11中，PSO、CS、DA-DOCS的进化曲线几乎垂直于纵轴，说明算法陷入局部极值的时间较长，搜索空间的多样性较弱；F11/F12中，II-DSCS比SDCS提前100余次收敛到理论最优值.

收敛曲线表明，加入信息交互机制的II-DSCS既能提高收敛速度，也能增强收敛精度，改进策略多角度更新鸟巢位置，动态评估搜索情况，使算法在高维环境下保持活跃的搜索力、快速的收敛速度以及较强的稳定性.

4.4 收敛性分析

时间复杂度是评价算法性能的重要因素，其高低反映算法运行效率.由文献[19]和文献[20]可知，CS每一代总的时间复杂度为O(n+f(n))[19]，依据文献[19]、文献[20]的分析方法，对II-DSCS算法的时间复杂度进行分析.

在II-DSCS算法中，初始化阶段的时间复杂度与CS算法一致，为O(n+f(n)).在第一个新解生成阶段，设变量生成时间为x1，公式(4)评价一次的时间为x2，新旧解比较时间为x3，新解替换旧解的时间为x4，计算目标函数的时间为f(n)，时间复杂度为：

O(N(n(x1+x2)+x3+x4n+f(n)))=O(n+f(n))

(11)

在第二个新解生成阶段，设求解发现概率的时间为x5，此阶段的变量初始化时间为x6，公式(7)每操作一次的时间为x7，新解与旧解比较以及替换的运行时间与第一个新解生成阶段一致，该阶段的时间复杂度为：

O(N(x6n+x7n+x3+x4n+f(n)))=O(n+f(n))

(12)

可知，II-DSCS记录最优解的时间复杂度与CS算法一样，为O(N(x3+x4n))=O(n).由此，本文所提算法最终的时间复杂度为O(n+f(n)).改进的II-DSCS算法增加了选择比较操作时间，但时间复杂度与原始CS保持在同一量级上.

5 结束语

基于传统CS算法，综合考虑其收敛速率低、勘探开发不平衡、搜索空间多样性低等缺点后提出一种利用鸟巢信息交互的动态选择布谷鸟算法.在保证CS算法自身特性的基础下，采集多类别种群数据，将单一更新机制变成多组搜索策略，利用个体交互信息扩展搜索区域的多样性，并动态选择位置更新方式以确保局部开发与全局探索之间达到平衡；融合扰动因子，保证交互信息的全面性；运用适应度差值来评价种群的进化程度，基于控制参数自适应更新发现概率.对该算法进行测试验证，结果表明，在6种算法中，II-DSCS算法的收敛精度和速度均优于PSO、CS、NCS、DA-DOCS、SDCS算法，该算法的稳定性更高、鲁棒性更强、搜索更灵活，拥有极具竞争价值的寻优求解能力，具有较高的实际应用价值.近一步的计划是将该改进机制应用于实际优化问题中.

图2 PSO/CS/NCS/DA-DOCS/SDCS/II-DSCS寻优收敛曲线图Fig.2 Optimization convergence curves of PSO/CS/NCS/DA-DOCS/SDCS and II-DSCS