求解函数优化问题的改进布谷鸟搜索算法

doi:10.11896/jsjkx.181102165

摘要/Abstract

摘要： 在工程优化中,大多问题是连续优化问题,即函数优化问题。针对布谷鸟算法求解函数优化问题时存在的收敛速度慢、求解精度不高和易陷入局部最优等问题,文中提出非线性惯性权重对数递减和随机调整发现概率的布谷鸟搜索算法(Cuc-koo Search Algorithm with Logarithmic Decline of Nonlinear Inertial Weights and Random Adjustment Discovery Probability,DWCS)。首先,在布谷鸟寻窝的路径和位置更新公式中,设计一种随进化迭代次数非线性递减的惯性权重来改进鸟巢位置的更新方式,以协调布谷鸟算法的探索和开发能力;其次,引入随机调整发现概率代替固定值发现概率,使较大和较小的发现概率随机出现,从而有利于平衡算法的全局探索和局部开发能力,加快算法收敛速度,增加种群多样性;最后,分析对数递减参数和随机调整发现概率,选取对数递减最佳参数组合和随机调整发现概率的最佳取值范围,此时,函数的优化效果最好。与BA,CS,PSO,ICS算法相比,所提算法极大地提高了寻优精度,显著地减少了迭代次数,有效地提高了收敛速度和鲁棒性。在16个测试函数中,DWCS均能收敛到全局最优解,证明了DWCS在求解连续复杂函数优化问题上具有较强的竞争力。

关键词: 布谷鸟搜索算法, 参数选取, 对数递减, 发现概率, 函数优化

Abstract: In engineering optimization,most problems are continuous optimization problems,that is function optimization problems.Aiming at the problems of slow convergence speed,low precision and easy to fall into local optimization in the later stage of Cuckoo algorithm,this paper proposed an improved Cuckoo search algorithm based on the logarithmic decline of nonlinear inertial weights and the random adjustment discovery probability.Firstly,in the update formula of the path and position of the cuckoo homing nest,a update method that inertia weight decreases nonlinearly with the number of evolutionary iterations is designed to improve the nest location and coordinate the abilities of exploration and exploitation.Secondly,the discovery probability with random adjustment is introduced to replace the discovery probability of fixed value to make the larger and smaller discovery probabi-lity appear randomly,which is beneficial to balancing the global exploration and local exploitation of the algorithm,accelerating the convergence speed,and increasing the diversity of the population.Finally,the logarithmic decreasing parameter and stochastic adjustment discovery probability are analyzed and tested,and the optimal parameter combination of logarithmic decrement and the optimal range of stochastic adjustment discovery probability are selected.At this time,the optimization effect of the function is the best.Compared with other evolutionary algorithms (BA,CS,PSO,ICS),DWCS greatly improves the precision of optimization,significantly reduces the number of iterations,and effectively improves the convergence speed and robustness.In 16 test functions,DWCS can converge to the global optimal solution,which proves that DWCS has a strong competitive power in solving the optimization problem of continuous complex functions.

Key words: Cuckoo search algorithm, Discovery probability, Function optimization, Logarithmic decreasing, Parameter selection

中图分类号:

TP301.6

李煜,尚志勇,刘景森. 求解函数优化问题的改进布谷鸟搜索算法[J]. 计算机科学, 2020, 47(1): 219-230. https://doi.org/10.11896/jsjkx.181102165

LI Yu,SHANG Zhi-yong,LIU Jing-sen. Improved Cuckoo Search Algorithm for Function Optimization Problems[J]. Computer Science, 2020, 47(1): 219-230. https://doi.org/10.11896/jsjkx.181102165

参考文献

