精英反向学习的单纯形交叉布谷鸟搜索算法

摘要： 提出一种加强搜索能力的改进布谷鸟搜索算法，该算法采用精英反向学习策略促使Lévy Flights随机走动中的部分精英个体进行反向搜索，以避免搜索新个体的趋同性；并采用单纯形交叉操作在Biased随机走动中随机选择一个个体进行精细搜索，以降低搜索的盲目性以及低效性.另外，提出的算法采用混沌映射模型实现发现概率参数的自适应控制.仿真实验结果表明，该算法能够总体上有效改善算法的搜索能力和收敛速度.

关键词： 布谷鸟搜索算法；单纯形交叉；反向学习；混沌映射

0 引言

近年来，涌现诸如人工蜂群算法[1]、萤火虫算法[2]、群搜索算法[3]、布谷鸟搜索算法[4-5]等一些新颖算法.布谷鸟搜索算法(cuckoo search, CS)在求解函数优化问题上能获得较好的性能，同时具有运算简单和参数较少的特点，这些使得该算法已成为研究的热点.一方面，一些学者针对算法中的随机走动进行了研究与改进，文献[6-8]开展了Lévy Flights随机走动及其步长的相关研究工作；文献[9-10]则对加强Biased随机走动的搜索方式进行了研究.另一方面，一些学者通过混合其他优化算法以提高算法的搜索能力[11-13].

上述研究容易导致种群的同质性问题，而且种群中的当前最优个体无法从自身获得任何步长信息，这也限制了该个体的搜索能力.另外， Biased随机走动中的随机交叉搜索方式可能会导致盲目或者低效搜索问题.因此，笔者针对上述两个问题，引进解对称和单纯形交叉策略，以改善CS算法的收敛速度以及求精能力，并提出了精英反向学习的单纯形交叉布谷鸟搜索算法(elite opposition-based learning based simplex crossover cuckoo search algorithm, ESCS).

1 布谷鸟搜索算法

布谷鸟搜索算法是Yang和Deb[5-6]基于布谷鸟的繁殖策略而构建的算法.该算法主要包含3种部件：Lévy Flights随机走动、Biased随机走动以及贪婪选择.对于求解连续函数优化问题，CS算法首先在问题的解空间[xj,min,xj,max] (j=1,2,…,D)内随机初始化种群.

xi,j,0=xi,j,min+r(xi,j,max-xi,j,min), i=1,2,…,N，

式中:r∈[0,1]是缩放因子；N是种群大小.

在初始化之后，CS算法进入进化阶段.在进化过程中，Lévy flights随机走动和Biased随机走动被分别用于搜索新的个体.在每个随机走动之后，CS算法比较每个当前个体和新搜索个体的适应值，贪婪选择适应值较好的个体进入种群.

在Lévy flights随机走动中，种群以当前获得的最优个体为导向进行进化，其形式可表达为

式中:Xi,G、Xi,G+1和Xbest分别表示第G代的第i个当前个体、新个体以及当前最优个体；α0为缩放因子(取0.01)；μ,ν服从正态分布；β=1.5；以及

其中，Γ表示伽马(Gama)方程.

在Biased随机走动中，为了搜索新的个体，当前个体随机选择两个个体，各维按一定的概率接受它们的步长信息，具体如下：

式中，xm,j,G、xn,j,G表示第G代的第m和第n个解；r是缩放因子；pa∈[0,1]，是发现概率.

2 提出的改进算法

针对CS算法的搜索新个体的趋同性以及搜索低效率问题，提出一种基于精英反向学习的单纯形交叉布谷鸟搜索算法，这种算法采用精英反向学习、单纯形交叉以及发现概率pa的自适应控制策略.

2.1 精英反向学习

基于群体搜索的智能算法的迭代过程是一个搜索区域变换到另一个搜索区域的过程[14].反向学习(opposition-based learning, OBL)[15]是实现区域变换搜索的一种模式.文献[14]概括了4种常见反向学习模型.

式中:a、b为搜索空间的上下界；k为实数.

当k=0时，得解对称的一般反向学习模型，即

当k=1/2时，得区间对称的一般反向学习模型，即

