基于逐维改进的自适应步长布谷鸟搜索算法

基于逐维改进的自适应步长布谷鸟搜索算法

作者：任璐 李海洋 贺兴时

来源：《河北科技大学学报》2015年第05期

摘要：步长的选取对于布谷鸟搜索算法的收敛速度与运算结果的精度起着关键作用。提出了一种基于逐维改进的自适应步长布谷鸟搜索算法。首先，在原始自适应步长布谷鸟搜索算法中，当上一代鸟窝位置为最优位置时，步长不再更新，则简单修正原有的步长让其更新；其次，将逐维更新评价策略引入修正后的自适应步长布谷鸟搜索算法。实验结果表明，该算法不仅平衡了全局寻优能力和寻优精度之间的矛盾而且具有较好的收敛速度。

关键词：算法理论；布谷鸟搜索算法；逐维改进；自适应步长；进化曲线

中图分类号：TP186文献标志码：A

Abstract：The choice of step length plays an important role in convergence speed and precision of Cuckoo search algorithm. In the paper， a selfadaptive step Cuckoo search algorithm based on dimensional improvement is provided. First， since the step in the original selfadaptive step Cuckoo search algorithm is not updated when the current position of the nest is in the optimal position， simple modification of the step is made for the update. Second，

龙源期刊网 http://www.qikan.com.cn

evaluation strategy based on dimension by dimension update is introduced to the modified selfadaptive step Cuckoo search algorithm. The experimental results show that the algorithm can balance the contradiction between the global convergence ability and the precision of optimization. Moreover， the proposed algorithm has better convergence speed.

Keywords：theory of algorithm； Cuckoo search algorithm （CS）； dimension by dimension improvement； selfadaptive step； evolutionary curre

近几年，各种启发式算法如粒子群算法[1]、蚁群算法[2]、遗传算法[3]已经成为智能计算领域的研究热点。剑桥大学的YANG等[4]于2009年提出了一种启发式算法——布谷鸟搜索（Cuckoo Search， CS）算法，该算法模拟了自然界中布谷鸟寻找合适的鸟窝孵化鸟蛋的过程。算法中布谷鸟首先选择一系列鸟窝，通过比较和搜寻，最终找到一个较优的鸟窝来孵化自己的鸟蛋。布谷鸟搜索算法的特点是采用 Lévy飞行模式以及实时参考当前位置从而找到最优鸟窝，这是一种高效的寻优模式，具有易搜索、参数少、路径优、多目标问题求解能力强等优点[57]。2011年，EHSAN等[8]将布谷鸟算法应用于神经网络；2012年，VIPINKUMAR[9]将布谷鸟算法应用到了人脸识别；2013年，有许多学者将布谷鸟算法应用于整数规划[10]、多阈值图像分割[11]、求解置换流水区间等调度问题[12]。近些年来对于布谷鸟搜索算法也有大量的改进算法[1318]，提高了布谷鸟搜索算法的性能。

在基本CS 算法中，步长是通过Lévy飞行随机产生的，在搜索过程中，随着步长的增大，全局寻优能力增强，但是搜索精度却降低了，甚至有时会出现震荡现象；若步长

龙源期刊网 http://www.qikan.com.cn

减小，则取到相反的结果。因此，采用Lévy飞行产生步长在具有随机性的同时缺乏了自适应性。针对这个问题，郑洪清等＼[19＼]提出了一种自适应步长布谷鸟搜索算法（DCS），该算法根据不同阶段的搜索结果，自适应动态调整步长的大小，调节了布谷鸟搜索算法在全局寻优能力和寻优精度之间的关系，使得算法具有更好的自适应性。逐维改进的布谷鸟搜索算法通过将逐维更新评价策略引入到偏好随机游动中，达到了避免维间互扰的效果（RCS）[20]。该算法中的缩放因子r取＼[-1，1＼]区间的均匀分布随机数，使算法可以达到双向搜索，提高局部搜索能力。与此同时，算法利用解的本身信息，将原来的双随机解改为一个随机解与上一迭代中的最优解，有利于逐维改进策略进行局部搜索。

