基于t-分布精英保留机制的花朵授粉算法

张 超

(宿州职业技术学院计算机信息系，安徽 宿州 234101)

自然界中的很多生物种群涌现出不同形式的群体行为特征。学者们对这些智能涌现的群体行为模式进行研究，仿生设计了各种元启发式群智能优化算法，如粒子群算法、蝙蝠算法、遗传算法、和声算法、蚁群算法等。这些算法因其设计简单、结构灵活，已在自然科学和工程等领域被广泛应用[1]。花朵授粉算法[2-3](Flower Pollination Algorithm，FPA)是基于自然界中的花授粉过程，设计的一种智能优化算法。算法结构简单，参数少，使用转换概率参数P平衡全局搜索和局部搜索。目前花朵授粉算法已被成功应用到交通流预测[4]、神经网络优化[5-6]、大整数规划[7]、产品拆卸序列规划[8]等领域。

但花朵授粉算法也存在易陷入局部最优，算法迭代后期收敛速度慢等不足[9]，特别，对于局部极值较多、较复杂的高维优化问题，算法的收敛精度不高[10]。为此，国内外学者对花朵授粉算法进行了优化和改进研究工作。文献[11]等利用logsig函数对解进行变换，映射到0-1空间中，提出了二进制花朵授粉算法。文献[12-13]分别对花朵授粉算法的两个控制参数：转换概率p和全局搜索时的移动步长缩放因子γ做取值对比试验，得出p=0.2，γ=16时花授粉算法对大多数测试函数的寻优能力更好。文献[14-15]认为初始解的质量影响花朵授粉算法的寻优能力，为此分别通过萤火虫算法、粒子群算法、和声算法获得待优化问题的最优解，并将该最优解作为花朵授粉算法的初始解，以期提高花朵授粉算法的寻优精度和速度。文献[16-17]中分别把杂草算法和差分进化算法的思想融入到花朵授粉算法中，通过扩展种群的多样性提高算法的全局搜索能力。文献[18-19]将量子行为引入到花朵授粉算法中，分别利用量子的随机性搜索、态叠加特性增强花朵授粉算法的全局搜索能力。文献[20]等使用精英混沌搜索对种群中部分花朵个体进行变异，提高了花朵授粉算法的寻优速度。文献[21]等将精英保留机制引入到花朵授粉算法中，使用外部存档法对个体的适应度进行排序，按一定比例选择适应度好的个体进入下一迭代，通过精英个体的引导，提高算法的收敛速度。文献[22]将引力搜索机制添加到基本花朵授粉算法的全局搜索部分，使用万有引力牵制Levy飞行的随机游走，提高了算法的收敛精度。

以上改进策略取得了良好的效果，但花授粉算法的寻优性能仍有待提高。鉴于此，本文提出一种基于t-分布算子的精英保留机制花朵授粉算法。改进算法在全局搜索时引入精英概率保留参数pe，通过pe将全局搜索时花朵个体位置更新分为两种方式：一是基本算法自身的Levy飞行机制；二是将经过t-分布变异的精英个体位置信息赋予花朵个体。该机制通过精英概率保留参数平衡种群的多样性和集中性，提高算法的收敛精度。改进算法在进行局部搜索时，使用具有较好局部搜索能力的高斯变异，代替基本FPA算法的随机数扰动因子，提升算法的局部开发能力。拟选用12个标准测试函数进行仿真实验，12个函数包括高维单峰函数、高维多峰函数及低维局部极值较多函数，以验证本文提出改进策略的有效性。

1 花朵授粉算法

花朵授粉算法(Flower Pollination Algorithm，FPA)假设一株花只开一朵花和繁衍一个花粉配子，并遵循以下四个理想原则：(1)异花授粉是蜜蜂、果蝇等传播者遵循Levy飞行轨迹进行的全局搜索；(2)局部搜索过程通过模拟显花植物自花授粉实现；(3)花的繁衍概率与两朵花的相似性成比例关系；(4)转换概率参数p∈[0，1]控制两类授粉过程的转换。整个授粉过程更倾向于自花授粉。

基于以上假设，花朵授粉算法基本步骤如下：

(1)初始化参数。对迭代次数、搜索变量的维度、转换概率、种群规模、步长缩放因子等算法参数进行初始设置。

