混合改进的花朵授粉算法*

陶志勇, 崔新新

(辽宁工程技术大学 电子与信息工程学院,辽宁 葫芦岛 125100)

0 引 言

花朵授粉优化算法[1](flower pollination algorithm,FPA)是由Yang X S等人在2012年提出的一种模拟自然界中花粉授粉过程的群优化算法,由于该算法不需要知道待优化函数的具体形式、易实现、参数少、易调节等特点,引起了很多学者的研究兴趣,并广泛应用于自然科学研究领域。然而该算法和粒子群算法[2]、蚁群算法[3]、遗传算法[4]等类似,都存在早熟收敛,容易陷入局部最优,收敛精度低,迭代次数多等问题。文献[5]提出一种基于引力搜索机制的花朵授粉算法,采用花朵个体间的万有引力和算法本身的莱维飞行共同实现个体位置的更新,使花朵受莱维飞行和万有引力的双重影响；文献[6]通过定义种群多样性及差异性指标,定性分析了花朵授粉算法在多模函数优化中的寻优缺点,利用Nelder-Mead单纯形搜索技术对花朵局部授粉进行重构,提出一种新的花朵授粉寻优架构；Wang R等人[7]提出了一种逐维度计算的FPA算法,通过逐维度更新算子,保留各算子各维度的最优信息；王玉鑫等人[8]将差分进化和变异策略与花朵授粉算法结合,提高种群多样性,从而提高算法的寻优能力。肖辉辉等人[9]将模拟退火算法与花朵授粉算法相结合,提高了算法的全局寻优和跳出局部最优的能力。

以上文献在一定程度上提高了FPA算法的寻优能力,但大多是通过与其他智能算法进行混合的方式以提升FPA算法的性能[10～13],但这样增加了算法的复杂性,破坏了FPA算法简单易实现的特点。

本文在不增加算法复杂度的前提下,针对FPA算法速度和精度不足的问题,将均匀初始化、正态分布缩放因子、扰动进化和边界变异引入花朵授粉算法中,提出利用共轭梯度法改进的花朵授粉算法,并通过7种标准测试函数仿真实验测试HFPA算法的性能 。

1 花朵授粉算法

花朵授粉算法是一种模拟自然界开花植物授粉过程的群智能优化算法。自然界的授粉过程非常复杂,很难通过算法完全真实地模拟花粉授粉的各个细节,且实用价值不高。为了使该算法更为高效,FPA对花朵授粉过程进行简化。在FPA中,假设每朵花为优化问题的一个解,并且每朵花都是通过转换概率p进行异花授粉操作,或以概率 1-p进行自花授粉操作繁衍后代。异花授粉通过一些昆虫或鸟类进行,此类授粉的范围较大,在优化理论中可以视为全局搜索；自花授粉主要是在自然作用下两朵花之间进行小范围授粉,此类授粉的范围较小,在优化理论中可以视为局部搜索。

2 混合改进的花朵授粉算法

2.1 均匀种群初始化

为了使初始种群相对均匀的分布在搜索空间中,同时保持种群的多样性,采用随机均匀种群初始化,如式(1)所示

Xi=bL+(i-1)(bU-bL)/n+rand(1,d)

(1)

式中Xi为种群的第i个个体,bL为优化问题的下界,bU为优化问题的上界,n为种群规模,rand(1,d)为d维的随机数。

2.2 正态分布缩放因子

原始FPA算法采用Levy飞行进行全局搜索,Levy飞行属于随机游走的一种,其特征是小步长的移动很多,但有小概率进行较大步长的移动。理论上Levy飞行能够帮助算法脱离局部最优,但由于转换概率p的限制,花朵授粉算法进行的全局搜索较少,这就大概率导致Levy飞行是以较小步长进行局部运动,反而使算法不易脱离局部最优。

本文算法采用式(2)进行全局搜索

(2)

2.3 变异策略

花朵授粉算法的局部搜索策略为

(3)

在差分进化算法中,常用的变异策略有两种：

DE/rand/1：

(4)

DE/best/1：

(5)

Zheng W等人[14]对差分进化算法进行研究后,提出了一种新的变异策略

(6)

式(6)中,以全局最优解作为基向量,算子本身参与变异,能够更好地平衡变异的随机性和方向性,既能加快收敛速度,又能减慢算法陷入局部最优的速度。

仅采用单一的差分进化仍有可能导致算法陷入局部最优。为了增强算法跳出局部最优的能力,HFPA算法在使用新的变异策略的基础上,算子有较小概率发生变异,使算法跳出局部最优

(7)

最终的局部寻优表达式为

ifrand>pl

else

(8)

2.4 边界变异

在原FPA算法中,对越界算子的处理是将越界的维度的值改为所超越的边界

(9)

