基于协同进化布谷鸟搜索算法

王庆喜++朱丽华

摘要：在布谷鸟搜索算法的基础上，通过引入协同进化策略，提出了一种协同进化布谷鸟搜索算法，该算法对高维函数优化问题采用分而治之的方式把高维问题分解为若干个低维问题，各低维问题协同进化。改进提升了算法的搜索能力，提高了算法的有效性。

关键词：布谷鸟搜索算法；协同进化策略；维数灾难

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2017）04-0233-02

Cuckoo Search Algorithm Based on Co-evolution

WANG Qing-xi， ZHU Li-hua

（School of Computer Science & Information Engineering， Anyang Institute of Technology， Anyang 455000， China）

Abstract： based on cuckoo search algorithm， we propose a collaborative cuckoo search algorithm by introducing the cooperative strategy， the algorithm solves the algorithm of high dimensional optimization problems using the way that the high dimensional problem is decomposed into several low dimensional problems， and the low dimensional problems co evolution. The improved algorithm improves the searching ability of the algorithm and improves the algorithm's effectiveness.

Key words： Cuckoo search algorithm； co-evolution strategy； Curse of dimensionality

1 背景

智能算法是一種模仿自然界生物机理的算法，具有自学习、自组织和自适应性，其有效性被多为学者证明，并且遗传算法和粒子群优化算法已经被应用到在高维优化问题[1-2]。布谷鸟搜索算法从2009年Xin-She Yang开发出来以后，已经成功应用到多个领域[3-5]，布谷鸟搜索算法在求解低维优化问题时，通常高效可靠，但是在求解高维优化问题时，其优化效果大幅下降。因此本文引入协同进化策略，提出了优化高维问题的协同进化布谷鸟搜索算法。

2 布谷鸟搜索算法

2.1 算法原理

布谷鸟的繁殖是具有侵略性的，它们把鸟蛋下到其他鸟类的鸟窝中，并且通过把其他鸟的鸟蛋移出鸟窝的方式提高自己后代的孵化概率[3]。另一方面，宿主鸟也进化出识别外来鸟蛋的能力，当其识别出外来鸟蛋时，会将外来鸟蛋推出鸟窝保证自己后代能够繁衍。因此布谷鸟在选择鸟窝时，会对鸟窝进行评估，如果感觉可能被宿主鸟发现的话，就会放弃当前鸟窝。

研究显示[4]许多动物和昆虫的飞行路径是一种随机行走，因为下一步决定于两个因素：当前位置和到下一个位置的跃进概率，并且通过数学建模发现，其飞行行为呈现出莱维飞行的特点。莱维飞行是一种随机行走，其步长是根据重尾分布的概率分布，大量行走之后，从原来的随机游走的距离趋向于一个稳定的分布

2.2 算法描述

在布谷鸟搜索算法中，每一个鸟窝代表一个解决方案（解），每一个布谷鸟鸟蛋代表一个新的解决方案（新解）。布谷鸟搜索算法[5]采用新的比较好的解决方案代替一个鸟窝中不太好的解决方案，经过若干次的迭代后，找到最优的解决方案。

在优化单目标问题时，每一个布谷鸟一次选择一个鸟窝下一个蛋；在迭代过程中，最好的鸟窝（解决方案）会被保留到一下代，而不好的鸟窝会被新的鸟蛋（解决方案）替代；宿主鸟窝数量是固定的，宿主鸟发现外来鸟的概率也是固定的，为了简单，该概率取值0.25。

鸟窝位置更新公式：

其中[α]>0表示步长，Levy表示莱维飞行，其值由莱维分布决定：

3 协同进化布谷鸟搜索算法

目前，大多数优化算法都是针对低维问题提出的，但是优化问题的规模和复杂度越来越大，解决低维优化问题的算法已经不能满足大规模高维度优化的需求。

虽然原始布谷鸟搜索算法已经被广泛地应用于函数优化，但是对于高维函数，算法优化性能急剧下降。为了使用布谷鸟搜索算法求解高维函数优化，必须对高维函数问题进行降维处理，本文采用协同进化策略实现降维。

