基于小批量梯度下降的布谷鸟搜索算法

2020-09-24梁永全

山东科技大学学报(自然科学版) 2020年5期

田媛，梁永全

（山东科技大学计算机科学与工程学院，山东青岛266590）

20世纪后期出现了越来越多受自然启发的现代元启发式算法，通过模拟自然现象和动物行为来解决函数优化问题，如蚁群算法（ant colony optimization，ACO）［1］、粒子群算法（particle swarm optimization，PSO）［2］等，这类启发式智能算法是计算智能领域的研究热点方向之一，并在求解工程优化等实际问题中获得广泛应用。

随着计算智能技术的快速发展，各种新颖的仿生优化算法相继被提出，其中布谷鸟搜索（cuckoo search，CS）算法是剑桥大学的Yang等［3］于2009年在模拟布谷鸟寻巢产卵的行为中提出的一种全局搜索算法，用来解决函数目标优化问题，具有选用参数少、容易实现、搜索路径优和寻优能力强等特点［4-6］。已经通过建立Markov链模型在理论上证明了布谷鸟搜索算法可收敛于全局最优［7］，在收敛速度和稳定性方面都超过了遗传算法和粒子群优化算法［3］。布谷鸟搜索算法需要的控制参数少，并且可以在随机化和集约化上保持良好的平衡。但CS算法作为一种新兴的仿生算法，其收敛速度和收敛结果精确度仍需进一步改善，针对函数优化问题，大部分都是基于发现概率、自适应步长的改进和混合CS算法改进的。

基于发现概率的改进中，文献［8］认为发现概率P 如果固定不变，将会使得不管是较好解还是较坏解都会以同样的概率被替换掉，因此提出一种动态的方法，根据整体解的情况确定来调节发现概率P 从而提高算法的求精能力和收敛速度。文献［9］通过改变发现概率，提出一种基于自适应机制的改进机制来控制缩放因子和发现概率，提高布谷鸟搜索算法求解函数优化问题的求精能力和收敛速度。文献［10］使用模糊控制系统来动态的调节布谷鸟搜索算法的发现概率P，提高了CS算法的收敛速度与计算精度。

在基于自适应步长的改进中，文献［11］通过对标准布谷鸟搜索算法中参数偏度动态自适应取值来实现算法对步长的动态自适应，同时引入动态平衡因子以调节全局适应度和当前迭代次数所占的比重，实现了布谷鸟搜索算法收敛速度和搜索精度的平衡。文献［12］利用一种基于种群排序的改进算法来指导随机游动时的步长，提高步长的自适应性，在收敛速度和收敛精确度上都优于标准的CS算法。

在混合CS算法改进中，文献［13］采用简单的2-opt算子作为局部优化算子加快算法收敛速度，引入模拟退火机制防止算法陷入局部最优，提高算法的通用性。文献［14］优化局部搜索，在算法中偏好随机游动和莱维随机游动之间融合PSO组件，利用PSO算法优化种群，然后利用CS算法在最优个体中继续寻优，提高了算法的性能。文献［15］结合动态惯性改进策略改进鸟窝位置的更新方式，依据动态惯性权重值保留上代鸟窝的最优位置并进行下一代位置更新，有效平衡了种群探索能力和开发能力。文献［16］在布谷鸟算法的迭代过程中对鸟窝位置加入高斯扰动，增强了鸟窝位置变化的活力，提高了算法的收敛速度。

目前，布谷鸟搜索算法以及其改进算法已经广泛应用于大量实际应用问题中。文献［4］选用布谷鸟搜索算法解决调度置换流水车间问题，取得了良好的实验结果，证实其可以作为解决流水线生产调度问题的一种有效方法。文献［5］融入量子计算和混沌局部搜索策略，以IEEE 118节点系统的最优潮流计算问题证明改进后的布谷鸟搜索算法的有效性。文献［6］将改进后的布谷鸟搜索算法应用于桥式起重机主梁优化设计中，算法符合主梁约束条件，改进算法具有较高的可行性并取得了显著的优化效果。

