Page 257 - 《软件学报》2021年第5期

傅文渊:具有万有引力加速机理的布谷鸟搜索算法 1481

布谷鸟算法(cuckoo search,简称 CS)是 Yang 等人于 2009 年根据布谷鸟的孵育寄生行为提出的一种新型仿
生智能优化算法 [1,2] ,该算法具有通用性强、控制参数少、算法执行速度快等优点,其整体性能相比于粒子群算
法(particle swarm optimization,简称 PSO)、遗传算法(genetic algorithm,简称 GA)、蚁群算法(ant colony
optimization,简称 ACO)、模拟退火算法(simulated annealing,简称 SA)具有较好的竞争力,已经成功应用于工业
界各个领域,例如结构优化 [3,4] 、光伏系统 [5,6] 、支持向量机及神经网络训练 [7,8] 和多目标优化 [9−12] 等.
然而,布谷鸟算法与其他智能启发式算法类似,也存在搜索效率不高的问题.为此,国内外学者对该算法进
行了大量的研究以提高收敛性能.目前的改进算法主要包括两个方面.
• 算法控制参数改进和混合算法策略.文献[13]提出一种自适应搜索步长的 CS 算法,提高了收敛性能.文
献[14]在文献[13]的基础上,将搜索步长因子变更为 3 种不同的函数适应度值变化因子,通过动态调节
步长因子,增强算法的鲁棒性.文献[15]将搜索步长因子设计为均匀分布随机数,虽然提高了 CS 算法的
全局搜索性能,但是该方法没有考虑局部搜索的性能,导致算法执行后期易发生迟滞现象.文献[16]提
出一种逐维更新的函数评价策略,将各维逐一更新,同时采用贪婪更新方式接受改善解.该算法具有一
定的竞争力,但是逐维更新的评价策略导致函数评价次数急剧增加,算法执行效率较低.文献[17]将发
现概率设置为动态变化,增强了算法的收敛性能.但是由于改进算法搜索步长的可容许范围过小,造成
算法全局收敛性能较差.
• 另一方面,混合算法策略的主要方法是布谷鸟算法与其他算法融合,获得最佳的优化性能.文献[18]将
和声优化算法与 CS 算法结合,在算法执行过程增加和声算法的变异操作,并将变异结果反馈到寻优过
程,加快算法的收敛速度.文献[19]借鉴粒子群算法良好的局部优化性能,在 CS 算法中引入粒子群组件,
提高了 CS 算法的收敛精度.文献[20,21]在偏好随机扰动中引入一种正交学习机制,以提高 CS 算法的
整体搜索性能.文献[22]将 CS 算法与万有引力算法结合,引入一种局部搜索机制,使布谷鸟个体的更新
由局部最优解和引力加速度共同作用.该算法虽然提高了收敛速度,但是引入的局部搜索极易使算法
陷入局部最优.文献[23]将 CS 算法与模式搜索方法结合,提高了 CS 算法的局部开采能力.
由上所述,该类算法虽然提高了搜索性能,例如种群的多样性、收敛精度等,但是增加了优化函数评价次数
及算法复杂度.当处理高维度多峰函数、脊峰函数和奇异函数时,算法的自适应调节能力较差,寻优效果不理想.
同时,该类算法没有深入挖掘种群寻优过程的内部机理,算法执行效率较低.因此,研究新的改进方法具有积极
的意义.
基于此,本文提出一种具有万有引力加速机理的布谷鸟算法(gravitational acceleration search based cuckoo
search,简称 GASCS),提高 CS 算法的收敛速度和全局收敛效率.本文的主要特色及贡献为:(1) 该算法基于万有
引力搜索无需学习外部环境因素的变化亦能感知全局最优的特点,将布谷鸟巢穴等价为不同质量的个体,利用
CS 算法优化过程中遵循的牛顿万有引力定律进行加速搜索,并且提出一种概率变异方法增大种群多样性;
(2) 该算法提出两种新型的布谷鸟个体更新律;(3) 该算法解决了 CS 算法存在的 3 个局限性,提高了 CS 算法的
全局搜索效率和收敛精度.

1 布谷鸟算法(CS)及其存在的局限性

布谷鸟采用一种特殊的寄生宿主巢穴的方式孕育繁殖,它将孵育的蛋置入寄生宿主的巢穴,让寄生宿主孵
化布谷鸟蛋.由于布谷鸟幼雏能发出比寄生宿主幼雏更闪亮的叫声,因此获得更多的食物,具有更高的存活率.
在某些情形下,寄生宿主发现巢穴内不是宿主幼雏,则会遗弃该巢穴,并重新选择新的巢穴孵育繁殖.Yang X. S.
[1]
和 Deb 等人基于上述孵育寄生机理,提出布谷鸟算法.它遵循以下 3 个理想规则 .
规则 1. 每只布谷鸟 1 次有且仅有孵化 1 个蛋,并随机选择 1 个寄生宿主巢穴存放.
规则 2. 在随机选择的 1 个寄生宿主巢穴中,最优的寄生宿主巢穴将被保留至下一代.
规则 3. 可利用的寄生宿主巢穴数量是固定的,1 个寄生宿主巢穴的宿主发现寄生布谷鸟蛋的概率为 P a .
基于上述 3 个理想规则,可以得到 1 个宿主巢穴代表 1 个候选解.因此,布谷鸟算法的基本算法流程包含 3