河北科技大学学报2015年第5期任璐，等：基于逐维改进的自适应步长布谷鸟搜索算法 然而，自适应步长布谷鸟搜索算法在运行过程中，若当前位置为最优位置时步长就不再更新，不能够有效地使算法达到自适应的目的；同时该算法只对步长进行改进，无法避免维间互扰，也没有充分利用解的本身信息，不利于逐维改进策略进行局部搜索。

本文提出了一种基于逐维改进的自适应步长布谷鸟搜索算法（RDCS）。首先，针对步长更新问题做出了相应的改进，即判断di是否为零。当其为零时， 对di赋于0到1之间的一组随机数，使步长可以得到更新并且也增加了解的多样性。其次，将逐维更新评价策略引入改进后的自适应步长布谷鸟搜索算法，使算法的搜索能力进一步提高。RDCS算法能调节全局寻优能力和寻优精度之间的关系，同时避免了维间互扰，最终提高算法的局部搜索能力。实验结果表明，RDCS算法在收敛速度方面比原始的布谷鸟搜索算法以及RCS算法和DCS算法具有更好的效果。

1基本布谷鸟搜索算法

龙源期刊网 http://www.qikan.com.cn

布谷鸟是一种聪明的鸟类，它们用一种独特的方式来繁殖自己的后代。布谷鸟将自己的卵产在义亲鸟的鸟窝中，由义亲鸟代为孵化和育雏，并且为了保证孵化率，它会将义亲鸟的蛋扔出鸟巢。

布谷鸟搜索算法先要设定以下3个理想的状态[4]：

1）每一只布谷鸟在一个时刻只能产一个卵，并随机选择鸟窝孵化；

2）在随机选择的一组鸟窝中，拥有最好鸟蛋的鸟窝将会被保留到下一代；

3）鸟窝数量n是固定的，并且宿主鸟发现一个外来鸟蛋的概率为pa。在这种情况下，宿主鸟将扔掉这些外来鸟的卵或直接放弃它的窝，去一个新的地方建立新窝。

从实现的角度看，用每一只布谷鸟的卵所在的鸟窝位置代表一个解，每一只布谷鸟只能产一个卵（因此只有一个解），目标是使用新解和更好的解类替代一个较差解。在这种情况下，卵、鸟窝和布谷鸟之间是没有差别的，每一个鸟窝都有一个卵，也可以表示有一只布谷鸟。

其中m为算法的维数。根据式（4）实现自适应动态调整步长。当第i个鸟窝位置与最优位置的距离越接近，步长则越小，反之步长越大。这样，本次迭代的移动步长就可以根据上一次迭代的结果来动态更新，具有更好的自适应性。但是仅仅只对步长进行改进，无法避免维间互扰，也没有充分利用解的本身信息。因此将逐维更新评价策略引入改进后的自适应步长布谷鸟搜索算法，即首先将双随机解的差改为一个随机解与上一次迭代中最优解的差，利用了解本身的信息；其次将r取为[-1，1]区间的均匀分布随机数，达到

龙源期刊网 http://www.qikan.com.cn

双向搜索，提高局部搜索能力，即使用公式x（t+1）i=x（t）i+r（x（t）j-x（t）i）进行更新，其中r是＼[-1，1＼]区间的随机数，x（t）i表示第t代的随机解。

3改进算法的步骤

步骤1（初始化） 随机生成n个鸟窝位置，发现概率pa，精度tol，设定搜索空间的维数nd与解的上下界ub与lb，最大步长stepmax与最小步长stepmin，找出当前最优位置nbest。

步骤2（循环过程） 保留上代最优位置x（t）b，利用改进的自适应步长来更新步长，再利用Lévy飞行对其他解进行更新，得到一组解。将这组解与上一代的解进行比较，用新解中较好的解替换上一代中较差的解，从而得到一组新解x（t+1）i，i=1，2，3，…，n。

步骤3用服从均匀分布＼[-1，1＼]的随机数r作为缩放因子与发现概率pa比较，若r>pa则不改变解，否则用x（t+1）i=x（t）i+r（x（t）j-x（t）i）来更新解，得到一组解。用这组解与上一代解进行比较，同时用这组接种好的解替代上一代中差的解，从而得到一组新解。