(2)花朵种群初始化。在搜素域内生成n朵花，花朵个体位置记为xi，并记录最佳花朵位置x*。

(3)算法迭代寻优。生成一个随机数γ，如果转换概率p>γ，按公式(1)进入异花授粉的全局搜索过程。

(1)

式中：x*是当前迭代的最优解，xit是第i个花朵在第t次迭代的解，γ为缩放因子，L为服从λ为指数的Levy分布的随机数，L使用公式(2)计算。

(2)

式中：λ=3/2，Γ(λ)为标准伽玛函数。

如果转换概率p<γ，算法进入自花授粉的局部搜索过程，其计算公式如下：

(3)

式中：ε是[0，1]之间的随机数，xjt、xkt是同类型植物不同花朵的花粉配子。

(4)适应度值排序，记录当前最优花朵信息。

(5)重复步骤(3)至(4)，算法进入迭代寻优搜索，直至满足迭代结束条件为止。

2 改进花朵授粉算法

2.1 全局搜索改进策略

全局搜索是在当前最优花朵个体引导下，使用能够体现蜜蜂等昆虫飞行轨迹的Levy飞行函数，对组成花朵位置的各维度进行变异生成新解。Levy飞行偶尔会以较大步长跳跃且方向多变的特点，一方面维持了种群的多样性，使算法能够跳出局部极值的束缚，但也可能因跳跃太大导致最优花朵个体信息丢失，从而影响算法的收敛精度。精英个体是进化过程中性能表现较好的个体，对种群的进化起着关键的引导作用。维护种群的多样性可以使算法在更大的可行空间内搜索，提高全局探测能力，而充分利用精英个体的信息可以提高算法的全局收敛性。鉴于此种思想，为花朵授粉算法的全局搜索过程添加基于学生t-分布(简称t分布)的精英概率保留机制。

当花朵授粉算法的转换概率p控制算法进入全局搜索时，设置一个精英概率保留参数pe∈[0，1]，并生成一个随机数γ，如果pe>γ，使用公式(4)计算全局搜索生成新解方式，反之，仍按原算法公式(1)计算。这样将花朵授粉算法的全局搜索，通过精英保留概率pe分为两个部分进行：一是原算法通过Levy飞行进行的全局搜索，充分维护了种群的多样性；二是通过保留最优个体位置信息，并对最优个体位置使用t-分布变异算子进行扰动计算，充分利用精英个体信息提高算法收敛精度。

xnew=xold-best+ω*t(Iteration)⊗xold-best

(4)

式中：xold-best为当前迭代的最优解，Iteration是迭代次数计数参数，t(Iteration)是以Iteration为自由度的t-分布，⊗为点乘符号，ω为缩放因子，ω使用公式(5)计算。

ω=a+(b-a)*(T-t)/T

(5)

式中：a=0.1，b=1，ω的取值随着迭代次数的增加逐渐减小，T为最大迭代次数。

公式(4)对最优解进行t-分布变异，在最优解附近生成新解，此种机制使精英个体信息得以保留到下一迭代中去，引导种群朝着最优位置进化。为了防止算法在此过程中被局部极值吸引，导致算法早熟，迭代前期ω取较大值，在保留精英个体信息的同时，利用t-分布算子特性维护种群多样性，防止算法被局部最优值吸引；迭代后期ω取较小的值，可以使花朵精英个体的信息充分保留，从而提高算法的收敛精度。t-分布随着自由度参数Iteration值的增长，数值分布状态由柯西分布逐渐向高斯分布逼近，自由度为1时，t-分布与柯西分布曲线重合，当自由度大于30以后，t-分布曲线形态开始趋向于高斯分布曲线形态，直至趋于无穷大时，t-分布和高斯分布曲线无限重合。在智能优化算法中引入高斯分布变异，已被证明能够获得良好的局部搜索能力，而引入柯西分布变异，能够扩大搜索空间，维持种群的多样性，增加算法跳出局部极值的能力。在花朵授粉算法迭代的早期阶段，自由度参数Iteration取值较小，t-分布主要呈现柯西分布特征，有助于维护种群多样性，提升算法的全局搜索能力；算法迭代进行到中后期，t-分布主要呈现高斯分布特征，有助于算法在最优花朵周围，进行更精细、稳定的局部探测，提高收敛精度。