原始布谷鸟搜索算法是基于无约束的全局优化方法，每一代都参考当前最优鸟窝，使其具有高效的寻优能力，但布谷鸟种群进化方向由Lévy flight随机游走产生的随机步长决定，过大的随机性会使寻优结果无法准确落在最优解的位置，而是围着最优解进行小范围波动，导致算法在进化过程中缺乏可控制性，存在后期收敛慢和搜索精度不稳定的问题。目前提出的改进算法中，无论是动态改变发现概率还是结合其他框架，都增加了算法复杂度和运行内存，破坏了原始布谷鸟搜索算法控制参数少、运算简便等优点。针对这个问题，本研究在随机游走过程中引入小批量梯度下降（mini-batch gradient descent，MBGD），与CS算法结合得到基于随机梯度下降的布谷鸟搜索算法（cuckoo search algorithm based on mini-batch gradient descent，MBGDCS）。

1 布谷鸟算法

在自然界中，布谷鸟采用寄生育雏的特殊繁殖后代策略，将自己的卵生在其他（义亲）鸟的鸟巢里，由义亲鸟来代替自己孵化与养育下一代，并且为了保证孵化率，将义亲鸟的蛋扔出鸟巢。

布谷鸟搜索算法在寻优的过程中采用Lévy flight模式，Lévy flight是一种随机游走，每一步方向完全随机而各向同性，步长较小的短距离行走与偶尔较大步长的长距离行走相互交替，且步长服从重尾分布（heavy-tailed）。Shlesinger［17］将该飞行方式植入到群智能搜索算法中，长距离行走用于探索发现，扩大搜索范围，跳出局部最优的情况，距离越大，越容易搜索全局最优，但会降低搜索精度，有时会出现震荡现象；短距离行走用于在小范围内收敛于全局最优解，距离越小，求解精度越高，但会降低搜索速度。Lévy flight每步游走都由两个因素控制：一是游走方向，一般选取一个服从均匀分布的数；二是步长，步长服从Lévy分布。Reynolds等［18］证明了当目标位置呈现随机特征并且无规律地稀疏排布时，对于M 个相互独立的寻优者来说，Lévy flight是最有效、最理想的搜索策略。Lévy flight可以在不确定区域内最大限度地进行有效的搜索，许多动物的觅食模式都是Lévy flight，很多人类行为也符合Lévy flight。图1为一个二维1 000步Lévy flight实例图，在原点［0，0］开始随机游走，游走过程中可以看出较小的跳跃组成的聚集被较大的跳跃分隔开的现象。

图1 二维1 000步Lévy flight实例图Fig.1 2D Lévy flights in 1 000 steps

布谷鸟寻找适合自己产卵的鸟窝位置是随机的或类似随机的方式，通过模拟布谷鸟寄生育雏行为及鸟类Lévy flights行为，设定以下三个理想规则［3，17］：

规则1 每只布谷鸟一次只产一枚蛋，并随机选择一个鸟窝存放；

规则2 在上一代选取的鸟窝里，鸟窝里最好的鸟蛋会保留到下一代；

规则3 可利用的鸟窝数量n 是固定的，宿主鸟发现一个外来鸟蛋的概率pa∈［0，1］，被发现的情况下，宿主鸟将扔掉这些外来鸟的卵或直接放弃该窝，去随机建立一个新窝。

在这三个理想规则的基础上，布谷鸟寻窝的路径和位置更新公式如下：

其中，α0是常数（α0=0.01），xbest表示当前最优解；Levy（β）是Lévy随机搜索路径，服从Lévy概率分布：

通过Lévy flight生成的步长s是不重要的，CS算法的提出者Yang等［19-20］提出了一个简单方案：

其中，u，v 服从标准正态分布，即

这里

综合式（1）～（6），在Lévy flight随机游动组件中，生成新的解x（t）i的公式可以归纳为：

经过位置更新后，用随机数r∈ ［0，1 ］与发现概率pa∈［0，1 ］进行比较，若r＞pa，则对进行随机改变，舍弃小部分不好的鸟窝，根据随机游走生成与舍弃鸟窝相同数目的鸟窝，与未舍弃的鸟窝混合得到一组新鸟窝，从而避免陷入局部最优，反之不变。最后保留测试值较好的一组鸟窝位置仍记为