步骤4保留好的解。判断是否达到精度要求，满足则输出结果；若不满足，返回步骤2。

4仿真实验

龙源期刊网 http://www.qikan.com.cn

4.1实验设计

实验中算法参数设置鸟窝规模为25，pa=0.25，步长按式（2）与式（3）动态调整，偏好游走的步长则按式（4）来调整，各函数优化的参数如上文所示，用基本CS 算法、自适应步长布谷鸟搜索算法、逐维改进布谷鸟搜索算法、基于逐维改进的自适应步长布谷鸟搜索算法分别对上述测试函数的最小值寻优，最终结果为独立运行100次后的平均值。采用固定收敛精度目标值，评估算法达到该精度所需的迭代次数。

4.2实验结果及分析

固定收敛精度tol=1.0e-5，算法独立运行100次，其中CS表示原始的布谷鸟算法、RCS表示逐维改进布谷鸟搜索算法、DCS表示自适应步长布谷鸟搜索算法、RDCS表示基于逐维改进的自适应步长布谷鸟搜索算法，实验结果如表1所示。

Ackley函数、Rastrigin函数为多峰值函数，RDCS的运行结果比RCS，DCS和CS均有所改善，并且可明显看出RDCS的迭代次数远远小于CS。Zakharov函数的效果尤为明显，RDCS迭代了3 050次就取得了最优值，而CS却迭代了6 800次。Hump函数、Sphere函数、Sum Squares函数为单峰值函数，RDCS的最小适应值与平均适应值比RCS，DCS和CS都小了许多，迭代次数也有明显的减少。

图1-图6是Ackley函数、Rastrigin函数、Zakharov函数、Hump函数、Sphere函数与Sum Squares函数的最优值与迭代步数所对应的进化曲线。对应着各图与表1可以看出，RDCS在Ackley函数测试过程中虽然总共迭代了10 950次，但它在

龙源期刊网 http://www.qikan.com.cn

500次时就已经非常接近最优解，而其他3种算法则需要更多的次数来迭代。从Rastrigin函数也可看出类似的结果。Zakharov函数RDCS只迭代了200次就非常接近最优值，但是RCS，DCS和CS的迭代次数却达到了RDCS的2倍以上。Sphere函数与Sum Squares函数的图像很类似，但也明显可以看出RDCS的效果比其他3种算法好了很多。

5结语

将自适应步长布谷鸟算法引入逐维改进的布谷鸟算法中，对布谷鸟算法的步长、偏好游走中的缩放因子进行改进。相应算法RDCS加快了布谷鸟搜索算法的搜索速度，提高其计算精度，有效地提高了CS算法的收敛速度并改善解的质量。6个标准测试函数的测试结果表明，改进后的自适应步长布谷鸟搜索算法具有较快的收敛速度和较高的寻优精度。

参考文献/References：

[1]KENNEDY J， EBRHART R. Particle swarm optimization[C]//Proc IEEE Int Conf on NeuralNetworks.Perth：[s.n.]，1995： 19421948.

[2]GOLDBERG D E. Genetic Algorithm in Search， Optimization and Machine Learning [M]. Boston ： AddisonWesley Longman Publishing Co Inc， 1989.

[3]DORIGO M， BONABEAU E， THERAULAZ G. Ant algorithms and

龙源期刊网 http://www.qikan.com.cn

stigmergy [J]. Future Generation Computer Systems， 2000， 16（8）： 851871.

[4]YANG X S， DEB S. Cuckoo search search via Lévy

flights[C]//Proceedings of World Congress on Nature & Biologically Inspired Computing. [S.l.]： IEEE Press， 2009： 210214.

[5]YANG Xinshe， DEB S. Engineering optimization by Cuckoo search[J]. International Journal of Mathematical Modeling and Numerical，2010，1（4）： 330343.

[6]YANG Xinshe. NatureInspired Metaheuristic Algorithms[M].2nd