当k=1时，得反向学习模型，即

当k=r时，r为[0,1]之间的随机数时，得到随机的一般反向学习模型，即

单纯形交叉(Simplex Crossover, SPX)[16]是一种基于交叉操作的局部搜索技术，常用于加强个体的求精，并呈现出潜在的性能[17].

算法1 SPX的流程如下.

步骤1：计算n个父个体xi(i=1,…,n)的中心位置O.

步骤2：生成n-1个随机数

为[0,1]之间的随机数.

步骤3：计算yi=O+ε(xi-O)，i=1,…,n，ɛ为扩张因子，ε=1.0.

步骤4：生成子个体C=yn+Cn.

2.3 发现概率pa的自适应控制

式(4)中的pa控制着个体获取外部信息的概率.越小的发现概率使得个体接受外部信息的机会越大，这有利于搜索的全局性；反之，有利于个体的求精能力.显然，动态控制pa有利于改善搜索部件的效率.因此，与文献[14]类似，ESCS采用高斯混沌映射模型控制pa参数，见式(10)，其中初始pa (0)=0.7.

2.4 ESCS算法框架

算法2给出了ESCS算法的流程.需要指出的是在步骤2.1中，除了采用式(8)外，也可采用式(6)、式(7)和式(9)的反向学习模型搜索新的个体，并引入参数M控制精英个体规模.本文简单采用种群中的前M个最优个体作为精英个体.另外，ESCS选择待交叉个体以及当前种群中的K-1个随机个体，组合成K个个体作为单纯形交叉的父个体.

算法2 ESCS的流程如下.

步骤1：采用公式(1)初始化种群Xij(i=1,…,N; j=1,…,D);

步骤2：当迭代终止条件未满足;

步骤2.1:的伪代码如下.

②if Xi是精英个体而且精英个数≤M

③采用式(8)反向学习搜索个体Vi

⑤采用式(2) 搜索个体Vi

⑦如果Vi的适应值优于Xi，则用Vi替换Xi

步骤2.2:伪代码如下.

①从[1，N]中随机产生待用单纯形交叉个体indSPX

②选择n个体成为父个体

③根据式(10)获得pa

⑥采用算法1生成候选子个体Vi

⑧采用公式(4)生成候选子个体Vi

⑩如果Vi的适应值优于Xi，则用Vi替换Xi

步骤2.3：更新当前最优个体;

步骤3：输出最优个体.

3 仿真与结果

为了分析ESCS算法的性能，选择文献[18]中的10个旋转变换函数作为算法的测试函数.其中，F1～F5为单峰函数；F6～F10为多峰函数.更详细的测试函数内容见文献[18].同时，为了公平评价算法的性能，笔者采用平均适应值误差及其收敛曲线图评价准则.其中，适应值误差E计算见式(11).

式中：X为算法得到的解，是已知的最优适应值.从公式可以看出，适应值误差越小则性能越优.

ESCS算法引入参数M和K分别用于控制参与精英反向学习个体的规模和参与单纯形交叉的父个体规模.由于M和K存在不同的取值范围，这就形成规模较大的组合，因此，本实验中假设其中一个参数取常量情况下分析另一个参数.

首先，为了分析参数M对算法性能的影响，图1给出了ESCS算法在K为常量以及不同M时求解10个测试函数(D=30)Friedman的检验平均排序.其中，每个M取值所对应的算法在每个测试函数上独立运行25次,种群大小N=30，最大函数评价次数为10 000×D.

从图1可以看出，M取较小时，算法总体上获得较好性能.这是因为大部分的个体仍采用式(2) 搜索新个体时，种群的小部分精英个体参与反向学习确保了新个体的趋同性，从而加强其搜索能力.另外，从图1可知，当M∈[6,9]时，算法的性能总体最优；综合不同K值情况下的性能可知，M=9较为理想.

图2给出当M∈[6,9]时，取不同K值的算法求解函数的Friedman检验的平均排序.从图2中可以看出，M不同时，算法获得最优的平均排序的K值是不同的.但是，从图2中的水平线(平均排序值=13.3)可知，只有K=15所对应的4个M的平均排序都处于水平线下，而K取其他值所对应M的平均排序少数低于水平线下，这说明了K=15是较为理想的.