为了解决粒子群算法易在边界上陷入局部最优的缺陷,引入了边界变异思想,使得种群多样性得到提升,从而提高了算法的搜索能力。

本文将边界变异思想引入到花朵授粉算法中,对算法中的越界个体依照式(10)进行边界变异：

(10)

式中xi(t,r)为第t次迭代中,第i个算子的第r维。越界个体变异后,可以使个体不在聚集在边界处,提高算法的全局搜索能力。

2.5 算法流程

a.初始化算法的参数,迭代次数N(或迭代停止精度),种群数量n,转换概率p,变异概率pl；b.均匀初始化种群,并计算各个个体的适应度值；c.若p>rand,按照式(2)对更新解,进行全局寻优；d.若p

3 仿真实验与结果分析

本文选择具有代表性的4个函数来验证HFPA算法的有效性和优越性,包括单峰、多峰函数,并将测试结果与FPA算法,粒子群算法(PSO)等算法那进行比较。测试函数选取CEC2013 benchmark[15]测试函数的一部分：

其中,f1,f2,f3为单峰函数,f4～f7为多峰函数,一般用来验证算法逃离局部极值的能力。

3.1 低维下的性能分析

此实验各算法种群数均为20,迭代次数为1500,维度为30。每种算法对每个测试函数运行100次,对比各算法的最优值、平均值就、最差值及寻优成功率。若算法所得最优值与理论最优值相差小于0.001,则认为寻优成功。实验结果如表1所示。其中FPA算法的参数为：p=0.8,n=20;HFPA算法的参数为：p=0.8,n=20,pl=0.1;MFPA的参数为p=0.8,n=20,w=0.618;PSO算法参数为：c1=1.496 2,c2=1.496 2,w=0.729 8。实验结果如表1所示。

从表1可以看出,HFPA算法对各个函数求解的最优值都远小于FPA和PSO算法。较同为FPA改进算法的MFPA算法相比,HFPA解的精度有1～16个数量级的提升,同时解得最优解的成功率和稳定性有很大提高,对7种测试函数的求解均达到了100 %的寻优成功率。图1是其中四种算法在测试函数F1～F4的收敛曲线,其中横坐标代表迭代次数,纵坐标表示测试函数的适应度值。

表1 HFPA在低维的性能分析

图1 测试函数收敛曲线

从图1可以看出,HFPA 算法不易陷入局部最优,且能在算法迭代初期快速收敛,有效提高了迭代速度和精度。

3.2 高维下的性能分析

实验中各算法种群数均为20,迭代次数为1500,维度为100。每种算法对每个测试函数运行100次,对比各算法的实际最优值、平均值就、最差值,如果理论最优值与实际获得的最优值误差小于0.001,认为寻优成功。实验结果如表2所示。

从表2可以得知,HFPA,在300维测试函数下,除F7函数外,都能达到都能够达到70 %以上的收敛率,而FPA算法大部分情况下无法收敛。HFPA 与 FPA、PSO、MFPA 相比,对于函数 ,HFPA 的最优值、平均值、最差值和寻优成功率均好于其他 3 种算法。这说明从寻优精度、收敛速度和鲁棒性上,HFPA相较原算法有较大幅度的提高。

3.3 固定精度下的性能分析

实验中各算法种群数均为20,最大迭代次数为3000,维度为30。每种算法对每个测试函数运行100次,对比各算法达到10-3精度所需的最少迭代次数,平均迭代次数和最大迭代次数。

表2 HFPA在高维的性能分析

表3 HFPA在固定精度下的性能分析

从表3可以看出,对于4个测试函数,HFPA算法均能在1000次迭代内达到目标精度,且无论是最小收敛代数还是平均收敛代数均优于原算法,与其他花朵授粉改进算法相比,迭代次数明显降低。说明HFPA有效提高了FPA算法的收敛速度。

3.4 运行速度分析

针对4种测试函数,维度30,算法种群数均为20,迭代次数1500次。每个算法运行10次,比较FPA算法和HFPA算法的最小运行时间和平均运行时间。实验结果如表4所示。

表4 HFPA运行速度分析 s

从表4可以看出,HFPA的在相同迭代次数下的运行时间在各测试函数下相比FPA算法均有降低。说明HFPA的时间复杂度低于原FPA算法,结合HFPA达到目标精度所需迭代次数较少的特点,使得算法收敛到目标精度所需的时间相比FPA算法大大缩短。

4 结 论

仿真实验结果表明：HFPA算法在收敛速度和精度,运行速度相比原FPA算法有较大提升。HFPA算法在低维下寻优精度较原FPA算法有5～20个数量级的提升,高维下有3～9个数量级的提升,达到相同精度所需的迭代次数大大减少,单次运行时间的比FPA算法有0.4～0.5s的降低,证明本文算法具有一定的可行性。今后准备将花朵授粉算法与其他领域结合,将算法应用于实际当中。