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

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

部分:首先,在当前候选解的基础上,以 Levy 飞行随机游动生成新的候选解,评价并保留较好的候选解;其次,按照
发现概率 P a 舍弃部分候选解;最后,按照偏好随机游动方式产生新的候选解并替代舍弃的解,保留较好解后进入
下一次进化,直至满足算法的收敛条件.
设布谷鸟算法进化至第 r 代时第 m 个候选解为 X r,m , X = (x (1) , x (2) ,..., x ( )j , ..., x ( )D ) ,j∈[1,D].采用 Levy 飞
, rm , r m , rm , rm , r m
行随机游动产生新的个体(候选解)X r+1,m 更新律的表达式为
X r+1,m =X r,m +(X r,m −X r,gb )⋅(γ 0 ⊕L(β)) (1)
其中,X r,gb 为当前搜索到的全局最优解,L(β)表示 Levy 飞行随机游动路径,γ 0 表示初始搜索步长,⊕表示点对点乘
法,t 为飞行时间:
L(β)~ϑ=t −1−β ,0<β≤2 (2)
[1]
通过数学代换 ,公式(2)等价于:
Γ (1 β + ⎛ )sin(π ⋅ β / 2) ⎞ 1/ β
ϑ ⎜ ⎟
L () ~β ⋅ ⎛ 1 β ⎞ + (β − 1) / 2 (3)
β
|| v 1/ β ⎜ Γ ⎜ ⎜ ⎟ ⋅⋅ 2 ⎟ ⎟
⎝ ⎝ 2 ⎠ ⎠
其中,Γ(⋅)为伽玛函数,取β=1.5;ϑ,v 为标准高斯分布随机数.
在偏好随机游动方式中,按照发现概率 P a 舍弃部分候选解后,生成相同数量的新解:
X r+1,m =X r,m +φ⋅(X r,k −X r,s ) (4)
其中,φ为算法的控制缩放系数,满足φ∈U(0,1);X r,k 和 X r,s 分别为第 r 代时第 k 个和第 s 个随机候选解.
基本 CS 算法虽然具有一定的收敛能力,但是存在以下局限性.
(1) 采用 Levy 飞行随机游动产生新候选解的搜索步长设置困难:如果搜索步长较大,则寻优速度增大,但
由于 Levy 飞行具有无限跳跃特性,使得算法执行过程中极易跳过全局最优解;如果搜索步长较小,虽
然能以较大概率获得全局最优解,但是寻优速度会降低.考虑到 Levy 飞行具有无限大方差并且其增
量服从二阶分布,因此,设计合理的搜索步长变得尤为困难.
(2) CS 算法采用发现概率 P a 舍弃偏好随机游走方式产生新的候选解.这种方法虽然加强了算法的全局
搜索性能,但随机处理会舍弃较好的种群个体,而保留适应度较差的种群个体,进而降低算法搜索速
度和收敛精度.
(3) CS 算法仅通过两个随机个体的位置向量差获得下次进化的方向,未能充分利用当前宿主巢穴的足够
信息,因此在搜索过程中具有盲目性,不能对种群个体进行局部精细化搜索,导致算法具有较差的局
部搜索能力.纵然算法具有一定的全局搜索能力,但是仍然存在全局搜索和局部搜索不平衡的问题.

2 万有引力加速机理的布谷鸟算法(GASCS)

2.1 万有引力算法

受万有引力定律启发,伊朗学者 Esmat Rashedi 等人于 2009 年提出了万有引力搜索算法(gravitational
search algorithm,简称 GSA) [24] .GSA 算法的原理是:物质个体之间由于引力作用相互吸引,并且引力沿质量较大
的个体方向移动.物质个体的质量决定其万有引力的大小,质量越大的个体所受的引力越大.在外有引力的作用
下,物质个体位置不断变化,最终,整个群体都聚集在物质个体质量最大的周围,即逼近优化问题的全局最优解.
在万有引力算法中,借鉴理论物理学中质量定义的 3 种属性描述函数适应度值,即主动引力质量 M a 、被动
引力质量 M p 和惯性质量 M i .每个物质个体的位置对应优化问题解,其万有引力和惯性质量 M i 共同决定相应的
函数适应度数值.事实上,GSA 算法通过调节 M a ,M p 和 M i 来控制算法进化,促使群体中的物质个体聚集在万有引
力最大的物质个体附近,进而搜索到最优解.
GSA 算法模型包含物质个体的质量计算、引力计算、加速度计算和速度更新与位置更新.算法首先对解空
间内的物质个体位置和速度初始化.如文献[24,25]所示,设 D 维空间维度中进化至第 r 代时第 m 个物质个体的