综上所述，布谷鸟搜索算法中的随机游走效果明显，大步长的游走有效避免了算法陷入局部最优，而小步长的移动可以有效地寻找最优解，使算法在寻找最优解时十分有效且高效；同时，算法中需要调整的参数数量少，使得CS算法更广泛地适用于函数优化问题中。算法迭代过程中的每一组鸟窝都可以看作一组解决方案，因此CS算法也可以扩展应用在集合种群算法中。

2 基于小批量梯度下降的布谷鸟搜索算法

梯度下降算法是目前机器学习领域最常用的优化算法，被广泛应用于各种优化问题中。梯度下降算法大致可以分为三种：批量梯度下降（batch gradient descent，BGD），每次迭代利用整个训练集进行优化；小批量梯度下降（MBGD），每次迭代利用部分训练集进行优化；随机梯度下降（stochastic gradient descent，SGD），每次迭代仅用一个随机选择的样例进行优化求解。小批量梯度下降结合了批量梯度下降和随机梯度下降的优点，比批量梯度下降更简便，比随机梯度下降的准确性高，因此，在原始布谷鸟搜索算法中加入小批量梯度下降法，只需要每一代的小部分鸟窝信息即可以得出梯度方向，不会破坏原始布谷鸟搜索算法每一代进化过程中的独立性，不需要引进其他参数，利用小批量梯度下降法一定程度上限制原始算法进化过程中过大的随机性，使算法在迭代过程中可以更准确地寻找最优解，提高算法搜索速度和搜索精度。

在布谷鸟搜索算法迭代过程中，在每次迭代得到的一组解中选取适应值最优的部分构成一个小批量梯度下降的批，从而确定一个梯度方向，从当前解出发沿该方向确定一个梯度下降的点，再从这个点出发利用Lévy flight找到一个新的解与之前的解进行比较。若新的解优于旧解，则用新的解代替旧的解；若不优于旧解，则返回之前小批量梯度下降得到的点，继续小批量梯度下降得到新的点，重复此过程直到迭代结束。基于小批量梯度下降的布谷鸟搜索算法（MBGDCS）结合布谷鸟算法随机飞行不容易陷入局部最优和小批量梯度下降法寻找最优解的优势，提高算法的自适应性以及算法的求解精度和求解效率。

根据分析，MBGDCS算法的实施过程与步骤如下：

步骤1（初始化）随机生成n 个鸟窝，发现概率pa，搜索空间维数为nd，解的上下界分别为Ub与Lb，精度Tol，最大迭代次数iteration；生成初始鸟窝位置，i∈{1， 2，…，n}和当前的最优解fmin。

步骤2（循环过程）保留上代最优的batch_size个鸟窝的位置，通过小批量梯度下降得到下降方向向量，利用Lévy flight在方向对其它鸟窝进行更新，得到一组解；对这组鸟窝位置进行测试，将这组解与上一代的解进行比较，用新解中较好的解替换上一代中较差的解，从而得到一组较优的鸟窝位置，记为，i∈{1， 2，…，n}。

步骤3 用服从均匀分布的随机数r ∈ ［0，1 ］作为鸟窝主人发现外来鸟蛋的可能性并与pa比较，若r＞pa，保留被发现概率较小的鸟窝位置，同时随机改变发现概率较大的鸟窝位置，得到一组新的鸟窝位置，将这组鸟窝位置进行测试，与替换前的每个鸟窝位置的测试值进行对比，用测试值较好的鸟窝位置替换测试值较差的鸟窝位置，得到一组新的较优鸟窝位置。

改进后的基于小批量梯度下降的布谷鸟搜索算法只需要初始化鸟窝数和发现概率两个关键参数，设置好目标函数的相关信息，不需要额外的输入信息。算法输出包括算法迭代得到的最优目标函数值、最优鸟窝位置、得到最优鸟窝的迭代次数、每次迭代的结果和迭代过程图。

