基于逐维策略的布谷鸟搜索增强算法

摘要/Abstract

摘要：

布谷鸟搜索算法迭代运用Lévy Flights随机走动和Biased随机走动发现新个体的各维信息。当个体所有维信息生成后，算法将这些信息合成为个体并评价。在这种情况下，由于个体各维之间存在相互干扰，一些部分维进化的个体可能被放弃，从而影响算法的收敛速度以及求精能力。提出的布谷鸟搜索增强算法采用逐维评价策略接收一些部分进化的个体，可进一步增强算法的收敛速度和求精能力。在算法中，逐维评价策略作为局部搜索技术镶嵌在两个随机走动部件之后，并随机选择一些个体进行逐维更新后进行评价。实验结果说明逐维评价策略总体上能够有效且较好地改善算法的求解性能和收敛速度。

关键词: 布谷鸟搜索算法, 逐维评价, 逐维改进, 局部搜索

Abstract:

The cuckoo search algorithm utilizes Lévy Flights random walk and Biased random walk iteratively to search for the dimensional information of each new individual. After generating all dimensional information of each individual, the algorithm combines them as an individual and then evaluates it. Thus, the individuals with good dimensional information can be abandoned because of dimensional interference, which affects the convergence speed and refining capacity. We propose an enhanced cuckoo search algorithm based on the strategy of dimension by dimension evaluation to accept those with good dimensional information, which can enhance the convergence speed and refining capacity. In the proposed approach, the strategy of dimension by dimension evaluation is adopted as a local search technique. We embed it behind the two random walks, and evaluate new individuals after each dimension is generated from those randomly selected individuals. Experimental results show that the dimension by dimension evaluation strategy can generally and effectively improve the performance of solution and the convergence speed.

Key words: cuckoo search algorithm, dimension by dimension evaluation, dimension by dimension improvement, local searc

林要华1，王维2. 基于逐维策略的布谷鸟搜索增强算法[J]. 计算机工程与科学.

LIN Yaohua1,WANG Wei2.

An enhanced cuckoo search algorithm based

on dimension by dimension strategy

[J]. Computer Engineering & Science.

参考文献［16］

［1］	Yang X S,Deb S.Cuckoo search via Levy flight［C］∥Proc of World Congress on Nature & Biologically Inspired Computing (NaBIC 2009), 2009:210214.
［2］	Yang Xinshe, Deb S. Engineering optimization by cuckoo search［J］. International Mathematical Modelling & Numerical Optimisation, 2010,1(4):330343.
	Table 7Algorithm complexity of the ECS and the CS
	表7ECS和CS算法的复杂性
	D
	CS
	T0T1T2C
	ECS
	T1T2C
10	0.080 738 306.295 343 606.264 953 78-0.376 990 571.565 775 101.562 032 78-0.046 351 24
30	0.080 738 306.282 991 306.287 156 640.051 590 631.575 642 401.571 793 60-0.047 670 06
50	0.080 738 3011.624 637 3011.041 478 98-7.222 821 393.389 375 203.099 054 86-3.595 774 74
［3］	Hu Xinxin. Improved cuckoo search algorithm for function optimization problems［J］.Computer Engineering and Design,2013,34(10):36393642.(in Chinese)
［4］	Zhang Yongwei, Wang Lei,Wu Qidi.Dynamic adaptation cuckoo search algorithm［J］.Control and Decision,2014,29(4):617622.(in Chinese)
［5］	Liang Zhong,Lin Yaohua,Zhou Shucheng.Cuckoo search algorithm with reverse direction and binomial crossover［J］.Journal of Frontiers of Computer Science and Technology,2015,9(8):10101017.(in Chinese)
［6］	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.
［7］	Wang Lijin,Yin Yilong,Zhong Yiwen.Cuckoo search with varied scaling factor［J］.Frontiers of Computer Science,2015,9(4):623635.
［8］	Wang Lijin, Zhong Yiwen. Cuckoo search algorithm with chaotic maps［J］.Mathematical Problems in Engineering,2015(1):114.
［9］	Wang Lijin,Yin Yilong,Zhong Yiwen.Cuckoo search algorithm with dimension by dimension improvement ［J］.Journal of Software,2013,24(11): 26872698.(in Chinese)
［10］	Lin Yaohua,Liang Zhong,Hu Huaping.Cuckoo search algorithm with beta distribution ［J］.Journal of Nanjing University (Nature Sciences),2016,52(4): 638646.(in Chinese)
［11］	Wang Lijin,Zhong Yiwen,Yin Yilong.Orthogonal crossover cuckoo search algorithm with external archive［J］.Journal of Computer Research and Development,2015,52(11): 24962507.(in Chinese)
［12］	Wang F,He X S,Luo L G,et al.Hybrid optimization algorithm of PSO and cuckoo search ［C］∥Proc of the 2nd IEEE International Conference on Artificial Intelligence,Management Science and Electronic Commerce (AIMSEC),2011: 11721175.
［13］	Wang G G,Guo L H,Duan H,et al.A hybrid metaheuristic DE/CS algorithm for UCAV path planning ［J］.Journal of Information & Computational Science,2012,9(16) :48114818.
［14］	Li X T,Wang J N,Yin M H.Enhancing the performance of cuckoo search algorithm using orthogonal learning method ［J］.Neural Computing & Applications,2014,24(6): 12331247.
［15］	Li Juan,Li Yuanxiang,Tian Shasha,et al.A cuckoo search algorithm using elite opposition based learning and chaotic disturbance［J］.Journal of Wuhan University (Natural Science Edition),2015,61(4): 356362.(in Chinese)
［16］	Hu Xinxin,Yin Yilong.Cooperative coevolutionary cuckoo search algorithm for continuous function optimization problems ［J］.Pattern Recognition and Artificial Intelligence,2013,26(11): 10411049.(in Chinese)
［17］	Wang Lijin,Zhong Yiwen,Yin Yilong.A hybrid cooperative cuckoo search algorithm with particle swarm optimization［J］.International Journal of Computing Science and Mathematics,2015,6(1):1829.
［18］	Wang Lijin,Zhong Yiwen.One position inheritance based cuckoo search algorithm［J］.International Journal of Computing Science and Mathematics,2015,6(6):546554.
［19］	Blum C J,Puchinger J,Raidl G,et al. Hybrid metaheuristics in combinatorial optimization: A survey［J］.Applied Soft Computing,2011,11(6):41354151.
［20］	Lozano M, GarciaMartinez C.Hybrid metaheuristics with evolutionary algorithms specializing in intensification and diversification: Overview and progress report［J］.Computers & Operations Research,2010,37(3):481497.
［21］	Zhang J,Zhan Z H,Lin Y,et al.Evolutionary computation meets machine learning: A survey［J］. IEEE Computational Intelligence Magazine,
20	11,6(4):6875.
［22］	Zhong Y W,Liu X,Wang L J,et al.Particle swarm optimization algorithm with iterative improvement strategy for multidimensional function optimization problems［J］.International Journal of Innovative Computing and Application,2012,4(34):223232.
［23］	Noman N, Iba H. Accelerating differential evolution using an adaptive local search ［J］.IEEE Transactions on Evolutionary Computation,2008,12(1):107125.
［24］	Suganthan P N,Hansen N,Liang J J,et al.Problem definitions and evaluation criteria for the CEC2005 special session on realparameter optimization［R］.
	Singapore:Nanyang Technological University,2005.
	附中文参考文献：
