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

1484 Journal of Software 软件学报 Vol.32, No.5, May 2021

2.2 GASCS数学机理分析
传统的 CS 算法是基于 Levy 飞行随机游动方式和偏好随机游动方式两种搜索机理,虽然具有一定的收敛
性能,但仍然存在第 1 节所阐述的 3 点局限性.为此,本文提出具有万有引力加速机理的布谷鸟算法.它基于万有
引力搜索无需学习外部环境因素的变化亦能感知全局最优信息的特点,将布谷鸟巢穴赋予不同的个体质量,其
在优化过程中不仅遵循 Levy 飞行规律,而且遵循万有引力定律.
GASCS 算法的详细机理如图 1 所示,设定 nest(m),nest(s),nest(k)分别为种群进化的宿主巢穴位置,nest_g 为
最优巢穴位置,并且假设宿主巢穴的质量满足 nest(s)>nest(m)>nest(k).因此,最优巢穴位置 nest_g 的质量满足如
下数学关系:nest_g>nest(s)>nest(m)>nest(k).为便于分析,设定 X r,m 等价于 nest(m),X r,s 等价于 nest(s),X r,k 等价于
nest(k)以及 X r,gb 等价于 nest_g.F r,ms ,F r,mk 和 F r,mg 是分别作用于 nest(m)到 nest(s)、nest(m)到 nest(k)以及 nest(m)
到 nest_g 的万有引力.在万有引力作用下产生的加速度分别为 a ms ,a mk 和 a mg .F r,m 是作用于 nest(m)和 nest_g 产
生加速度 a mg 的所有合力;同时,F r,t 是作用于 F r,m 和 nest(k)产生加速度 a r 的合外力.因此,在万有引力的作用下,
宿主巢穴逼近质量最大的巢穴 nest_g.根据牛顿第二定律,宿主巢穴在进化过程中所受的加速度由巢穴所受的
合外力及自身质量共同决定.基于此,将布谷鸟算法的个体更新律(1)和更新律(4)改进为公式(15)和公式(16):
X r+1,m =a r −(γ 0 ⊕L(β))⋅(a r −X r,gb ) (15)
X r+1,m =X r,gb +p⋅(X r,k −X r,s −a r ) (16)
其中,公式(15)和公式(16)分别表示 Levy 飞行随机游动和偏好随机游动方式的个体位置,p∈(0,+∞),a r 为 F r,t 产生
的合加速度.由公式(15)可知:与传统的 CS 算法宿主巢穴只是单纯的按照 Levy 飞行随机游动产生候选解不同,
GASCS 算法将每个宿主巢穴视为不同质量的物质个体,它遵循万有引力定律和牛顿第二定律.如图 1 所示,宿主
巢穴 nest(m),nest(s),nest(k)沿加速度 a r 的方向移动,并且公式(15)的步长修正项为−(γ 0 ⊕L(β))⋅(a r −X r,gb ).由向量运
算法则得到 a g =a r −(γ 0 ⊕L(β))⋅(a r −X r,gb ),因此,算法能较好地逼近全局最优解 nest_g.

nest(k)-nest(s)-a r
nest(k)-a r/2
nest(k)
F r,mk
a mk nest(k)-nest(m)-a r/2
nest(m)
a r/2 a p
F r,ms
F r,m F r,mg
a ms nest(s)- a g
nest(s) nest(m)+ a r
a r/2 F r,t nest_g
a mg

Fig.1 Mechinism of gravitational attraction acceleration
图 1 万有引力加速机理
综上所述,由于 Levy 飞行随机游动和偏好随机游动方式的个体位置更新引入了合加速度 a r ,并且 a r 随算法
进化而自适应变化的,因此 GASCS 算法能够平衡算法的搜索进程,抵消搜索步长设置不合理引发的算法性能恶
化.本算法在进化中不仅利用 Levy 飞行随机游动方式的无限跳跃特性易于跳出局部最优解的特点,而且利用了
万有引力加速度快速逼近全局最优解的特性,克服了第 1 节 CS 算法的第 1 点局限性.
其次,针对第 2 点局限性中随机处理会舍弃较好的种群个体引起算法寻优速度和收敛精度下降的问题,本
文算法的改进思路如图 1 所示.作用于 nest(m)到 nest(k)的外力与 F r,t /2 产生的合加速度 a r /2 的向量差为 nest(k)−
nest(m)−a r /2.同理,作用于 nest(m)到 nest(s)的合力与 F r,t /2 产生的合加速度 a r /2 的向量和为 nest(s)−nest(m)+a r /2.
根据向量运算法则,X rd =nest(k)−nest(m)−a r /2−(nest(s)−nest(m)+a r /2)=nest(k)−nest(s)−a r ⇔X r,k −X r,s −a r .
由公式(16)可知,X r,gb 与 p⋅X rd 组合的结果为图 1 所示的加速度 a p .通过 Levy 飞行随机游动方式产生的加速