2.2 局部搜索改进策略

原算法在进行局部搜索时，使用公式(3)生成新解。公式(3)为同类型植物不同花朵的花粉位置各维度，添加随机数扰动生成新解，因随机数的生成分布不稳定，为此本文使用高斯变异替代原算法的随机数扰动生成局部新解的方式，即使用公式(5)代替原算法的公式(3)。利用高斯变异良好的局部搜索能力，提高算法的收敛速度。

(5)

式中：N(0，1)为μ=0，σ=1的高斯分布，xjt、xkt是同类型植物不同花朵的花粉配子。

2.3 TFPA算法的执行流程

改进的算法记为TFPA，其算法流程如下：

1)初始化参数。对迭代次数、搜索变量的维度、转换概率、精英保留概率、种群规模、步长缩放因子等算法参数进行初始设置。

2)花朵种群初始化。在搜素域内生成n朵花，花朵个体位置记为xi，并记录最佳花朵位置x*。

3)生成一个随机数γ1，如果转换概率p>γ1，算法进入全局搜索，再随机生成一个随机数γ2，如果精英保留概率pe>γ2，按公式(4)进行位置更新，反之，按公式(1)进行位置更新。

4)如果转换概率p<γ1，算法进入局部搜索，按公式(5)进行位置更新。

5)适应度值排序，记录当前最优花朵信息。

6)重复步骤3)至5)，算法进入迭代寻优搜索，直至满足迭代结束条件为止。

3 实验与结果分析

3.1 实验方案和测试函数

本节对基本花朵授粉算法FPA和改进的TFPA算法做对比实验。分别从固定迭代次数下的收敛精度、固定精度下的收敛速度、在特别高维上的寻优性能及时间复杂度四个方面，对实验结果进行分析。

仿真实验选择12个标准测试函数，函数的名称、表达式、类型、变量范围、理论极值和目标精度设定如表1所示。文献[23]指出，维度越大、目标精度越高、变量取值范围越大，寻优难度就越大。为此，12个标准测试函数均使用比较严格苛刻的参数设置。部署仿真实验的机器配置：Win10系统(64位)，内存：4GB，CPU主频：2.50GHz。

算法参数设置：花朵种群规模设为20，最大迭代次数设为800，精英保留概率pe=0.1，转换概率和步长缩放因子取值：p=0.2，γ=16。

表1 标准测试函数

3.2 实验结果分析与比较

1)固定迭代次数下的收敛精度比较

使用基本FPA算法和本文改进的TFPA算法，对表1中的12个标准测试函数进行函数寻优。比较两种算法在最差值、最优值、优化平均值、标准差4个指标上的性能优劣。为了防止偶然性带来的误差，仿真程序分别随机独立运行50次，表2为实验结果。表2中TFPA算法在Sphere、Schwefelf、Chung Reynolds、Griewank、Ackley、Rastrigin、Exponential、Csendes、Shubert、Schaffer F6十个函数上，在30维的情况下，每次均能收敛到函数的理论极值，而FPA算法的收敛情况与函数的理论极值相差甚远。Shubert、Schaffer F6是低维多局部极值函数，TFPA算法每次均能收敛到函数的理论极值，而FPA算法均不能收敛到函数的理论极值。Rosenbrock函数被称为香蕉函数，不易获得理论极值，在30维时，TFPA算法在四个指标上均优于FPA算法，且FPA算法的收敛精度误差偏大。Zakharov函数的理论极值为0，TFPA算法在四个指标上均优于FPA算法，TFPA算法的寻优平均值为1.197 1×10-64，FPA算法的寻优平均值为8.977 5×101，TFPA算法的最差值为2.735 2×10-63也比FPA算法的最优值3.878 0×101高出64个数量级。

表2 实验结果

图1为TFPA和FPA算法的适应度收敛曲线比较图，图1中除了f9、f11、f12三个函数外，其他函数的适应度值均做了10为底的对数处理。从图1中可知，TFPA算法收敛到最优值的速度明显优于FPA算法。TFPA算法在f1、f3～f7、f10七个函数上适应度曲线出现间断，表明算法已经收敛到函数理论极值0(对数的真数为0时不显示)。