ed.[S.l.]： Luniver Press， 2010.

[7]YANG Xinshe， DEB S. Multiobjective Cuckoo search for design optimization[J]. Computers & Operations Research， 2011，10（9）： 19.

[8]EHSAN V， SHAHRAM M，SAEED T. Improved Cuckoo search search [J].International Journal of Artificial Intelligence & Applications （IJAIA），2011，3（2），3643.

[9]VIPINKUMAR T. Face recognition based on Cuckoo search search algorithm[J]. Indian Journal of Computer Science and Engineering，2012，3（3）：401405.

龙源期刊网 http://www.qikan.com.cn

[10]吴炅，周健勇. 整数规划的布谷鸟算法[J].数学理论与应用，2013，33（3）： 99106.

WU Jiong， ZHOU Jianyong. Cuckoo search algorithm for solving integer programming[J].Mathematical Theory and Applications，2013，33（3）：99106.

[11]柳欣妮，马苗.布谷鸟搜索算法在多阈值图像分割中的应用[J].计算机工程，2013，39（7）：274278.

LIU Xinni，MA Miao. Application of Cuckoo search algorithm in multithreshold image segmentation[J].Computer Engineering，2013， 39（7）：274278.

[12]刘长平，叶春明.求解置换流水车间调度问题的布谷鸟算法[J]. 上海理工大学学报，2013，35（1）：1720.

LIU Changping，YE Chunming.Cuckoo search algorithm for the problem of permutation flow shop scheduling[J]. Journal of University of Shanghai for Science and Technology，2013，35（1）： 1720.

[13]VALIAN E， MOHANNA S，TAVAKOLI S. Improved Cuckoo search algorithm for global optimization[J].International Journal of Communications and Information Technology， 2011， 1（1）： 3144.

龙源期刊网 http://www.qikan.com.cn

[14]冯登科，阮奇，杜利敏.二进制布谷鸟搜索算法[J].计算机应用，2013，33（6）： 15661570.

FENG Dengke， RUAN Qi， DU Limin. Binary Cuckoo search algorithm[J].Journal of Computer Applications，2013，33（6）： 15661570.

[15]胡欣欣.求解函数优化问题的改进布谷鸟搜索算法[J].计算机工程与设计，2013，34（10）： 36393642.

HU Xinxin.Improvement Cuckoo search algorithm for function optimization problems[J].Computer Engineering and Design， 2013， 34（10）： 36393642.

[16]王凡，贺兴时，王燕.基于高斯扰动的布谷鸟搜索算法[J].西安工程大学学报，2011，25（4）： 566569.

WANG Fan， HE Xingshi， WANG Yan.The Cuckoo search algorithm based on guassian distrubance[J].Jouranl of Xi’an Polytechnic University，2011， 25（4）； 566569.

[17]杜利敏，阮奇，冯登科.基于共辘梯度的布谷鸟搜索算法[J].计算机与应用化学，2013，30（4）：406410.

DU Limin， RUAN Qi， FENG Dengke.Cuckoo search algorithm based on conjugate gradient method[J].Computers and Applied Chemistry，2013，30

龙源期刊网 http://www.qikan.com.cn

（4）： 406410.

[18]李明，曹德欣.混合CS算法的DE算法[J].计算机工程与应用，2013，49（9）：5760.

LI Ming， CAO Dexin. Hybrid optimization algorithm of Cuckoo search and DE[J].Computer Engineering and Applications， 2013， 49（9）：5760.

[19]郑洪清，周永权.一种自适应步长布谷鸟搜索算法[J].计算机工程与应用，2013，49（10）：6871.

ZHENG Hongqing， ZHOU Yongquan.Selfadaptive step Cuckoo search algorithm[J].Computer Engineering and Applications，2013，49（10）：6871.

[20]王李进，尹义龙，钟一文.逐维改进的布谷鸟搜索算法[J].软件学报，2013，24（11）：26872698.

WANG Lijin， YIN Yilong， ZHONG Yiwen. Cuckoo search algorithm with dimension by dimension improvement[J].Journal of Software，2013，24（11）：26872698.