表1给出了ESCS算法和CS算法在D=30维上的“Eavg±Esd”(Eavg为平均适应值误差，Esd为标准方差).其中，每个算法在每个测试函数上独立运行25次,两种算法的种群大小N=30，而ESCS算法的M=9，K=15,最大函数评价次数为10 000×D.另外，表1也给出了两种算法在0.05显著水平下的Wilcoxon符号秩检验，“+”表示ESCS算法显

著优于CS算法，“-”表示CS算法显著优于ESCS算法，而“=”表示两算法不存在显著差异.

从表1可以看出，ESCS算法总体上可以改善求精能力.由Wilcoxon统计检验的结果分析可知，虽然在F7测试函数上，ESCS算法的求解能力未显著优于CS算法，但在其他测试函数上，ESCS算法性能显著优于CS算法.

为了进一步比较算法的收敛性能，图3形化展示CS和ESCS算法的收敛过程, 其中，收敛曲线图中的平均适应值误差均是变换后的平均适应值误差，变换函数是lg.从图3可以看出，对于ESCS算法获得的适应值优于CS算法的函数，ESCS算法同时具有较快的收敛速度，在迭代后期具有较好的求精能力，可见图3中的(a)～(f)、(h)、(i)和(j).对于F7函数的收敛过程见图3(g)，ESCS算法在前期具有较快的收敛，但后期陷入局部最优.

综合上述的实验结果，相对于CS算法，ESCS算法对于大多数函数具有较强的求精能力以及较快的收敛速度.

3.3 ESCS与其他改进的CS算法比较

为了进一步观察ESCS与其他改进的CS算法的竞争优势，表2列出ESCS算法与CSPSO[11]、OLCS[12]以及CCS[8]在D=30维空间上的求精能力比较结果，其中用于对比算法的实验数据来源于文献[8].表中加粗数据表示相应算法在该函数获得最优性能，可以得出，不同算法在求解给定的测试函数上具有不同的优势；ESCS算法在F4、F5、F6和F10函数上获得最好的解质量.另外，CSPSO、OLCS、CCS和ESCS 4种算法的Friedman检验结果分别为3.2、3.3、1.8、1.7.从检验结果可知，ESCS具有最小的平均排序值，这说明ESCS算法总体性能最优，其次依次为CCS、CSPSO和OLCS.

3.4 不同反向学习模型对算法性能影响分析

为了分析不同反向学习模型对算法性能的影响，表3给出了ESCS在不同反向学习模型下求解测试函数所获得的平均误差，而表4列出相关算法的Friedman检验结果.其中，ESCS6、ESCS7和ESCS9表示ESCS算法分别采用式(6)、式(7)以及式(9)的反向学习模型.

从表3可知，不同反向学习模型使算法求

解部分函数时获得较好性能.例如，ESCS6算法在F1和F3上获得最佳性能;ESCS7算法在F1上获得最优值；ESCS9算法求解F7获得较好适应值；ESCS算法在较多的函数上获得较好解.同时，根据表4中各算法的平均排序可知，基于式(8)的ESCS算法具有较小的平均排序,这说明采用反向学习模型总体最优.

4 结论

笔者提出一种基于精英反向学习和单纯形交叉以及发现概率自动控制相结合的布谷鸟搜索算法.仿真实验验证了提出的策略总体上能够改善算法的求精能力和收敛速度，从而也验证提出的策略是有效和可行的.下一步工作将提出的算法应用于实际工程优化问题.

[1] KARABODA D. An idea based on honey bee swarm for numerical optimization[R]. Kayseri, Turkey: Computer Engineering Department, Erciyes University, 2005.

[2] YANG X. Nature-inspired metaheuristic algorithms [M]. Frome, UK: Luniver Press, 2008.

[3] HE S, WU Q, SAUNDERS J. A novel group search optimizer inspired by animal behavioral ecology [C]//Proceedings of 2006 IEEE Congress on Evolutionary Computation.Vancouver,BC： IEEE, 2006:1272-1278.

