基于动态分组与混沌扰动的改进布谷鸟算法

薛益鸽

(温州商学院信息工程学院，浙江 温州 325035)

基于动态分组与混沌扰动的改进布谷鸟算法

薛益鸽

(温州商学院信息工程学院，浙江 温州 325035)

针对布谷鸟算法(CS)求解速度不够快、精度不够高的问题，给出一种基于动态分组与混沌扰动的改进布谷鸟算法(ICS)，并通过5种经典的测试函数对其性能进行测试.仿真实验结果表明，ICS比CS有更快的求解速度和更高的求解精度.

布谷鸟搜索算法;混沌扰动;动态分组

0 引言

20世纪以来，各种启发式算法出现，包括粒子群算法(PSO)[1]、遗传算法(GA)[2]、蝙蝠算法(BA)[3]、布谷鸟算法(CS)[4]等.

CS算法是一种新型的启发式算法，自提出开始便受到学术界的广泛关注，并不断得以改进.如王李进等[5]给出了基于逐维改进的布谷鸟算法，将对解的寻优从全局转移到了每一个维度，并通过仿真实验验证了改进的有效性；Wang等[6]给出了基于可变缩放因子的布谷鸟算法，通过改变缩放因子的方式影响解的寻优步长与寻优方向，一定程度上提高了CS算法的求解速度；Xue等[7]利用动态分组策略改进CS算法，给出了基于动态分组的改进布谷鸟算法(DGCS)，即对每次寻优的解根据适应值进行分组，对于不同的分组采取不同的调整步长控制量，从而在较大程度上提高了CS算法的求解精度和求解速度.Wang等[8]利用混沌扰动策略改进CS算法，进一步提高了CS算法的性能.本文将使用动态分组策略与混沌扰动策略对CS算法进行改进.

1 布谷鸟算法

CS算法由Yang等[4]根据布谷鸟寄生育雏的特殊繁殖方式给出：寄生育雏即布谷鸟会将自己的鸟蛋产入其他鸟类的鸟巢中让鸟巢主人为自己孵化幼鸟，鸟巢主人能有一定的概率发现布谷鸟蛋，这时它会毁坏布谷鸟蛋或者放弃自己的鸟巢.

CS算法步骤[4,9-10]总结如下：

1) (初始化)随机生成n个解，记录其中适应值最优的解；

2) (循环体)使用Lévy-flights随机游动公式(1)生成新的解集并与旧解集比较，保留较优的解，记为lk=[xk,1,xk,2,…,xk,n]；

(1)

3) 对lk中的每个解都随机生成随机数r～U(0,1)，如r>0.25，对解使用式(2)进行改变；保留适应值较优的解到下一代，记为jk=[xk,1,xk,2,…,xk,n];

xk+1,i=xk,i+r(xk,j-xk,e).

(2)

其中,r～U(0,1)是缩放因子；xk,j、xk,e是第k代的两个随机解.

4) 判断此时是否满足算法结束条件.满足则输出最优解与最优适应值；否则，执行步骤2.

2 基于动态分组与混沌扰动的改进布谷鸟算法

2.1 混沌扰动策略

启发式算法，包括CS算法的求解过程会依赖种群中其他解的信息，一旦陷入局部收敛就会降低种群的多样性从而影响算法的求解速度和精度.CS算法中引入混沌扰动可以有效地提高种群多样性，从而避免种群陷入局部收敛.

混沌扰动是在原解上加一个服从混沌分布的随机量[11]，如式(3)所示：

(3)

式中N(0,1)服从标准正态分布.

设立记录板，记录算法每代的最优解的适应值，如果连续3代适应值变化极小，则判定为陷入局部收敛，此时用当前最优解替代当前最差解，用式(3)更新剩下的解，比较更新前后解集的适应值，保留较优的解到下一代，并选出最优解至记录板.

2.2 动态分组策略

(4)

2) 适应值劣于fa的解为第二组，用式(5)更新步长控制向量的对应分量.

(5)

2.3 改进算法的流程

1) (初始化) CS算法的解空间维数为m，算法最大迭代次数为K，发现概率为Pa∈[0,1]，最低阈值q，适应值连续不明显改变代数a，随机生成n个解，记录其中适应值最优的解为x0,b,其最优适应值fmin,b∈{1,2,…,n]；记录板记录fmin.

2) (循环体)保留上一代的最优解，记为xk-1,b.式(4)和(5)改变步长控制向量，使用式(1)生成新的解集并与旧解集lk-1= [xk-1,1,xk-1,2,…,xk-1,n]比较.保留较优的解，记为lk=[xk,1,xk,2,…,xk,n]；

3) 对lk中的每个解都随机生成随机数r～U(0,1)作为鸟巢主人发现布谷鸟蛋的概率，即发现概率，如r>Pa，对解使用式(2)进行改变；否则保留此解不变.比较更新前后的解，并保留适应值较优的解到下一代，记为jk=[xk,1,xk,2,…,xk,n];

4) 计算jk中最优解xk,b与最优适应值fmin，判断此时是否满足算法结束条件.满足则输出xk,b与fmin；否则，执行步骤5.

3 实验与结果

3.1 实验设计

