一种改进的布谷鸟搜索算法

田野，方明

（长春理工大学计算机科学技术学院，长春 130022）

一种改进的布谷鸟搜索算法

田野，方明

（长春理工大学计算机科学技术学院，长春 130022）

布谷鸟搜索算法是近年来提出的一种新的仿生智能算法，算法主要通过模拟布谷鸟的繁殖习性对问题进行最优求解。针对布谷鸟搜索算法中解的发现及放弃策略的随机性问题，将解的适应度情况同时考虑进来，并在此基础上提出一种基于解的优劣度的改进布谷鸟搜索算法。算法充分考虑解的适应度，并将适应度作为评估是否被放弃的一个标准，从而使得适应度较好的解更有可能被保留下来，提高算法的求解质量。实验结果表明新算法在求解质量以及收敛速度方面，都比标准的布谷鸟搜索算法有了一定的提高。

人工智能；全局优化；布谷鸟搜索算法；适应度

智能优化算法是通过模拟自然界的生物运动或者自然现象来设计求解实际复杂优化问题的新型算法，如遗传算法［1］、粒子群优化算法［2］、人工蜂群算法［3］等都属于智能优化算法。布谷鸟搜索（Cuckoo Search，CS）算法是2009年由Yang和Deb提出的一种新的智能优化算法［4-5］，其原理是对布谷鸟的繁殖习性进行模拟，根据布谷鸟寄生育雏的特点，对问题的最优解进行有效搜索。由于CS算法具有参数少、简单易实现等优点，很快吸引了众多学者的关注和研究热情［6-8］。

CS算法的高效性主要源于它的莱维飞行（Lévy flights）随机游动和偏好随机游动。而在偏好随机游动过程中，算法以一定的概率随机发现需要被放弃，并且重新生成的解，这种随机方式使得质量较好的解可能被放弃。针对这一问题，文中考虑将解的适应度情况作为是否放弃解的评价标准，提出一种基于解的优劣度的改进布谷鸟搜索（Improved Cuckoo Search，ICS）算法，来提高算法的性能。

1 布谷鸟搜索算法

CS算法通过模拟某些种属布谷鸟的寄生育雏习性有效的求解最优化问题。布谷鸟最为特殊的习性是寄生育雏［4］。某些种属的布谷鸟将自己的卵偷偷产入宿主巢穴，由于布谷鸟后代的孵化时间比宿主的幼雏早，孵化的幼雏会本能的破坏同一巢穴中其他的卵（推出巢穴）并发出比宿主幼雏更响亮的叫声。很多宿主通过后代的叫声大小判断其健康程度，而健康后代获得的食物较多，进而拥有更高的存活率。在某些情况下，宿主也会发现巢穴中的陌生卵，这时，宿主将遗弃该巢穴，并选择其他地方重新筑巢。在与宿主不断的生存竞争中，布谷鸟的卵以及幼雏叫声均朝着模拟宿主的方向发展，以对抗宿主不断进化的分辨能力。

在此生物学基础上，YANG和Deb对其寄生育雏行为提出了三个假设，并依据该假设给出了布谷鸟算法［5］。

假设1：每只布谷鸟每次只产一个鸟蛋随机放进某个鸟巢；

假设2：存有布谷鸟蛋的最好的鸟巢会被保留到下一代；

假设3：鸟巢数量固定，并且布谷鸟蛋被鸟巢的主人以一定的概率发现。

由此得到CS算法的步骤描述如下：

Step 1.初始化。随机产生N个鸟窝（即问题的解），其位置表示为，记录最优的解；

Step 2.利用莱维飞行进行解的位置更新，获取新的候选解的位置，利用贪心选择策略保留更好的解；

Step 3.根据发现概率Pa，丢弃部分解，并用偏好随机游动产生新的解替代丢弃的解；

Step 4.选择当前最好的解，如果满足终止条件，则输出最好的解；否则，返回Step 2继续迭代。

2 改进的布谷鸟搜索算法