[4] YANG X, DEB S. Cuckoo search via Lévy flight [C]//Proceedings of World Congress on Nature amp; Biologically Inspired Computing. Piscataway, NJ: IEEE, 2009: 210-214.

[5] YANG X, DEB S. Engineering optimization by cuckoo search [J]. Int J Math Modelling Num Opt， 2010,1(4):330-343.

[6] VALIAN E, MOHANNA S, TAVAKOLI S. Improved cuckoo search algorithm for global optimization[J]. Int J Communications and Information Technology, 2011, 1(1):31-44.

[7] WANG L, YIN Y, ZHONG Y. Cuckoo search with varied scaling factor [J]. Frontiers of computer science, 2015, 9(4):623-635.

[8] WANG L, ZHONG Y. Cuckoo search algorithm with chaotic maps [J]. Mathematical problems in engineering, 2015(1): 1-14.

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

[10] 王李进, 钟一文, 尹义龙. 带外部存档的正交交叉布谷鸟搜索算法 [J]. 计算机研究与发展, 2015, 52(11): 2496-2507.

[11] WANG F, HE X, LUO L, et al. Hybrid optimization algorithm of PSO and cuckoo search [C]//Proc of the 2nd Int Conf on Artificial Intelligence, Management Science and Electronic Commerce (AIMSEC). Piscataway, NJ: IEEE, 2011: 1172-1175.

[12] LI X, WANG J, YIN M. Enhancing the performance of cuckoo search algorithm using orthogonal learning method [J]. Neural computing amp; applications, 2014, 24(6): 1233-1247.

[13] WANG L, ZHONG Y. One position inheritance based cuckoo search algorithm [J]. Int J Computing Science and Mathematics, 2015,6(6):546-554.

[14] 王晖. 基于一般反向学习的群体随机搜索算法框架[J]. 南昌工程学院学报, 2012, 31(3): 1-6.

[15] TIZHOOSH H. Opposition-based learning: a new scheme for machine intelligence [C]//Proceedings of the International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce. Piscataway, NJ: IEEE, 2005, 1: 695-701.

[16] TSUTSUI S, YAMAMURA M, HIGUCHI T. Multi-parent recombination with simplex crossover in real coded genetic algorithms [C]//Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation (GECCO′99). Orlando, Florida, USA: CECCO, 1999:657-664.

[17] NOMAN N, IBA H. Accelerating differential evolution using an adaptive local search [J]. IEEE transaction on evolutionary computation, 2008, 12(1):107-125.

[18] SUGANTHAN P, HANSEN N, LIANG J, et al. Problem definitions and evaluation criteria for the CEC2005 special session on real-parameter optimization[R]. Singapore, Singapore: Nanyang Technological University, 2005.

Elite Opposition-based Learning Based Simplex Crossover Cuckoo Search Algorithm

(College of Computer And Information Science, Fujian Agriculture And Forestry University, Fuzhou 350002, China)

Abstract: Cuckoo search algorithm iteratively uses Lévy Flights random walk and Biased random walk to search for new individuals. In this paper, an enhanced cuckoo search was proposed, which employed elite opposition-based learning, simplex crossover and parameter control for the fraction probablity. The elite opposition-based learning strategy was used to avoid the new individuals being homogeneous in the Lévy Flights random walk. The simplex crossover strategy was utilized to reduce the inefficience of Biased random walk. The chaotic map was used to adaptively adjust the parameter pa to balance the exploration and the exploitation. The results of experiment showed the proposed strategies were overall effective, and make a great improvement on the performance of solution and convergence.

Key words: cuckoo search algorithm; simplex crossover; opposite learning; chaotic maps

基金项目：福建省自然科学基金资助项目(2016J01280)；福建省教育厅资助项目(JB09114)

作者简介：林要华(1979— )，男，福建宁德人，福建农林大学讲师，主要从事智能算法及其应用研究.

通信作者：王李进(1977— )，男，福建泉州人，福建农林大学副教授，博士，主要从事智能算法、智能信息处理研究，E-mail:lijinwang@fafu.edu.cn.