为了验证ICS改进策略的有效性，对ICS，CS，DGCS和CCS[8]设计仿真实验进行性能比较.仿真环境为Windows 8，内存8.00 GB，机器主频2.90 GHz，MATLAB R2016a.各算法参数的设计见表1.

表1 参数设计表Tab. 1 Table of parameter design

表2 测试函数参数

本文使用如下5个基准测试函数进行测试，各函数的参数列于表2.

3.2 实验结果分析

3.2.1 4种算法的平均收敛曲线对比

在种群规模为20，最大迭代次数相同，CS，DGCS，CCS和ICS分别独立运行30次的前提下，4种算法对5个测试函数的收敛曲线见图1所示.其中当前最优适应值的对数平均值(MBFL)计算公式为：

式中，G为算法的运行次数，gbesti(t)为第i次运行第t次迭代的当前最优值.

由图1各曲线的变化可见，在算法迭代次数相同的情况下，ICS相比CS,DGCS和CCS有更快的收敛速度与更高的求解精度.

图1 4种算法求解测试函数的平均收敛曲线对比Fig. 1 Comparison of average convergence curves of test functions by four algorithms

3.2.2 4种算法的全局最优值对比

求解规模为20，迭代次数为500，4种算法分别独立运行30次，比较各自的全局最优值.依据表3中4种算法求解测试函数的最小值、最大值和平均值可知，ICS算法较CS，DGCS和CCS算法有更高的收敛速度、求解精度.从4种算法的标准差比较则可看出ICS算法相比CS，DGCS和CCS算法有更高的稳定性.

表3 4种算法求解函数的最小值、最大值、平均值对比Tab. 3 The minimum, maximum, average value comparison of the four algorithms for solving test functions

表4 4种算法的平均迭代次数对比

3.2.3 4种算法的平均迭代次数对比

求解精度为e-10，4种算法独立运行30次，每次算法所得最优适应值精度达到e-10记录当前迭代次数，比较30个迭代次数的平均值，结果如表4所示.

可见，在求解精度相同的情况下，ICS算法相对CS，DGCS和CCS算法能更快地得到目标精度，即ICS算法具有更快的求解速度.

4 结论

本文给出基于动态分组与混沌扰动的改进布谷鸟算法,用于提高CS算法的收敛速度与求解精度.仿真实验证明，ICS算法相对CS，DGCS与CCS算法有更高的收敛速度、求解精度及稳定性.

[1] EBERCHART R C, KENNEDY J. Particle swarm optimization[C]//Proceedings of the IEEE International Conference on Neural Networks. Perth： IEEE，1995:1942-1948.

[2] GOLDBERG D E. Genetic algorithms in search, optimization, and machine learning[M]. San Francisco： Addison-Wesley Pub. Co.，1989:2104-2116.

[3] YANG X S. A new metaheuristic bat-inspired algorithm[J]. Nature Inspired Cooperative Strategies for Optimization，2010,284:65-74.

[4] YANG X S, DEB S. Cuckoo search via Lévy flights[C]. Proceedings of World Congress on Nature & Biologically Inspired Computing. Coimbatore: IEEE,2009:210-214.

[5] 王李进,尹义龙,钟一文.逐维改进的布谷鸟搜索算法[J].软件学报,2013(11):2687-2698.

[6] WANG L J, YIN Y L, ZHONG Y W. Cuckoo search with varied scaling factor[J]. Frontiers of Computer Science,2015,9(4):623-635.

[7] XUE Y G, DENG H W. The cuckoo search algorithm based on dynamic grouping to adjust flight scale[J]. Applied Mechanics and Materials,2014,543:1822-1826.

[8] WANG G G, DEB S, GANDOMI A H, et al. Chaotic cuckoo search[J]. Soft Computing,2016,20(9):3349-3362.

[9] VALIAN E, MOHANNA S, TAVAKOLI S. Improved cuckoo search algorithm for global optimization[J]. International Journal of Communications and Information Technology，2011，1(1)：31-44.

[10] 薛益鸽.改进的布谷鸟搜索算法及其应用研究[D].重庆：西南大学，2015.

[11] YANG M, HUANG H X, XIAO G Z. A novel dynamic particle swarm optimization algorithm based on chaotic mutation[C]//Second International Workshop on Knowledge Discovery and Data Mining. Moscow: IEEE,2009:656-659.

ImprovedCuckooAlgorithmBasedonDynamicGroupingandChaoticDisturbing

XUE Yige

(College of Information Engineering, Wenzhou Business College, Wenzhou 325035, China)

The cuckoo algorithm (CS) is a new heuristic intelligent algorithm, which has the problem that the solving speed is not fast enough and the solving accuracy is not high enough. An improved cuckoo algorithm(ICS) based on dynamic grouping and chaotic disturbing is given, and the performance of which is tested by 5 classical test functions. The simulation results show that the ICS has faster speed and higher precision than the CS.

cuckoo search algorithm; chaotic disturbing; dynamic grouping

2017-02-10

浙江省教育厅科研项目(Y201636359).

薛益鸽(1990-)，男，助教，硕士，主要从事计算智能研究.E-mail:15968723096@163.com

10.3969/j.issn.1674-232X.2017.06.020

TP301.6

A

1674-232X(2017)06-0676-05