3 实验结果与分析

仿真实验的运行环境为Intel（R）Core（TM）i5-4200U CPU，主频1.60 GHz，内存4 GB，Windows 10 64位操作系统，实验仿真软件采用Matlab R2013b。

为了观察改进算法求解函数优化问题的收敛速度和解的质量，验证所提出方法的有效性，实验选择3类测试函数，包括5组单峰基准测试函数、3组多峰基准测试函数和3组固定维度多峰基准测试函数［21-22］，见表1。实验中用CS算法和改进后的MBGDCS算法对每个测试函数分别运行20次，进行200次迭代，取平均值表示搜索的结果精准性，实验中参数默认设置为：鸟窝规模n 为25，发现概率pa为0.25，梯度下降的批量batch_size为5。实验结果如表2～3和图2～12所示。

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

3.1 收敛速度和求精能力分析

对单峰基准测试函数而言，由表2可以看出，MBGDCS算法比CS算法在提高收敛速度上效果显著，测试函数f1的MBGDCS算法平均迭代次数比CS算法平均减少16.25次，提高了77.57%；测试函数f2的MBGDCS算法平均迭代次数比CS算法平均减少43.3次，提高了95.58%；测试函数f3的MBGDCS算法平均迭代次数比CS算法平均减少15.45次，提高了79.23%；测试函数f4的MBGDCS算法平均迭代次数比CS算法平均减少59.5次，提高了96.75%；测试函数f5的MBGDCS算法平均迭代次数比CS算法平均减少95.5次，提高了63.83%。从表3可以看出，MBGDCS算法迭代得到的最优解的精确度有了很大提高，测试函数f1到f4都收敛到了理论最小值，而CS算法都存在一定的误差；测试函数f5在MBGDCS算法的迭代中虽然没有收敛到理论最小值，但是收敛结果比CS算法提高了0.000 281 4，与理论最小值相差0.000 182 4。

对多峰基准测试函数而言，从表2和表3可以看出，无论是收敛速度还是收敛结果，MBGDCS算法都比CS算法有了显著提高，尤其是收敛速度上，多峰基准测试函数f6、f7、f8都以极快的速度收敛，仅需要1次迭代或者2次迭代即可收敛，相比原算法收敛速度分别提高了98.38%、98.97%和97.43%，同时在收敛结果上也稳定收敛到理论最优值，尤其对测试函数f7，收敛结果与理论最优值的误差减小了12.802 37，效果十分明显。

表2 平均收敛次数表Tab.2 Average number of iterations to convergence

表3 平均收敛结果表Tab.3 Average convergence result

对固定维度基准测试函数而言，由表2和表3可知，CS算法和MBGDCS算法都收敛到了理论最优值，但是MBGDCS算法在收敛速度上比CS算法有一定的提高，测试函数f9迭代到58.25次收敛，收敛速度提高了8.48%；测试函数f10迭代87.4次到达收敛，收敛速度提高了25.52%；测试函数f11迭代32.55次到达收敛，收敛速度提高了33.97%。

图2到图12是测试函数迭代过程中的函数值进化曲线，可以看出，改进后的MBGDCS算法比原始CS算法收敛速度更快，寻优精确度更高，效果提升明显。

图2 测试函数f1 迭代过程图Fig.2 Iterative process of f1

图3 测试函数f2 迭代过程图Fig.3 Iterative process of f2

图4 测试函数f3 迭代过程图Fig.4 Iterative process of f3

图5 测试函数f4 迭代过程图Fig.5 Iterative process of f4

图6 测试函数f5 迭代过程图Fig.6 Iterative process of f5

图7 测试函数f6 迭代过程图Fig.7 Iterative process of f6

图8 测试函数f7 迭代过程图Fig.8 Iterative process of f7

图9 测试函数f8 迭代过程图Fig.9 Iterative process of f8

图10 测试函数f9 迭代过程图Fig.10 Iterative process of f9

图11 测试函数f10迭代过程图Fig.11 Iterative process of f10

图12 测试函数f11迭代过程图Fig.12 Iterative process of f11

