文章目录
- 一、理论基础
- 1、基本花授粉算法
- 2、基于多策略改进的花授粉算法
- （1）新全局搜索策略
- （2）引入精英变异策略的局部搜索策略
- （3）对劣解的改进策略
- （4）自适应调整转换概率
- 二、实验仿真及分析
- 三、参考文献
一、理论基础
1、基本花授粉算法
请参考这里。
2、基于多策略改进的花授粉算法
对基本FPA算法的搜索机制进行定性分析显示：基本FPA算法的搜索策略存在的不足制约着算法的收敛效果，包括存在收敛速度慢和易陷入局部最优等缺点。对于这些影响算法性能的不利因素，文献[1]对FPA算法进行了多策略改进。
（1）新全局搜索策略
从技术角度来说，FPA算法在全局授粉时，莱维飞行和最优个体(
x
b
e
s
t
x_{best}
xbest)对种群中的个体同时施加影响。由于受全局最优个体
x
b
e
s
t
x_{best}
xbest的吸引，FPA算法在优化简单问题时具有较快的收敛速度；但在解决复杂的优化问题时，若种群中的个体
x
b
e
s
t
x_{best}
xbest陷入到探索领域中的某些局部极小位置，则其他个体受
x
b
e
s
t
x_{best}
xbest的影响，也快速移动到
x
b
e
s
t
x_{best}
xbest所在的位置，使得(
x
i
t
−
x
b
e
s
t
x_i^t-x_{best}
xit−xbest)变得非常小，从而造成个体位置更新公式无效，因为
x
i
t
+
1
=
x
i
t
+
0
=
x
i
t
x_i^{t+1}=x_i^t+0=x_i^t
xit+1=xit+0=xit。在这种情况下，种群将停止进化，并且很难逃离局部最优。为了解决该问题，本文利用式(1)对原始公式进行改进：
x
i
t
+
1
=
x
i
t
+
γ
L
(
λ
)
(
x
i
t
−
x
b
e
s
t
+
x
i
1
t
−
x
i
2
t
+
x
i
3
t
−
x
i
4
t
)
(1)
x_i^{t+1}=x_i^t+\gamma L(\lambda)(x_i^t-x_{best}+x_{i_1}^t-x_{i_2}^t+x_{i_3}^t-x_{i_4}^t)\tag{1}
xit+1=xit+γL(λ)(xit−xbest+xi1t−xi2t+xi3t−xi4t)(1)其中，
i
1
i_1
i1、
i
2
i_2
i2、
i
3
i_3
i3、
i
4
i_4
i4分别是从当前群体中随机选取的4个不同于
i
i
i的下标，其余变量的含义同原始公式相同。
从式(1)可以看出：在莱维飞行机制的基础上，引入了两组差异矢量，增加了种群个体之间的差异性，提高了算法在多维空间的探索能力，有利于抑制算法早熟收敛，提升算法的性能。
（2）引入精英变异策略的局部搜索策略
在基本花授粉算法的局部搜索部分，由于个体缺乏对种群中最优个体良好经验的继承和学习机制，个体的进化方向具有很强的盲目性，这导致了对搜索全局最优解的计算量增大，降低了算法的收敛速度。
为了解决上述存在的这个问题，基于差分进化算法的思想和FPA算法的特性，把差分进化算法中的经典变异算子DE/best/2的思路融入到局部授粉中，提出一种新的复合型局部搜索机制：如果
r
a
n
d
<
ζ
rand<\zeta
rand<ζ，则按式(2)进行处理；否则按式(3)进行处理。
v
i
=
x
i
+
δ
(
x
r
2
−
x
r
3
)
(2)
v_i=x_i+\delta(x_{r_2}-x_{r_3})\tag{2}
vi=xi+δ(xr2−xr3)(2)
v
i
=
x
b
e
s
t
+
α
(
x
r
1
−
x
r
2
+
x
r
3
−
x
r
4
)
(3)
v_i=x_{best}+\alpha(x_{r_1}-x_{r_2}+x_{r_3}-x_{r_4})\tag{3}
vi=xbest+α(xr1−xr2+xr3−xr4)(3)其中，
r
a
n
d
rand
rand是
[
0
,
1
]
[0,1]
[0,1]上服从均匀分布的随机数；
ζ
=
1
−
t
/
Max
_
i
t
e
r
\zeta=1-t/\text{Max}\_iter
ζ=1−t/Max_iter，
t
t
t是当前迭代次数，
Max
_
i
t
e
r
\text{Max}\_iter
Max_iter为最大迭代次数；参数
δ
\delta
δ、
α
\alpha
α是服从高斯分布且均值和标准偏差分别为0.5、0.1，其作用是用于控制算法的演化速度；
n
n
n为种群数，
i
∈
(
1
,
2
,
⋯
,
n
)
i\in(1,2,\cdots,n)
i∈(1,2,⋯,n)为当前个体的下标，
r
1
r_1
r1、
r
2
r_2
r2、
r
3
r_3
r3、
r
4
r_4
r4为4个不同的随机个体的下标，
x
b
e
s
t
x_{best}
xbest为当前种群中最优个体。
从上述改进的局部授粉策略可知：式(2)采用变异策略增加种群个体的差异性，从而达到提升算法的全局优化能力，但算法的搜索速度比较慢；对于式(3)运用的变异机制，是通过精英个体对其他个体的演化方向进行引导，同时利用精英个体的信息有利于开发其周围领域，提高FPA算法的搜索效率，从而提升了算法的收敛速度和开采能力，但这一策略也容易导致FPA算法陷入局部极小问题。为了能够使这两种方法优势互补，提高FPA算法的寻优能力，通过一个线性递减概率规则融合这两种变异机制，构建MIFPA算法的新局部搜索策略。
依据
ζ
=
1
−
t
/
Max
_
i
t
e
r
\zeta=1-t/\text{Max}\_iter
ζ=1−t/Max_iter可知：在算法进化初期，选择式(2)的变异策略的概率要比选择式(3)的变异机制的概率大，这有利于种群个体在演化初期扩大搜索空间。因为从式(2)可以发现：在算法进化初期，由于个体之 间的差异性比较大，则(
x
r
2
−
x
r
3
x_{r_2}-x_{r_3}
xr2−xr3)值较大，这使得种群个体有利于向更广的搜索范围进行扩散，易于算法找到最优值。在算法的演化后期，个体选择式(3)的变异策略的概率要比选择式(2)的变异机制的概率大，这有利于加快算法的收敛速度。因为式(3)利用精英个体对种群其他个体的演化方向进行了引导，促进种群的其他个体加速向精英个体靠近，达到提高算法的搜索速度和计算精度。综上所述，通过线性递减概率规则可使这两种变异策略优势互补，提升算法的收敛能力。
（3）对劣解的改进策略
在基本花授粉算法中，总是以贪婪式演化策略选择较优个体来保证群体向前进化，即：经过全局搜索或局部搜索后，产生一个新个体，只有当子代的适应度值优于父代才能演化。然而，依据FPA算法的具体流程可知：如果子代劣于父代，则父代直接保留到下一代，并没有对其作任何改进措施，算法直接进入下一次进化，这使得本次迭代的计算资源严重浪费，增加了对全局最优解的搜索计算量，降低了算法的收敛速度，且容易造成算法收敛精度不高。
针对基本花授粉算法存在的这一不足，在算法进入下次迭代之前，如果父代没有得到改善，则利用式(4)重新产生一个新个体，若新解优于原始解，则用新解代替原始解：
x
n
e
w
=
2
×
cos
(
(
π
×
t
)
/
(
2
×
Max
_
i
t
e
r
)
)
×
φ
×
x
t
(
r
)
(4)
x^{new}=2\times\cos((\pi\times t)/(2\times\text{Max}\_iter))\times\varphi\times x_t(r)\tag{4}
xnew=2×cos((π×t)/(2×Max_iter))×φ×xt(r)(4)其中，
φ
\varphi
φ是
[
−
1
,
1
]
[-1,1]
[−1,1]上服从均匀分布的随机数，其作用是使种群个体实现随机游走；
Max
_
i
t
e
r
\text{Max}\_iter
Max_iter为最大迭代次数，
x
t
(
r
)
x_t(r)
xt(r)是迭代次数为
t
t
t时种群中的一个随机个体；
x
n
e
w
x^{new}
xnew为产生的新个体，
t
=
1
,
2
,
⋯
,
Max
_
i
t
e
r
t=1,2,\cdots,\text{Max}\_iter
t=1,2,⋯,Max_iter。
通过融入余弦函数搜索因子，利用其振荡特点使得种群个体位置具有振荡性，扩展个体的搜索范围，有
效引导个体跳出局部最优,提高解的质量。
（4）自适应调整转换概率
通过实验可知：如果转换概率
p
p
p取固定的值，不利于FPA找到全局最优解。为了解决这一不足，采用式(5)对
p
p
p进行自适应调整，提高FPA算法的性能和灵活性。
p
=
p
min
+
(
p
max
−
p
min
)
×
(
(
Max
_
i
t
e
r
−
t
)
/
Max
_
i
t
e
r
)
(5)
p=p_{\min}+(p_{\max}-p_{\min})\times((\text{Max}\_iter-t)/\text{Max}\_iter)\tag{5}
p=pmin+(pmax−pmin)×((Max_iter−t)/Max_iter)(5)其中，
p
max
p_{\max}
pmax、
p
min
p_{\min}
pmin分别是
p
p
p的最大值(取0.9)和最小值(取0.2)，
Max
_
i
t
e
r
\text{Max}\_iter
Max_iter是最大迭代次数，
t
t
t是当前迭代次数。
根据上述式(5)和改进算法的流程可知：在算法的进化初期，变量
t
t
t的值较小，则转换概率
p
p
p的取值较大，算法更偏向于异花授粉(全局搜索)；当算法进入演化后期，变量
t
t
t的值越来越大，转换概率
p
p
p的值越来越小，则算法更倾向于自花授粉(局部搜索)。综上所述。通过
p
p
p的自适应调整策略，能够更有效地解决算法的全局搜索和局部搜索之间的平衡问题，从而更有利于提高算法的全局优化能力。
二、实验仿真及分析
MIFPA算法对FPA算法进行了4个方面的改进：在全局授粉部分增加了两组随机个体的差异矢量；通过一个线性递减概率规则，融合两种变异机制对局部授粉部分进行改进；自适应地调整转换概率；引入余弦函数搜索因子对劣解进行改善。为了验证这些改进策略分别对基本FPA算法的性能提升的效果，分别把这些策略融入到基本FPA算法中，并比较这些不同策略对基本FPA算法的性能改进效果，从而达到证明这些策略的效用。利用不同方法改进的FPA算法如下：
- IGFPA：在基本FPA算法的全局搜索部分增加了两组随机个体的差异矢量改进后的算法；
- ILFPA：对基本FPA算法的局部搜索部分改进后的算法；
- IPFPA：采用自适应调整转换概率的FPA算法；
- CFPA：融入余弦函数搜索因子的FPA算法；
- MIFPA：引进上述所有改进策略的FPA算法。
将MIFPA与FPA和上述4种不同方法改进的FPA算法进行对比，以文献[1]表1中的F1、F2(单模态高维函数/30维)、F6、F8(非旋转的多模态高维函数/30维)、F10、F11(多模态低维函数/4维、4维)为例，实验设置种群规模为30，最大迭代次数为500，每种算法独立运算30次，结果显示如下：
- 函数适应度值的收敛曲线对比及收敛结果
函数：F1
FPA：最优值: 1102.6762, 最差值: 2709.4261, 平均值: 1816.8628, 标准差: 398.424
IGFPA：最优值: 278.6499, 最差值: 865.4833, 平均值: 543.0433, 标准差: 164.4604
ILFPA：最优值: 335.6107, 最差值: 1468.8504, 平均值: 741.2832, 标准差: 275.4976
IPFPA：最优值: 225.1061, 最差值: 789.9161, 平均值: 454.1126, 标准差: 145.1454
CFPA：最优值: 0, 最差值: 0, 平均值: 0, 标准差: 0
MIFPA：最优值: 0, 最差值: 0, 平均值: 0, 标准差: 0
函数：F2
FPA：最优值: 10939.2367, 最差值: 25554.5761, 平均值: 18051.0455, 标准差: 3143.089
IGFPA：最优值: 5064.7047, 最差值: 16534.6618, 平均值: 11121.1297, 标准差: 2790.6069
ILFPA：最优值: 492.2353, 最差值: 1783.3709, 平均值: 1107.1141, 标准差: 351.6503
IPFPA：最优值: 12338.2242, 最差值: 26571.4515, 平均值: 17969.6029, 标准差: 3915.6045
CFPA：最优值: 0, 最差值: 0, 平均值: 0, 标准差: 0
MIFPA：最优值: 0, 最差值: 0, 平均值: 0, 标准差: 0
函数：F6
FPA：最优值: 13.0261, 最差值: 17.9042, 平均值: 15.9319, 标准差: 1.1135
IGFPA：最优值: 10.4705, 最差值: 16.9197, 平均值: 13.7115, 标准差: 1.5584
ILFPA：最优值: 7.0271, 最差值: 10.9861, 平均值: 9.1135, 标准差: 1.2454
IPFPA：最优值: 9.1531, 最差值: 14.3869, 平均值: 11.3617, 标准差: 1.3076
CFPA：最优值: 8.8818e-16, 最差值: 8.8818e-16, 平均值: 8.8818e-16, 标准差: 0
MIFPA：最优值: 8.8818e-16, 最差值: 8.8818e-16, 平均值: 8.8818e-16, 标准差: 0
函数：F8
FPA：最优值: 19.2057, 最差值: 12779.5492, 平均值: 822.5082, 标准差: 2446.8099
IGFPA：最优值: 7.5994, 最差值: 27.365, 平均值: 12.36, 标准差: 4.3884
ILFPA：最优值: 4.0587, 最差值: 32.3221, 平均值: 9.0326, 标准差: 5.5655
IPFPA：最优值: 6.7877, 最差值: 25.2227, 平均值: 13.0217, 标准差: 3.7959
CFPA：最优值: 0.005025, 最差值: 0.050079, 平均值: 0.018714, 标准差: 0.010305
MIFPA：最优值: 0.0030858, 最差值: 0.045018, 平均值: 0.019766, 标准差: 0.010802
函数：F10
FPA：最优值: 0.00049111, 最差值: 0.0012362, 平均值: 0.00087339, 标准差: 0.00017134
IGFPA：最优值: 0.00034314, 最差值: 0.00076413, 平均值: 0.00059345, 标准差: 0.00012123
ILFPA：最优值: 0.00030749, 最差值: 0.0012232, 平均值: 0.00036854, 标准差: 0.00023232
IPFPA：最优值: 0.00062474, 最差值: 0.0010752, 平均值: 0.00077192, 标准差: 9.6805e-05
CFPA：最优值: 0.00030749, 最差值: 0.00060913, 平均值: 0.00033403, 标准差: 7.632e-05
MIFPA：最优值: 0.00030749, 最差值: 0.00030749, 平均值: 0.00030749, 标准差: 1.2613e-19
函数：F11
FPA：最优值: -10.1482, 最差值: -7.879, 平均值: -9.7537, 标准差: 0.50232
IGFPA：最优值: -10.1532, 最差值: -10.1509, 平均值: -10.1526, 标准差: 0.00049563
ILFPA：最优值: -10.1532, 最差值: -10.1532, 平均值: -10.1532, 标准差: 3.2574e-10
IPFPA：最优值: -10.1526, 最差值: -9.1482, 平均值: -10.0558, 标准差: 0.19797
CFPA：最优值: -10.1532, 最差值: -5.0552, 平均值: -6.4144, 标准差: 2.2925
MIFPA：最优值: -10.1532, 最差值: -5.0552, 平均值: -6.2447, 标准差: 2.1931
- 独立运行30次的函数最优适应度值比较特性图
实验结果表明：MIFPA算法是一种富有竞争力的新算法，其解的质量、鲁棒性和收敛速度、时间复杂度等方面总体上都要优于对比算法。
三、参考文献
[1] 肖辉辉, 万常选. 基于多策略的改进花授粉算法[J]. 软件学报, 2021, 32(10): 3151-3175.
