一种混合重心重构花授粉改进算法

陈昌兴，王建彬，陈建平

（肇庆学院计算机科学与软件学院，肇庆526061）

0 引言

花授粉算法[1]是一种模拟花朵授粉行为的进化算法，与其他进化算法相比，其概念简单、参数少、容易实现。作为一种新的智能优化方法，花授粉算法已经成功应用于函数优化、气象预测、工程设计等领域，在有关问题上展示了较好的性能[2-5]。

目前，许多学者都提出了不同的改进策略，常见的改进方法主要围绕花授粉算法中的参数和授粉方式展开，包括概率大小、全局授粉时的莱维分布系数以及局部时的均匀分布系统等。Salgotra 等人[6]为算法设计了动态切换概率以提高算法的搜索能力；刘升等人[7]依据正余弦算法思想，通过将正余弦算法嵌入到基本花授粉算法中进行混合以解决局部收敛问题；王兴凡等人[8]通过在异花授粉时引入自适应步长提高搜索能力；段艳明等人[9]通过量子系统的态叠加特性以及波函数，使得算法能够按照一定的概率密度在解空间进行搜索，从而提高了求解的速度和精度；肖辉辉等人[10]则针对基本FPA 的全局寻优部分，利用个体的莱维飞行以及万有引力共同实现个体位置的更新，提高算法后期的收敛速度。

上述这些改进方法在一定程度上提高了算法的搜索能力，针对特定问题取得了较好的效果，但是依然存在前期进化速度慢、算法难收敛，后期全局搜索能力差的问题。为此，本文提出一种混合重心重构花授粉算法。基于杠杆力平衡原理，通过对函数重心的重构，对搜索空间进行合理压缩简化，提高算法前期的局部搜索能力，同时在算法后期引入惰性变异机制以增强算法的爬山能力，跳出局部最优。通过对测试函数的仿真实验，表明了算法改进的有效性。

1 基本花授粉算法

基本花授粉算法是一种进化算法，是受大自然中花朵授粉的行为启发而得到的。研究表明，自然界中的花授粉行为90%为异化授粉，而另外的10%为自花授粉。基于这一研究，Yang 等人[1]于2012 年提出了FPA 算法，其基本步骤如下：

Step1 设定及初始化FPA 的基本参数：变量的个数、各变量的取值范围、转换概率、种群数量、最大迭代次数等；

Step2 产生初始解xit：根据适应度函数计算适应度值，并从初始解中选出当前最优值作为当前全局最优解g*；

Step3 生成随机数rand ，并与转换概率p 进行比较，若p>rand，则按照式（1）进行全局搜索，其中L 为服从莱维分布的步长；

Step4 若p

Step5 将新产生的解与之前得到的解进行比较，若新解优于前解，则将前解替换为新解，否则保留前解，转下一步；

Step6 判断是否满足最大迭代条件，若满足，则停止迭代，输出最优解；否则，转Step3。

2 重心重构

2.1 物体重心与函数最优解的关系

在力学研究过程中，通过杠杆原理可知，物体的重心总是靠近其质量分布密集的区域，分布越稀疏的区域离重心的位置越远。为维持力矩平衡，质量越大的点离重心的距离越近，质量越小的点离重心的距离越远。如图1 所示，对于由函数f(x)围成的封闭区域，C表示它的最大函数值，通过分析可知，它的“重心”G 在最大值附近。

图1 重心与函数最优值的关系

由图1 可知，函数的重心与其全局最优值处于一个小的邻域内，该邻域的取值范围远小于函数的定义域。因此如果能够找到函数搜索空间的重心位置，也就可以确定其全局最优解的取值范围。

2.2 重心重构原理

对于复杂的优化问题，往往其函数值存在多个峰值，此时获取的函数重心落在全局最优值的邻域内的概率变低，这使得很难直接根据原函数重心位置来寻找全局最优值的邻域，因此需要进行函数重心的重构。本文利用函数填充技术[11]设计变换函数如下：

经过变换函数（3）填充以后的效果如图2 所示。

图2 函数填充效果

通过调节参数δ，将函数原来的寻优空间进行分割，大于δ 的搜索区域维持不变；小于δ 的区域用函数值ξ 进行填充，减小局部极值在搜索空间中所占的比例，从而增大全局最优极值的相对比重，重构重心在函数空间中的位置，提高重心落在最优值邻域内的几率。

3 花授粉算法的改进

3.1 算法搜索空间

基于上一节的分析，采用重心公式（4）迭代更新重心的位置，实现寻优空间的重心重构。

其中xp和F(xp)为前k-1 次迭代过程中出现的最优解及其函数值，M(k)为第k 次迭代时搜索区域范围内所产生的个体解的数量，即种群规模。

在传统的智能优化方法中，搜索范围一般是固定的。这种方式虽然能够确保全局最优位于原始的搜索区域内，但过大的搜索区域会增加寻优的次数和难度，不利于快速寻优。

为确保重构的重心能更加逼近全局最优所在的邻域，同时提高计算效率，搜索范围O(k)和种群规模M(k)需遵循以下原则：

（1）种群规模M(k)与搜索范围O(k)应成正比变化；

（2）搜索范围O(k)应随着迭代次数k 的增加不断减小。