在CS算法中，为了提高种群的多样性，算法以Pa概率放弃一部分解，并通过偏好随机游走的方式生成新的解，这种策略有效地加强了算法的全局搜索能力。但是，在以Pa概率发现并放弃解的时候，算法采用了随机的方式，即对于每个解生成一个0到1之间的随机数，如果该随机数大于发现概率Pa，则该解被放弃，这种随机方式可能导致适应度较好的解被放弃掉，而适应度较差的解得以保留的问题，影响算法收敛速度和解的质量。因此文中ICS算法的主要思想是：在发现并放弃解的时候，将解的适应度同时考虑进来，将解的适应度作为评判是否放弃解的一个度量。

首先，根据解的适应度，计算解的选择概率，公式如下：

其中，Pi表示第i个解的选择概率，Fiti是第i个解的适应度，gBest和gWorst分别表示目前为止最好的解和最差的解的适应度值。从公式（1）中可以看出，解的质量越好，适应度越好（适应度值越小），则解的选择概率也就越小，反之亦然。现在将适应度考虑到以Pa概率发现并放弃解的策略中，如公式（2）所示：

其中，ri表示第i个解对应的随机数，取自［0，1］之间，r'i是经过计算后的新随机数，如果r'i＞Pa，则该解被发现并放弃，通过偏好随机游走的方式生成新的解，否则，保留该解。根据公式（2），按以下两种情况来分析：

第一种情况：ri＜Pa

如果第i个解适应度较好，则Pi值相对较小，因此该解仍然以较小的概率被发现并放弃；

如果第i个解适应度较差，则Pi值相对较大，因此可能增加该解被发现并放弃的概率；

第二种情况：ri≥Pa

如果第i个解适应度较好，则Pi值相对较小，因此可能降低该解被发现并放弃的概率；

如果第i个解适应度较差，则Pi值相对较大，因此该解可能以较大的概率被发现并放弃；

由于r是随机数，所以在放弃解的时候无法辨识其适应度情况，而Pi值的作用就是用来帮助调节新的随机数r'i的，即调节解的发现放弃概率。总的来说，解的适应度越好，Pi值越小，则会降低该解被放弃的概率；解的适应度越差，Pi值越大，则会增加被放弃的概率。整个改进算法流程可以描述为如下算法：

表1 测试函数

3 实验

本节中，将文中提出的ICS算法和标准的CS算法［1］在一些标准测试函数上进行对比分析，验证ICS算法的有效性。

3.1 测试问题

为了测试ICS算法的性能，文中列举了一些具有不同复杂程度的基准函数作为测试问题，这些测试问题包含单模和多模，最优值均为0。表1中列出了函数的表达形式、搜索空间及误差阈值。

3.2 实验结果

本文中的ICS算法和标准的CS算法均采用Matlab编程。为了更好地观察改进算法和标准CS算法在收敛速度和解的质量的对比情况，文中采取了两组实验，第一组实验主要验证改进算法的求解质量；第二组实验侧重于算法的收敛速度分析。

3.2.1 实验一

在本小节实验中，将本文提出的ICS算法与标准的CS算法进行比较。其中测试问题的维度D均为30，群体规模N=D，发现概率为Pa=0.25，最大函数评价次数FES=10000×D，每个算法独立运行30次，表2列出了两种算法针对五个测试函数获得的最优解平均值及标准差。

表2 CS和ICS关于最优解均值对比

从上表中可以看出，对于所有的测试问题，改进的ICS算法在最优解的均值和方差都获得了比标准的CS算法更好的结果，这说明无论是在求解质量、求解精度及稳定性方面，ICS算法都有了一定的提高。主要原因是因为在ICS算法中，对于发现及放弃解的过程中，充分考虑到了解的适应度情况，降低了适应度更好的解被放弃的可能，使得算法的整体求解质量有了提高。

3.2.2 实验二

