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

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

度 a g 以及偏好随机游动方式产生的加速度 a p 均能快速聚集在全局最优解 nest_g.同时,由于向量 nest(k)−
nest(s)−a r 偏离全局最优解方向,因此在偏好随机游动方式中,能有效预防种群进化后期出现的迟滞现象.注意到
公式(16)中 p∈(0,+∞),且为确定的数,不同于传统 CS 算法中的控制缩放系数 q 为随机数.这种非随机处理方式能
够保留较好的种群个体,舍弃进化过程中出现的较差种群个体,提高算法寻优速度和收敛精度.
最后,针对第 3 点局限性中存在全局搜索和局部搜索不平衡的问题,GASCS 算法提出一种概率变异方法增
大种群进化的多样性,避免算法陷入局部搜索以及算法执行后期出现的迟滞现象.
假设 X , rm = (x (1) , r m , x (2) ,..., x ( )j , rm ,..., x ( )D , rm ) ,并且 x ( )j , rm ∈ [l ()j ,u ()j ] .执行概率变异操作时,首先从 X r,m 中以概率 1/D 选
, rm
取种群个体 x ()j , rm ,j∈[1,D];其次,利用公式(17)的 x ()j , rm 取代 x ()j , rm ,其中,k 为[1,D]内的随机整数,ξ为(0,1)内的均匀分
(j)
(j)
布随机数,l 和 u 分别为 x ()j , rm 的上界和下界;最后,通过概率变异将候选解 X r,m 更替为 X , rm ,并进入算法执行过
程,其中, X , rm = (x (1) , r m , x (2) , rm ,..., x ( )j , rm ,..., x ( )D , rm ) .经过概率变异后的种群进化获得更大的多样性,避免算法寻优过程单一
化而造成的全局搜索效率较低的问题.通过两个随机个体的位置向量差、当前搜索到的最优解及群体中宿主巢
穴所受到的万有引力加速度,获得下一次进化的方向,充分利用宿主巢穴及群体内部进化过程出现的有效信息:
⋅
⎧ ⎪ (u ()j + l ( )j )/2 (1 2 ξ ⋅ + − ) (u ()j − l ( )j )/2, j = k
x ()j , rm = ⎨ ()j (17)
⎪ ⎩ x , rm , j ≠ k
GASCS 算法在进化过程中不仅利用了 Levy 飞行随机游动方式的无限跳跃特性易于跳出局部最优解的特
点,而且采用概率变异增大算法的多样性,确保算法能够跳离局部最优解.因此,GASCS 算法较好地解决了 CS 算
法存在全局搜索和局部搜索不平衡的问题.
2.3 GASCS算法实现

基于 CS 算法存在的 3 点局限性,本文提出了具有万有引力加速机理的 GASCS 算法.该算法通过当前搜索
到的最优解、Levy 飞行随机游动和偏好随机游动方式产生的个体更新位置及宿主巢穴所受到的万有引力加速
度共同作用,获得下一次进化的方向及最佳巢穴位置,并采用概率变异方法,引导宿主巢穴沿全局最优解方向移
动,进而搜索到全局最优解.
GASCS 算法的执行步骤如下所示.
步骤 1. 算法初始化,种群为 N 个宿主巢穴,优化问题的空间维度 D,最大进化代数 W,发现概率 P a ,初始时
刻万有引力系数 G 0 ,算法控制参数θ,宿主巢穴的初始移动速度 V r,m ,其中,进化代数 r=1.
步骤 2. 计算随机化宿主巢穴位置 X r,m (m=1,2,…,N)对应的适应度函数值 f(X r,m ).
步骤 3. 由公式(10)计算 G r ,同时,由公式(7)和公式(8)计算当前最优值 f r,best 和最差值 f r+1,worst ,以及对应的
最优解 X r,gb .
步骤 4. 根据公式(5)和公式(6)计算宿主巢穴的质量 q r,m ,M r,m .
步骤 5. 分别根据公式(11)和公式(12)计算当前进化代数的宿主巢穴所受到的万有引力合力 F ()j 和加
, rm
速度 a ()j .
, rm
步骤 6. 采用公式(15)的 Levy 飞行随机游动方式产生新的宿主巢穴,按照发现概率 P a 舍弃候选解 X r+1,m .
步骤 7. 采用公式(16)的偏好随机游动方式产生新的宿主巢穴,替换步骤 6 中被舍弃的候选解.
步骤 8. 采用概率变异方法产生候选解 X r+ 1,m 对应的函数适应度值 (f X r+ 1,m ) .
步骤 9. 计算步骤 8 中种群产生的候选解对应的函数适应度值 (f X r+ 1,m ) ,同时更新当前最优值 f r+1,best

和最差值 f r+1,worst 以及对应的最优解 X r+1,gb .
步骤 10. 若满足算法终止条件,则输出当前进化的最优值及最优解,并停止算法;否则,转向步骤 3 继续执
行算法.