综上所述，改进的TFPA算法在高维多峰、高维单峰及低维多极值函数上均有优越的寻优性能，在10个函数上均能每次都收敛到函数的理论极值，在Zakharov、Rosenbrock函数上的收敛精度大幅提高，表明改进的TFPA算法有效的提升了花朵授粉算法的收敛精度。

图1 TFPA和FPA算法的适应度收敛趋势比较图

2)固定精度下的收敛速度比较

按照表1中设定的目标精度，比较FPA和TFPA算法的平均迭代次数和寻优成功率。FPA算法在预设目标精度下，均不能成功收敛到固定精度，而改进的TFPA算法在较高目标精度设定下，均能百分百成功收敛到固定精度。TFPA算法在12个函数上，收敛到目标精度使用的迭代次数分别为：33.3、31.5、30.2、24.7、38、40.8、41.8、217.5、169.2、43.2、846.4、51.3。TFPA算法在Shubert函数上平均迭代次数达到846.4，而在其他11个函数上均能使用比较少的迭代次数收敛到固定精度，从而说明改进的TFPA算法在收敛速度上有显著提升。

3)在高维上的实验结果

为了验证TFPA算法在高维函数上的优越性能，做两种算法在512维上的对比实验，程序独立运行50次，比较FPA和TFPA算法在最差值、最优值、优化平均值、标准差四个指标上的性能，实验结果如表3所示。

选择3个高维单峰函数，4个高维多峰函数做实验，从表3中可知，TFPA算法在Sphere、Chung Reynolds、Griewank、Ackley、Rastrigin、Exponential六个函数上每次均能收敛到函数的理论极值，50次实验寻优结果的标准差均为0，而FPA算法的寻优结果与函数的理论极值相差甚远。以Sphere为例，其理论极值为0，而FPA算法50次实验的寻优平均值为7.544 7×106。对于Schwefelf函数，TFPA算法的优化平均值为4.793 7×10-303，最差值也达到1.071 0×10-301的数量级，而FPA算法因为寻优结果太大，结果显示为inf。因此，从衡量算法性能的四个指标结果看，TFPA算法在高维函数上表现出了优越的寻优性能。

表3 TFPA和FPA在512维上的寻优结果

4)时间复杂度分析

一个优秀的智能优化算法在表现卓越寻优性能的同时又要兼顾低的时间复杂度。改进算法的时间复杂度应该不比原算法更高，运行时间不宜过长。表4为TFPA算法和FPA算法在7个高维函数上维数在30维，200维，512维上的平均运行时间。从表4的结果可知，在30维时TFPA的运行时间略高于FPA，在200维、512维时TFPA运行时间少于FPA算法，且随着维数增加TFPA相对于FPA所用时间大幅减少，而寻优精度正如表3所示得到大幅提高。说明基于t-分布的精英概率保留机制，通过引入精英个体保留概率，对最优个体位置使用t-分布变异算子进行扰动计算，使得最优个体位置信息能够引导算法快速朝着最优解靠近，提高了算法收敛精度，利用高斯变异良好的局部搜索能力，提高了算法的收敛速度。

表4 TFPA和FPA平均运行时间

综上可得出，本文基于t-分布精英保留机制的花朵授粉算法，在全局搜索时通过设置精英概率保留参数，使得算法在寻优过程中一部分最优解得到保留，并对保留的最优解实施t-分布扰动变异，能够引导算法快速朝着最优解靠近，从而提高了算法的收敛精度。在局部搜索时使用高斯变异代替原算法随机数扰动因子，高斯变异具有优越的局部开发能力，从而有效提高了算法的收敛速度。因此，改进的TFPA算法具有良好的鲁棒性和更高的收敛精度及速度。

4 结论

本文改进的TFPA算法在维度为30维时，在3个高维单峰和5个高维多峰测试函数上均能收敛到函数的理论极值。在2个低维多极值函数上也均能收敛到函数的理论极值。在固定精度下能够使用很少的迭代次数达到目标精度。在512维高维情况下，TFPA在Sphere、Chung Reynolds、Griewank、Ackley、Rastrigin、Exponential六个函数上均能收敛到函数的理论极值，并且实验的维数从30维递增到512维时，TFPA寻优结果的优化均值不变，均值平均变化率为0。从而表明，基于t-分布精英概率保留机制的花朵授粉算法，具有良好的鲁棒性，显著提高了算法的收敛精度和速度。