Page 183 - 《软件学报》2021年第10期

肖辉辉 等:基于多策略的改进花授粉算法 3155

全局最优解的计算量增大,降低了算法的收敛速度.
为了解决上述存在的这个问题,基于差分进化算法的思想和 FPA 算法的特性,本文把差分进化算法中的经
典变异算子 DE/best/2 的思路融入到局部授粉中,提出一种新的复合型局部搜索机制:如果 rand<,则按式(7)进行
处理;否则按式(8)进行处理.
v  x  i  (x  2 r x 3 r ) (7)
i
v  i x best   (x  1 r x  2 r x  3 r x 4 r ) (8)
其中,rand 是[0,1]上服从均匀分布的随机数;=1t/Max_iter,t 是当前迭代次数,Max_iter 为最大迭代次数;参数、
是服从高斯分布且均值和标准偏差分别为 0.5、0.1,其作用是用于控制算法的演化速度;n 为种群数,i(1,2,…,n)
为当前个体的下标,r 1 、r 2 、r 3 、r 4 为 4 个不同的随机个体的下标,x best 为当前种群中最优个体.
从上述改进的局部授粉策略可知:公式(7)采用变异策略增加种群个体的差异性,从而达到提升算法的全局
优化能力,但算法的搜索速度比较慢;对于公式(8)运用的变异机制,是通过精英个体对其他个体的演化方向进行
引导,同时利用精英个体的信息有利于开发其周围领域,提高 FPA 算法的搜索效率,从而提升了算法的收敛速度
和开采能力,但这一策略也容易导致 FPA 算法陷入局部极小问题.为了能够使这两种方法优势互补,提高 FPA 算
法的寻优能力,本文通过一个线性递减概率规则融合这两种变异机制,构建 MIFPA 算法的新局部搜索策略.
同时,从上述新的局部搜索策略可以看出:在进化过程中,通过线性递减概率规则“rand<”对两种变异策略
进行调节,如果 rand 产生的随机数小于,则个体执行公式(7)的变异机制;否则,执行公式(8)的变异策略.
依据=1t/Max_iter 可知:在算法进化初期,选择公式(7)的变异策略的概率要比选择公式(8)的变异机制的
概率大,这有利于种群个体在演化初期扩大搜索空间.因为从公式(7)可以发现:在算法进化初期,由于个体之
间的差异性比较大,则 (x  x 3 r ) 值较大,这使得种群个体有利于向更广的搜索范围进行扩散,易于算法找到最优
2 r
值.在算法的演化后期,个体选择公式(8)的变异策略的概率要比选择公式(7)的变异机制的概率大,这有利于加快
算法的收敛速度.因为公式(8)利用精英个体对种群其他个体的演化方向进行了引导,促进种群的其他个体加速
向精英个体靠近,达到提高算法的搜索速度和计算精度.综上所述,通过线性递减概率规则可使这两种变异策略
优势互补,提升算法的收敛能力.

2.3 对劣解的改进策略
在基本花授粉算法中,总是以贪婪式演化策略选择较优个体来保证群体向前进化,即:经过全局搜索或局部
搜索后,产生一个新个体,只有当子代的适应度值优于父代才能演化.然而,依据 FPA 算法的具体流程可知:如果
子代劣于父代,则父代直接保留到下一代,并没有对其作任何改进措施,算法直接进入下一次进化,这使得本次
迭代的计算资源严重浪费,增加了对全局最优解的搜索计算量,降低了算法的收敛速度,且容易造成算法收敛精
度不高.
针对基本花授粉算法存在的这一不足,在算法进入下次迭代之前,如果父代没有得到改善,则利用公式(9)重
新产生一个新个体,若新解优于原始解,则用新解代替原始解:
x new =2cos((t)/(2Max_iter))x t (r) (9)
其中,是[1,1]上服从均匀分布的随机数,其作用是使种群个体实现随机游走;Max_iter 为最大迭代次数,x t (r)是
迭代次数为 t 时种群中的一个随机个体;x new 为产生的新个体,t=1,2,…,Max_iter.
由上述可以看出:原始解的质量获得提升的概率得到提高,从而达到提高 FPA 算法解的质量.下面就公式(9)
可改善算法解的质量、提高算法优化能力的原因进行分析.
(1) 公式(9)能够有效避免随机产生的新个体(解)的质量太差(新个体远离全局最优个体 x best )而影响算法的
搜索速度.从公式(9)中可以看出:新个体的产生是以 x t (r)为中心,充分利用原有个体的信息引导新个体在其四周
产生,使其产生的新个体的位置距全局最优个体 x best 更近,避免了由于产生的新个体质量差而导致算法的收敛
速度慢.
(2) 依据上述新的全局搜索方程(6)和新的局部搜索方程(8)可以发现:在新构建的搜索策略中都采用了最