［3］	胡欣欣.求解函数优化问题的改进布谷鸟搜索算法［J］.计算机工程与设计,2013,34(10):36393642.
［4］	张永韡,汪镭,吴启迪.动态适应布谷鸟搜索算法［J］.控制与决策,2014,29(4):617622.
［5］	梁忠,林要华,周术诚.带反方向视角和二项交叉的布谷鸟搜索算法［J］.计算机科学与探索,2015,9(8):10101017.
［9］	王李进,尹义龙,钟一文.逐维改进的布谷鸟搜索算法［J］.软件学报,2013,24(11): 26872698.
［10］	林要华,梁忠,胡华平.贝塔分布的布谷鸟搜索算法［J］.南京大学学报（自然科学）,2016,52(4): 638646.
［11］	王李进,钟一文,尹义龙.带外部存档的正交交叉布谷鸟搜索算法［J］.计算机研究与发展,2015,52(11): 24962507.
［15］	李娟,李元香,田莎莎,等.基于精英反向学习的混沌布谷鸟搜索算法［J］.武汉大学学报(理学版),2015,61(4): 356362.
［16］	胡欣欣,尹义龙.求解函数优化问题的合作协同进化布谷鸟搜索算法［J］.模式识别与人工智能,2013,26(11):10411049.

[1]	杨炳媛, 袁杰, 郭园园. 一种自适应鲸鱼快速优化算法[J]. 计算机工程与科学, 2023, 45(01): 145-153.
[2]	宋强. Beam-PSO优化算法在多行程车辆路径问题的应用[J]. 计算机工程与科学, 2019, 41(10): 1882-1891.
[3]	黄亚飞1,2,梁昔明1,樊绍胜2. 基于局部字典搜索和多原子匹配追踪的图像逼近算法[J]. 计算机工程与科学, 2018, 40(01): 72-78.
[4]	刘汉强,郑朋. 局部搜索自适应核模糊聚类方法[J]. 计算机工程与科学, 2016, 38(08): 1735-1740.
[5]	臧培荃，孙晨骜，顾晓峰，吴滨，周长喜. 具有自适应趋向性和引导因子的人工蜂群算法[J]. J4, 2015, 37(09): 1692-1697.
[6]	包云，姜华，郑丽萍. 基于和声搜索的阻塞流水车间调度问题的算法优化[J]. J4, 2013, 35(7): 108-112.
[7]	刘一丹1,王子牛2 ,陈洁1 , 李少博1. 基于DEXEL和离散点阵法的数控加工仿真研究[J]. J4, 2011, 33(1): 171-175.
[8]	向佐勇[1,2] 刘正才[2]. 一种改进的混合遗传算法研究[J]. J4, 2008, 30(9): 53-57.
[9]	赵同昇[1] 朱文兴[2]. MAX—SAT问题一种改进的局部搜索算法[J]. J4, 2008, 30(11): 50-52.
[10]	郑雅燕[1] 朱文兴[2]. TSP问题的一种改进的GRASP算法[J]. J4, 2008, 30(11): 60-64.
[11]	蒋皓石杜谋辉林嘉宇. 说话人识别中随机局部搜索算法的研究[J]. J4, 2006, 28(7): 85-86.
[12]	韩丽霞[1] 王宇平[2]. 求解旅行商问题的一个新的单亲遗传算法[J]. J4, 2006, 28(2): 72-73.