本节实验主要是针对两种算法的收敛速度进行了对比分析。算法参数设置、终止条件及实验环境和3.2.1节相同。表3给出了两种算法收敛于指定误差阈值所需的平均函数评价次数和标准差及成功率（success rate，SR）。“-”表示算法在终止时未能收敛于指定误差阈值，平均函数评价次数和标准差只考虑算法执行成功的情况。ICS算法和标准的CS算法在成功次数上相差不大，几乎一样。此外，当收敛失败时，两种算法的平均函数评价次数都是一样的，因此不对问题f2和f5的结果作对比分析。对于Ackley测试问题，CS算法的成功率为83.33%，而ICS算法获得了100%的成功，并且ICS算法在平均函数评价次数及标准差上，都远远优于CS算法。对于其他测试问题，两种算法都以相同的成功次数收敛于指定误差阈值，但从平均函数评价次数上来看，ICS算法以较快的速度收敛。而从方差可以看出，ICS算法收敛时的函数评价次数相对更稳定。

表3 CS和ICS收敛于指定误差阈值的平均函数评价次数

从以上两组实验可以看出，由于改进的ICS算法在解的发现放弃过程中，充分利用了解本身的优劣情况，使得质量较好的解更有机会得以保留下来，因此在整体上提升了最优解的质量，并且提高了算法的收敛速度。

4 结论

本文针对标准布谷鸟搜索算法在解的发现放弃过程中存在的问题，将解本身的质量考虑进来，提出了基于解优劣特征的改进布谷鸟搜索算法ICS，算法将解的优劣特征作为被发现并放弃的度量标准，有效地保障了适应度较好的解能够被保留下来的可能性，从而提高算法的求解质量及收敛速度。

文中采用了具有不同难度的基准优化问题，通过两组对比实验分别来验证算法在求解质量和收敛速度上的性能，并且和标准的CS算法进行了比较。结果表明改进的ICS在求解质量及收敛速度上较标准的CS算法都得到了提高。

［1］Holland J H.Adaptation in natural and artificial systems［M］.AnnArbor：UniversityofMichigan Press，1975.

［2］KennedyJames，EberhartRussell.Particleswarm optimization［C］.Proceedings of the IEEE international conference on neural networks，Perth，Australia，1995（4）：1942-1948.

［3］Karaboga Dervis，Basturk Bahriye.A powerful and efficient algorithm for numerical function optimization：artificial bee colony（ABC）algorithm［J］.Journal of Global Optimization，2007，39（3）：459-471.

［4］Yang Xin She，Deb Suash.Cuckoo search via Lévy flights［C］.Proceedings of the World Congress on Nature and Biologically Inspired Computing（NaBIC 2009）.IEEE Publications，USA，2009：210-214.

［5］Yang Xin She，Deb Suash.Engineering optimisation by cuckoo search［J］.International Journal of Mathematical Modeling and Numerical Optimisation，2010，1（4）：330-343.

［6］Burnwal Shashikant，Deb Suash.Scheduling optimization of flexible manufacturing system using cuckoo search-based approach［J］.International Journal ofAdvancedManufacturingTechnology，2013，64（64）：951-959.

［7］Zhou Yongquan，Ouyang Xinxin，Xie Jian.A discrete cuckoo search algorithm for travelling salesman problem［J］.International Journal of Collaborative Intelligence，2014，1（1）：68-84.

［8］Civicioglu Pinar，Besdok Erkan.A conceptual comparison of the Cuckoo-search，particle swarm optimization，differential evolution and artificial bee colony algorithms swarm optimization，differential evolution and artificial bee colony algorithms［J］.Artificial Intelligence Review，2013，39（4）：315-346.

An Improved Cuckoo Search Algorithm

TIAN Ye，FANG Ming
（School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022）

Cuckoo search（CS）algorithm is a new nature-inspired intelligent algorithm which simulates the breed behavior of the cuckoo species to solve the global optimization problems.In this paper，an improved cuckoo search（ICS）algorithm based on the fitness of the solution is presented to overcome the randomness on finding and abandoning one solution.In the presented algorithm，the fitness of the solution is considered and as the abandon metric，which makes the better solution be likely to survive，and improve the performance of the algorithm.The experiment results show that ICS is better than CS in not only the solution quality，but also the convergence speed.

artificial intelligence；global optimization；cuckoo search algorithm；fitness

TP18

A

1672-9870（2017）01-0115-04

2016-07-09

吉林省科技发展计划、吉林省公共计算平台资助（20130101179JC-11）；吉林省自然科学基金（20130101054JC）

田野（1979-），男，博士，讲师，E-mail：tianye@cust.edu.cn