[1]WALTON S,HASSAN O,MORGAN K,et al.Modified cuckoo search:a new gradient free optimization algorithm[J].Chaos,Solitons and Fractals,2011,44(9):710-718.
[2]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.
[3]LI X T,WANG J A,YIN M H.Enhancing the performance of cuckoo search algorithm using orthogonal learning method[J].Neural Computing and Applications,2014,24(6):1233-1247.
[4]LONG W,CAI S H,JIAO J J,et al.Improved whale optimization algorithm for large scale optimization problems [J].Systems Engineering－Theory & Practice,2017,37(11):2983-2994.
[5]GOLDBERG D E,HOLLAND J H.Genetic algorithm in search,optimization and machine learning[M].Boston:Addison-Wesley Longman Publishing Co.Inc.1989.
[6]EBERHART R,KENNEDY J.A new optimizer using parti- cleswarm theory [C]∥Proceedings of the Sixth International Symposium on Micro Machine and Human Science.Nagoya:IEEE,1995:39-43.
[7]KIRKPATRICK S,GELATT C D,VECCHI M P.Optimization by simulated annealing [J].Science,1983,220:671-680.
[8]KOUDIL M,BENATCHBA K,TARABET A,et al.Using artificial bees to solve partitioning and scheduling problems in code sign [J].Applied Mathematics and Computation,2007,186(2):1710-1722.
[9]GEEM Z W,KIM J H,LOGANATHAN G V.A new heuristicoptimization algorithm:Harmony search[J].Simulation,2001,76(2):60-68.
[10]PAN W T.A new Fruit Fly Optimization Algorithm:Taking- the financial distress model as an example [J].Knowledge-Based Systems (0950-7051),2012,26(2):69-74.
[11]KRISHNANAND K N,GHOSE D.Detection of multiple source locations using a glowworm metaphor with applications to collective robotics[C]∥ Proceedings of IEEE Swarm Intelligence Symposium.Pasadena:IEEE,2005:84-91.
[12]YANG X S,DEB S.Cuckoo search via Levy flight [C]∥ Proceedings of World Congress on Nature & Bio-logically Inspired Computing.Coimbatore:IEEE,2009:210-214.
[13]YANG X S,DEB S.Engineering optimization by cuckoo search [J].International Journal of Mathematical Modeling and Numerical Optimization (2040-3607),2010,1(4):330-343.
[14]LI Y,MA L.A new metaheuristic cuckoo search algorithm [J].Systems Engineering,2012,30(8):64-69.
[15]LI Y,PEI Y H,LIU J S.Bat optimal algorithm combined uniform mutation with gaussian mutation[J].Control and Decision,2017,32(10):1775-1781.
[16]OUAARAB A,AHIOD B,YANG X S.Discrete cuckoo search algorithm for the travelling salesman problem[J].Neural Computing and Applications,2014,24(7/8):1659-1669.
[17]NAIK M K,PANDA R.A novel adaptive cuckoo search algorithm for intrinsic discriminant analysis based face recognition [J].Applied Soft Computing (1568-4946),2016,38(C):661-675.
[18]SETHI R,PANDA S,SAHOO B P.Cuckoo search algorithm based optimal tuning of PID structured TCSC controller[M].Odisha:Springer,2015:251-263.
[19]WANG J,ZHOU B.A hybrid adaptive cuckoo search optimization algorithm for the problem of chaotic systems parameter estimation [J].Neural Computing & Applications (0941-0643),2016,27(6):1511-1517.
[20]WANG L J,YIN Y L,ZHONG Y W.Cuckoo search algorithm with dimension by dimension improvement[J].Journal of Software,2013,24(11):2687-2698.
[21]MA W,SUN Z X.A global cuckoo optimization algorithm using coarse-to-fine search[J].Acta Electronica Sinica,2015,43(12):2429-2439.
[22]VALIA E,TAVAKOLI S,MOHANNA S.Improved cuckoo search for reliability optimization problems [J].Computers & Industrial Engineering (0360-8352),2013,64(1):459-468.
[23]ZHENG H Q,ZHOU Y Q.A novel cuckoo search optimization algorithm based on Gauss distribution[J].Journal of Computational Information Systems,2012,8(10):4193-4200.
[24]LI R Y,DAI R W.Adaptive step-size cuckoo search algorithm [J].Computer Science,2017,44(5):235-240.
[25]WANG L J,YIN Y L,ZHONG Y W.Cuckoo search with varied scaling factor[J].Frontiers of Computer Science,2015,9(4):623-635.
[26]JIN Q B,QI L F.Novel improved cuckoo search for PID controller design [J].Transactions of the Institute of Measurement & Control,2014,37(6):1-11.
[27]PRAJAPATI P P,SHAH M V.Performance Estimation of Differential Evolution,Particle Swarm Optimization and Cuckoo Search Algorithms[J].I.J.Intelligent Systems and Applications,2018,6:59-67.
[28]ZHANG Z C,HAN W,MAO B.Adaptive discrete cuckoo algorithm based on simulated annealing for solving TSP [J].Acta Electronica Sinica,2018,46(8):1849-1857.
[29]ZHANG M Q,WANG H,CUI Z H,et al.Hybrid multiob-jective cuckoo search with dynamical local search [J].Memetic Computing,2017,10(4):1-10.
[30]FU W Y.Equilibrium single evolution based cuckoo search algorithm [J].Acta Electronica Sinica,2019,47(2):282-288.
[31]MARELI M,TWALA B.An adaptive cuckoo search algorithm for optimization[J].Applied Computing and Informatics,2018,14(2):107-115.
[32]SALGOTRA R,SINGH U,SAHA S.New cuckoo search algorithms with enhanced exploration and exploitation properties [J].Expert Systems With Applications,2018,95:384-420.
[33]WANG Z,JIA C X,SUN Y H.Parasitized breeding and nestlings growth in oriental cuckoo[J].Chinese Journal of Zoology,2004,39(1):103-105.
[34]VISWANATHAN G M,AFANASYEV V,BULDYRE-V S V,et al.Lévy flights in random searches [J].Physica A:Statistical Mechanics and its Applications,2000,282(1/2):1-12.
[35]SHI Y H,EBERHART R C.Empirical study of particle swarm optimization [C]∥Proceedings of the 1999 Congress on Evolutionary Computation.Washington:IEEE,1999,3:1945-1949.
[36]SHI Y H,EBERHART R C.Fuzzy adaptive particle s-warm optimization [C]∥Proceedings the 2001 Congress on Evolutionary Computation.Seoul:IEEE,2001:101-106.
[37]EBERHART R C,SHI Y H.Tracking and optimizing dynamic systems with particle swarms [C]∥ Proceedings of the 2001 Congress on Evolutionary Computation.Seoul:IEEE,2001:94-100.
[38]PERAM T,VEERAMACHANENI K,MOHAN C K.-Fitness-distance-ratio based particle swarm optimization[C]∥Procee-dings of the 2003 IEEE Swarm Intelligence Symposium.Indiana-polis:IEEE,2003:174-181.
[39]FENG J M,LIU S Y.Particle swarm optimization algorithm based on inertia weight exponentially decreasing for solving absolute value equations[J].Journal of Jilin University (Science Edition),2016,54(6):1265-1269.
[40]ZHANG X,WANG P,XING J C,et al.Particle swarm optimization algorithms with decreasing inertia weight based on gaussian function[J].Application Research of Computers,2012,29(10):3710-3712,3724.
[41]DAI W Z,YANG X L.Particle swarm optimization algorithm based on inertia weight logarithmic decreasing.Computer Engineering and Applications,2015,51(17):14-19,52.