综上所述，改进后的MBGDCS算法与原始CS算法相比，在收敛速度和收敛精度方面都有明显提高。

3.2 同类算法性能比较

粒子群算法［2］与灰狼算法（grey wolf optimizer，GWO）［23］都是目前常见的启发式智能优化算法，处理函数目标优化问题各有优势，将改进布谷鸟搜索算法与粒子群算法、灰狼算法进行性能对比，每组函数运行10次，取平均值进行对比，对所有测试函数测试结果如表4所示。

表4 算法对比结果Tab.4 Comparisons of algorithms

由表4可知，对单峰基准测试函数和多峰基准测试函数，MBGDCS算法的寻优结果均比粒子群算法和灰狼算法优秀，除测试函数f5外都准确找到理论最优解，而粒子群算法和灰狼算法都有一定误差，测试函数f5的寻优结果也优于其他两种算法；对固定维度基准测试函数，测试函数f9仅在MBGDCS算法的寻优过程中找到了理论最优，测试函数f10和f11三种算法都寻找到了理论最优。

综上，MBGDCS算法较粒子群算法和灰狼算法有更高的寻优准确度，在实际应用的优化设计中较易取得更好的结果。

3.3 参数敏感性分析

参数敏感性分析是确定模型关键参数以及发现目标变量对某参数变化的响应敏感程度的重要方法。布谷鸟算法具有初始化参数少的优点，改进后的MBGDCS算法与原始CS算法相同，只需要初始化n 和pa，使用单参数分析方法对MBGDCS算法进行参数敏感性分析，分别单独改变各所选参数的取值，然后对改变参数后的MBGDCS算法进行10次运算，每次运算迭代200次，取10次运算的平均值表示结果的准确性，10次结果的标准差表示结果的稳定性。

首先对初始化鸟窝数n 进行敏感性分析。MBGDCS算法默认n 取25，固定其他参数不变，将初始化鸟窝数n 的数值分别取10、15、20、30、35、40，进行10次运算的平均收敛次数、平均收敛结果和对应标准差如表5、表6所示。从表5可知，n 取10～40时，测试函数f1、f3、f5、f9、f10和f11的平均收敛次数有很小的递减趋势，整体保持稳定，其他测试函数平均收敛次数稳定没有变化，说明MBGDCS算法对初始化鸟窝数n的变化不敏感。从表6可知，n 取10～40时，仅测试函数f5存在极小的误差，其他均收敛到理论最优，说明MBGDCS算法的收敛结果对初始化鸟窝数n 的变化不敏感。综上所述，说明MBGDCS算法的收敛结果对初始化鸟窝数n 的变化不敏感。

表5 参数n 敏感性测试平均收敛次数表Tab.5 The average convergence times of test functions on n

表6 参数n 敏感性测试平均收敛结果表Tab.6 The average convergence results of test functions on n

然后对初始化发现概率pa进行敏感性分析，MBGDCS算法默认pa取0.25，固定其他参数不变，将初始化发现概率pa的数值分别取0.10、0.15、0.20、0.30、0.35、0.40，进行10次运算的平均收敛次数、平均收敛结果和对应标准差如表7、表8所示。从表7可知，MBGDCS算法的收敛过程对初始化发现概率pa的变化不敏感。从表8可知，MBGDCS算法的收敛结果对初始化发现概率pa的变化不敏感。综上，说明MBGDCS算法对初始化发现概率pa的变化不敏感。

因此，通过单参数分析法对MBGDCS算法进行参数敏感性测试可知，算法具有较高稳定性。

4 结束语

针对布谷鸟搜索算法存在的后期搜索速度慢、易早熟收敛和局部搜索能力弱等缺点，提出了基于小批量梯度下降的布谷鸟搜索算法，利用小批量梯度下降优化局部搜索，提高算法自适应性，通过11个标准测试函数测试结果表明，改进后的布谷鸟算法具有更快收敛速度和更高的寻优精度，尤其是对多峰基准测试函数的寻优问题上提升十分显著，相比其他启发式智能优化算法在性能上有一定的优势。