基于随机扰动的自适应布谷鸟算法

2019-05-17叶亚荣贺兴时

计算机技术与发展 2019年5期

叶亚荣，贺兴时，张超

(西安工程大学理学院，陕西西安 710048)

0 引言

元启发式算法[1]自提出以来越来越被人们所熟知，其中包括遗传算法[2](genetic algorithm)、蚁群算法[3](ant colony optimization)、粒子群算法[4](particle swarm optimization)、萤火虫算法[5](fire fly algorithm)等。诸多研究已经证实了元启发式算法在实际应用中的可行性。

布谷鸟搜索算法是由英国剑桥大学杨新社和Suash Deb提出的，该算法模拟了布谷鸟寻找鸟窝放置新的鸟蛋行为，并有效结合了其他鸟类和果蝇的Levy飞行行为。这种算法不仅简单易行，参数较少，而且性能优于粒子群和遗传算法等启发式算法[6]。

布谷鸟算法与其他智能算法一样都存在易陷入局部最优且收敛速度慢等缺陷。对此，王凡等提出了一种基于高斯扰动的布谷鸟搜索算法(GCS)[7]，该算法与原有的布谷鸟算法相比能更好地跳出局部最优；王李进等提出了一种逐维改进的布谷鸟搜索算法[8]，但是存在求解全局最优解不够快的问题；薛益鸽等提出一种基于动态分组与高斯扰动的布谷鸟算法[9]，该算法求解速度快，精度高，但是易陷入局部最优。在算法运行过程中，初始化鸟群的质量起着至关重要的作用，好的初始种群能加快种群的收敛速度；宋庆庆等提出基于混沌序列的布谷鸟算法[10]；郑洪清等提出了一种自适应步长调整布谷鸟搜索算法[11]；陈华等提出了基于logistic模型的自适应布谷鸟算法[12]；李荣雨等提出一种基于梯度的自适应快速布谷鸟算法[13]。

受上述算法启发，针对布谷鸟算法的缺陷，文中提出了一种基于随机扰动的自适应布谷鸟算法。

1 CS算法

布谷鸟搜索算法(cuckoo search，SC)是模拟布谷鸟寻找鸟窝放置鸟蛋的行为，并结合Levy飞行更新鸟窝位置，完成了每代的更新，如果更新后的位置优于当前位置，则对鸟窝的位置进行更新，否则保留当前位置。由于布谷鸟算法简单、高效、搜索路径优等优点，已在背包优化[14]、机构优化[15]、工程优化[16]等问题中成功应用。

布谷鸟算法是在三个理想状态下进行概述。

规则1：每个布谷鸟每次只产一个蛋，并随机选择鸟窝放置它。

规则2：最好的鸟窝(解)会被保留在下一代。

规则3：可用的巢主鸟窝为n，巢主鸟能够发现外来鸟的概率是pa，其中pa∈[0,1]。在这种情况下，巢主鸟可将该鸟蛋丢弃，或者干脆抛弃这个鸟窝，在新的位置建立一个全新的鸟窝。

布谷鸟所选取的孵化鸟蛋的鸟窝，其实就是寻找搜索过程中的可行解，实质是当产生更好的鸟窝时，就代替上一代的鸟窝。基于布谷鸟育崽的习惯，布谷鸟下一代鸟窝的更新用levy飞行[5]进行更新，公式如下：

Xi(t+1)=Xi(t)+α⊕L(s,λ)

(1)

其中

1<λ≤3

(2)

其中，α>0为步长因子，它与问题的利害关系的程度相关联，大多数情况下取α=ο(L/10)，L为问题利害关系的特征范围。

2 自适应步长的随机扰动布谷鸟算法

2.1 自适应鸟窝位置更新

为了加快布谷鸟算法的收敛速度，在原始的布谷鸟算法中定义步长因子：

(3)

其中，ni表示第i代鸟窝的位置；nbest表示此代的最佳状态的鸟窝位置；dmax表示最好位置与其他所有鸟窝的距离的最大值。

在式3的基础上，引入了调解鸟窝位置的自适应调整步长策略：

stepsizei=stepmin+(stepmax-stepmin)di

(4)

其中，stepmax和stepmin分别表示步长的最大值和最小值。

位置更新公式如下：

s=s+α⊕stepsizei⊕ε

(5)

其中，ε是与pt同阶的随机矩阵；α为常数，⊕表示点对点乘法，通过多次实验，α取0.05来控制鸟窝的活动范围。

2.2 随机扰动

即

(6)

其中，ε是与pt+1同阶的随机矩阵，⊕表示点对点乘法。由于ε的随机取值范围较大，容易使鸟窝位置的活动范围偏离过大，经过多次实验取a=0.05来控制ε的搜索范围。

2.3 改进的布谷鸟算法(ASGCS)流程

1.初始化种群：nhost nestXi(i=1,2,…,n);

2.计算适应值：Fi(i=1,2,…,n);

3.While(t<最大迭代次数);

4.通过Levy flight与自适应步长来更新鸟窝Xi;

5.计算更新鸟窝的适应值Fi;

6.从n个鸟窝中随机选取一个鸟窝(记为j);

7.if(Fi

8.用新的解替换j;

9.Else对新的鸟窝进行随机扰动(记为k)；

10.End if

11.通过与发现概率pa进行比较，抛弃较差的解;

12.保留结果最优的解;

13.end

3 实验与结果分析

在参数相同的前提下，通过7个测试函数对ASGCS与CS算法性能进行比较，以MATLAB2016和Window7作为测试平台进行实验。对于所有的测试函数，种群的个数设置为n=8，最大迭代次数为500，搜索精度为105，扰动因子α=0.05。测试函数如表1所示。

表1 测试函数

在所有参数都一致的条件下，由图1可以看出，在Crownedcross函数下，原始的布谷鸟算法的初始值小于改进以后的ASCS算法的初始值，在后期收敛速度明显优于原始的CS算法，迭代次数也明显少于原始的CS算法。图2、图3在Matyas、Sphere函数下，无论是初始值还是收敛速度以及迭代次数，改进后的ASCS算法都优于原始的CS算法。由图4可以看出，在Multigaussian函数下虽然进化过程中收敛速度比较缓慢，但是改进后的ASCS算法比原始的CS算法能更快收敛。由于篇幅限制，Threehumpcamel、Zakh、Salomon函数没有进行展示，但是从收敛速度和迭代次数方面看，改进后的布谷鸟算法更好。故改进的ASCS算法性能优于原始的CS算法。

图1 Crownedcross函数的寻优曲线

图2 Matyas函数的寻优曲线

图3 Sphere函数的寻优曲线

图4 Multigaussian函数的寻优曲线

表2统计了两种算法在7个标准的测试函数下计算的平均最优值。可以看出，Crownedcross函数在ASCS的平均最优值比CS算法提高了4个点，而ASCS的最大值也比原始的CS值大，最小值也优于原始的CS算法。对于Matyas和Sphere函数的最大值与最小值，ASCS都优于原始的CS算法，ASCS算法的平均最优值也优于原始的CS算法。对于Salomon函数，ASCS算法的最大、最小值，平均值都为0，但是优于原始的CS算法。Zakh、Threehumpcamel函数在最大、最小值以及平均最优值提高了几十个点，虽然Multigaussian函数在ASCS算法下最优值比原始CA算法只提高了0.000 1，但是综上所述，ASCS在性能上优于CS算法。