3.1 协同进化策略

协同进化策略[6]是指通过将问题分解的方式解决大规模问题的一种策略，是一种分而治之的方法。在智能优化算法中，协同进化策略将一个高维搜索空间分解成多个低维的子空间，每个子空间作独立进化，并协同组成个体，进行适应度值计算。本文把d维向量分割成d个一维向量，即每一维都分解成一个子空间。在每一次迭代中，这些子空间的变量独立进化，在得到子空间的最优值后，将其通过当前最优解传给其他子空间，从而协同得出最终的全局最优解。

3.2 数学符号

假定使用种群规模为n的布谷鸟搜索算法来优化d维函数。

[xi，j]表示第i个鸟窝在第j维（第j个子空间）上分量的值。

[x（t）i（j，xi，j）]表示向量[x（t）i]第j个元素被[xi，j]替换后的向量。

b表示目前最佳鸟窝，即当前最优解。

p0表示宿主鸟发现外来蛋的概率

3.3 适应度值计算与比较

协同进化的鸟窝是分割开的，不再是一个完整的d维鸟窝向量，因此其鸟窝适应度值计算和原始布谷鸟搜索算法中的鸟窝适应度值计算存在差异。

假设在t次迭代时，第j个子鸟窝的第i个鸟窝的适应度值计算采用的向量为：第j个分量取[xi，j]，其余d-1个分量则取当前第i个鸟窝的其他n-1维的值，记为[x（t）i（j，xi，j）]。

3.4 鸟窝位置比较规则

令[x（t+1）i=x（t）i（j，xi，j）]，其中[j=1，2，…，d]

当[f（x（t+1）i）

从鸟窝比较规则可知：每个鸟窝在进化过程中始終保持最佳，而变量采用子空间的分量外，其余都采用了对应鸟窝的当前最佳分量，因此协同策略对更新后的鸟窝分量都进行适应度值评估，提高了鸟窝（解）的多样性，提高了鸟窝之间的相互学习性。

3.5 CCS伪代码

综上所述，协同进化布谷鸟搜索算法的进化过程转变为多个变量的协同进化，最大的改进是鸟窝的适应度值计算规则的修改，算法的伪代码如下所示：

4 结束语

通过引入协同进化策略的方式，对布谷鸟搜索算法进行改进，提升了算法的高维优化能力。系统进化策略把优化问题的高维搜索空间分解成多个一维的子搜索空间，子搜索空间协同进化，经过若干次迭代后获得高维优化问题的最优解。

参考文献：

[1] Dynamically Exploring Internal Mechanism Of Stock Market By Fuzzy-based Support Vector Machines With High Dimension Inputspace And Genetic Algorithm[J]. Expert Systems with Application， 2009 ，32（2）： 1240-1248.

[2] Kiranyaz S， Ince T， Yildirim A， et al. Fractional Particle Swarm Optimization in Multidimensional Search Space[J]. IEEE transactions on systems， man， and cybernetics， Part B. Cybernetics： A publication of the IEEE Systems， Man， and Cybernetics Society， 2010， 40（2）.

[3] S Walton， O Hasan， K Morgan， et al. Modify cuckoo search： A new gradient free optimisation algorithm[J]. Chaos， Solitons & Fractals， 2011， 44（6）： 710-718.

[4] Ehsan valiant， Saeed Tavakoli， Shahram Mohanna， et al. Improved cuckoo search for reliability optimization problems[J]. Computers & Industrial Engineering， 2013（64）： 459-468.

[5] Xinxin Ouyang， Yongquan Zhou， Qifang Luo，et al. A Novel Discrete Cuckoo Search Algorithm for Spherical Traveling Salesman Problem[J]. Applied Mathematics & Information Sciences， 2013， 7（2）： 777-784.

[6] Valian E， Mohanna S， Tavakoli S. Improved cuckoo search algorithm for feed forward neural network training[J]. Int J Artif Intell， 2011， 2（3）： 36-43.