令η=O(k)/O(k-1)<1，则经过k 次迭代以后的搜索范围为O(k)=ηkO(0)，其中O(0)为原始搜索区域范围，从而得到算法的初始搜索空间为：

3.2 惰性变异机制

在算法进化的中后期，由于花粉位置的过度集中，导致算法出现停滞现象，陷入局部最优，从而形成“惰性花粉”，即算法的适应值连续n 次迭代变化小于某一数值ρ。

为了避免算法陷入局部最优，应尽量在算法的中后期保持个体的多样性。当出现惰性花粉时，在函数的解空间中对其进行一定的操作，改善得算法搜索的全局性，从而更有可能获得全局最优解。考虑到FPA算法自身的进化机制，将以惰性花粉为中心的小邻域内的若干个花粉按照式（6）进行反向变异[12]：

其中xi为惰性花粉，oxi为变异后的新花粉，xmax和xmin为搜索空间的上界和下界。

3.3 算法的实现

基于以上分析，算法具体步骤为：

Step1 设定重心重构基本参数：重心重构种群规模M(k)，搜索范围压缩比η，填充函数参数δ 和ξ，各变量的取值范围，迭代次数k；设定和声搜索的基本参数，惰性花粉持续代数n 及其相应适应值的变化范围ρ；

Step2 根据杠杆原理进行重心重构；

a.按照公式（3）对原函数空间进行填充改造；

b.进行重心重构，通过公式（4）迭代产生新的重心；

Step3 判断是否到达迭代次数，如满足转下一步；否则返回Step2；

Step4 花粉授粉，以Oinit为初始搜索空间，初始化FPA 相关参数；

Step5 依据rand 与转换概率p 的大小，根据式（1）和式（2）机制产生新解；

Step6 计算新解的适应值，若新适应值优于已得到的最优适应值，则替换所对应的变量；

Step7 判断是否满足终止条件，如不满足则转下一步，否则算法结束；

Step8 判断是否出现惰性花粉，若出现，则按公式（6）进行反向变异，返回Step4；否则直接返回Step4。

4 仿真实验及分析

针对文献[8]测试的4 个基本的单模和多模函数，分别利用已有的PSO、HS、FPA 和GCRFPA 算法进行测试，从而比较了四种算法的求解效果和收敛速度。所有试验都是在硬件环境为Intel Core i3 处理器，内存8GB；软件环境为Windows 7 操作系统，MATLAB 2013a版本的机器上运行的。四个测试函数为：

（1）Sphere 函数：

搜索维数为2，搜索范围[-100,100]，最优解0。

（2）Ronsenbrock 函数：

搜索维数为10，搜索范围[-30,30]，最优解0。

（3）Ackley 函数：

搜索维数为10，搜索范围[-30,30]，最优解0。

（4）Griewank 函数：

搜索维数为10，搜索范围[-600,600]，最优解0。

在4 个经典测试函数中，Sphere 函数和Rosenbrock 函数是单模函数，分别用于测试算法的求解精度和收敛速度。Arckly 函数和Griewank 函数是多模函数，拥有多个局部极值点，用于测试算法的全局寻优能力。

为了分析每个算法的性能，每种算法单独运行100次，最大迭代次数max gen 为2000 次，种群规模为20。各算法的具体参数为：

对于PSO，C1=2，C2=2，权重W=0.8；

对于HS，和声记忆库大小HM=50，和声保留概率HMCR=0.8，微调概率PAR=0.5；

对于FPA，转换概率p=0.8 ，标准伽马函数参数λ=1.5；

对于GCRFPA，算法的重心重构迭代次数k 为5，搜索范围压缩比η=0.5，填充函数参数δ=0.01 和ξ =0.001，惰性和声持续代数为10 次，ρ 为0.0001。

依据以上分析，对上述函数进行运算，结果如表1-表5 所示。其中表1 表示的是Sphere 函数的重心重构过程，各个函数不同算法运行比较结果如表2 至表5所示。表中m 为100 次迭代得到的最优值的平均值，v 为方差，s 为成功率。平均最优值反映的是算法的收敛精度，方差反映算法的稳定性，成功率反映了算法的全局最优能力。

由表1 可知，只需要经过几次迭代，重心重构算法就可以非常好的压缩搜索空间，从而缩小了和声搜索算法的初始寻优空间，大大提高了和声搜索算法初期的局部搜索能力。

表1 Sphere 函数的重心重构过程

表2 Sphere 函数比较结果

表3 Rosenbrock 函数比较结果

表4 Arckly 函数比较结果

表5 Griewank 函数比较结果

由表2-表5 中可以看出，GCRFPA 算法找到的最优值、平均值、方差都比前面几个算法要好，成功率比前几个算法高。对于复杂的多峰函数，其他算法成功率低，而本算法仍能比较有效地跳出局部最优解，从而找到全局最优解。因此，从整体上看，GCRFPA 算法优于另外三种算法。

5 结语

本文对花授粉算法进行改进，提出一种混合重心重构花授粉算法。采用重心重构方法压缩简化函数的寻优空间，减小和声算法的搜索范围，弥补基本花授粉算法前期局部搜索能力弱的缺陷，后期采用惰性反向变异机制，提升算法的全局搜索能力。仿真实验结果表明GCRFPA 具有很好的收敛速度和跳出局部最优的能力。