相关文章 15

[1]	田真真, 蒋维, 郑炳旭, 孟利民. 基于服务器集群的负载均衡优化调度算法 Load Balancing Optimization Scheduling Algorithm Based on Server Cluster 计算机科学, 2022, 49(6A): 639-644. https://doi.org/10.11896/jsjkx.210800071
[2]	张蔷, 黄樟灿, 谈庆, 李华峰, 湛航. 基于动态近邻套索算子的金字塔演化策略 Pyramid Evolution Strategy Based on Dynamic Neighbor Lasso 计算机科学, 2021, 48(6): 215-221. https://doi.org/10.11896/jsjkx.200400115
[3]	曹素娥, 杨泽民. 基于聚类分析算法和优化支持向量机的无线网络流量预测 Prediction of Wireless Network Traffic Based on Clustering Analysis and Optimized Support Vector Machine 计算机科学, 2020, 47(8): 319-322. https://doi.org/10.11896/jsjkx.190800075
[4]	杨凯中, 提梦桃, 谢英柏. 基于罗盘算子的改进蝙蝠优化算法 Improved Bat Optimization Algorithm Based on Compass Operator 计算机科学, 2020, 47(6A): 135-138. https://doi.org/10.11896/JsJkx.190800112
[5]	霍林, 郭雅蓉, 覃志健. 具有自适应步长的柯西变异乌鸦算法 Crow Search Algorithm with Cauchy Mutation and Adaptive Step Size 计算机科学, 2020, 47(12): 218-225. https://doi.org/10.11896/jsjkx.191100207
[6]	仇国庆, 熊耕耘, 赵文铭. 一种改进的三维Otsu图像分割算法 Improved Three-dimensional Otsu Image Segmentation Algorithm 计算机科学, 2018, 45(8): 247-252. https://doi.org/10.11896/j.issn.1002-137X.2018.08.044
[7]	潘俊虹, 王宜怀, 吴薇. 基于优化BP神经网络的物理量回归方法 Physical Quantity Regression Method Based on Optimized BP Neural Network 计算机科学, 2018, 45(12): 170-176. https://doi.org/10.11896／j.issn.1002-137X.2018.12.027
[8]	张新明,涂强,康强,程金凤. 灰狼优化与差分进化的混合算法及函数优化 Hybrid Optimization Algorithm Based on Grey Wolf Optimization and Differential Evolution for Function Optimization 计算机科学, 2017, 44(9): 93-98. https://doi.org/10.11896/j.issn.1002-137X.2017.09.019
[9]	李荣雨,戴睿闻. 自适应步长布谷鸟搜索算法 Adaptive Step-size Cuckoo Search Algorithm 计算机科学, 2017, 44(5): 235-240. https://doi.org/10.11896/j.issn.1002-137X.2017.05.042
[10]	魏政磊,赵辉,韩邦杰,孙楚,李牧东. 具有自适应搜索策略的灰狼优化算法 Grey Wolf Optimization Algorithm with Self-adaptive Searching Strategy 计算机科学, 2017, 44(3): 259-263. https://doi.org/10.11896/j.issn.1002-137X.2017.03.053
[11]	张新明,尹欣欣,冯梦清. 动态高斯变异和随机变异融合的自适应细菌觅食优化算法 Adaptive Bacterial Foraging Optimization Algorithm Based on Dynamic Gaussian Mutation and Random One for High Dimensional Functions 计算机科学, 2015, 42(6): 101-106. https://doi.org/10.11896/j.issn.1002-137X.2015.06.023
[12]	朱旭辉,倪志伟,程美英. 变步长自适应的改进人工鱼群算法 Self-adaptive Improved Artificial Fish Swarm Algorithm with Changing Step 计算机科学, 2015, 42(2): 210-216. https://doi.org/10.11896/j.issn.1002-137X.2015.02.044
[13]	邹儒,冯翔. 创造性驱动优化算法 Creativity Driven Optimization Algorithm 计算机科学, 2015, 42(11): 260-265. https://doi.org/10.11896/j.issn.1002-137X.2015.11.053
[14]	杨辉华,张晓凤,谢谱模,韦向远. 基于布谷鸟搜索的多处理器任务调度算法 Multiprocessor Task Scheduling Method Based on Cuckoo Search Algorithm 计算机科学, 2015, 42(1): 86-89. https://doi.org/10.11896/j.issn.1002-137X.2015.01.020
[15]	黄光球,徐晓龙,陆秋琴. 具有脉冲毒素输入的生态毒理动力学的函数优化方法 Ecotoxicology Dynamics-based Optimization with Impulsive Toxicant Input 计算机科学, 2014, 41(8): 254-262. https://doi.org/10.11896/j.issn.1002-137X.2014.08.054

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed