基于三重动态调整的花授粉算法

洪 露,贺兴时，杨新社

(1.西安工程大学 理学院，陕西 西安 710048；2.密德萨斯大学 科学与技术学院,英国 伦敦 NW4 4BT)

0 引 言

为解决复杂的优化问题以及更为合理和满意的近似解，科研工作者们设计了大量的群智能算法，并在过去的几十年中得到迅速发展，成为当前最活跃的算法研究领域之一。群智能算法主要有布谷鸟算法[1](cuckoo search,CS)、蝙蝠算法[2](bat algorithm,BA)、萤火虫算法[3](firefly algorithm,FA)、蚁群算法[4](ant algorithm,AA)等。为了使算法在解决复杂优化问题时更加高效,诸多学者也提出相应的改进策略[5-7]。

花授粉算法(flower pollination algorithm,FPA)最早由剑桥大学学者杨新社提出。这种算法具有参数少、结构简单、稳定性和执行效率高等特点,目前已经应用到了诸多领域；但该算法也存在收敛速度慢、易陷入局部最优、收敛精度低等缺陷,所以诸多学者也对FPA算法进行了改进[8-11]。文献[12]提出了将克隆技术和花授粉算法融合在一起的混合二进制算法。但是，该算法也存在一定缺陷，如算法中涉及参数缺少一定的理论基础、执行到后期时算法收敛速度明显变慢、算法在执行过程中容易陷入局部最优、整体收敛性的相关理论证明不够充分等不足。针对该算法的这些缺陷，很多学者提出了改进和应用方案。YANG等提出在基本花授粉算法中存在的鹰策略(eagle strategy,ES)，是提升算法优越性的根本原因，完善了算法理论[13]；EL-HENAWY等将混沌理论思想引入基本花授粉算法中，使得花粉配子离散化，提出的基于混沌思想花授粉算法应用，解决了大整数规划问题[14]；肖辉辉等则成功将模拟退火原理思想与花授粉算法相融合，在解决函数优化问题中具有一定优势[15]；肖辉辉等还提出将Powell法和高斯变异机制引进到基本花授粉算法中形成混合算法，并对其控制步长的影响因子进行了测试修改，改变种群多样性的同时提升全局探索性能及局部开发机制[16]；HE等使用数学方法中马尔可夫链理论证明了花授粉算法的收敛性，通过为花粉种群构建适当的转换概率并使用同质性,证明构造的随机序列可以收敛到最优集合[17]；张超提出了分数阶扩散方程参数反演的改进花授粉算法，提升了算法的整体性能[18]。但是，对于花授粉算法收敛速度慢、易陷入局部最优及收敛精度低等问题，上述改进方法的效果是有限的。

针对FPA算法存在的诸多问题，本文提出了三重动态调整花授粉算法(HLFPA)， 增加以下策略：将转换概率动态化；在异花授粉过程中引入新型动态因子ω；在局部搜索更新过程中，引入了新型步长因子μ。随机选取7个基准函数对改进后的FPA算法进行测试，并与基础FPA算法、CS算法、ASCSA算法比较。

1 花授粉算法

花授粉算法是一种模拟自然界花朵授粉过程而设计出来的一种启发式算法。异花授粉对应全局搜索过程，自花授粉对应局部搜索过程，并且通过切换概率P∈(0,1)平衡2种搜索行为的比例。为了使算法过程尽可能简化，不妨假设以下4条理想化原则：

1) 异花授粉可被视作花粉传递者使用Levy飞行进行全局授粉过程；

2) 自花授粉可视作局部授粉过程；

3) 花的恒长性可视作繁殖概率，其与授粉过程中两朵花的相似度成正比；

4) 授粉方式通过切换概率p∈(0,1)，且当随机数rand(·)>p时，执行自花授粉过程， 否则就执行异花授粉过程。

异花授粉及全局搜索过程，更新公式为

(1)

(2)

2 改进后的花授粉算法

2.1 动态概率Pa

为了平衡FPA算法的全局搜索和局部搜索，使算法更加灵活，将固定转换概率0.8更改为随着迭代次数自适应变化的动态转换概率Pα，即

Pa=wmax-(wmax-wmin)α

(3)

α由式(4)计算得到,即

(4)

式中：wmax与wmin分别为w的最大值与最小值;t为当前迭代次数，tmax为最大迭代次数。根据文献[19]，wmax=0.9，wmin=0.2。在迭代初期，Pa的取值较大，所以算法侧重于全局搜索，有效地增强了全局搜索能力，使得种群中的个体更靠近最优解；随着迭代深入，Pa的值越来越小，使算法更倾向局部精细的搜索，有利于算法后期快速找到最优解。

2.2 新型动态因子ω

为了提高FPA算法跳出局部最优的能力，在式(1)给出的算法模型基础上引入新型动态因子ω[20]，调节种群迭代过程中搜索个体对当前母系花粉位置信息的依赖性。新型动态因子ω的计算公式如(5)式所示:

ω=ω1·ϑ

(5)

式中：

(6)

计算得ω1的取值范围为[0,0.367 9]，即

迭代前期动态因子ω值较小，削弱母系花粉位置对算法的影响，让花粉更自由地以Levy飞行在搜索空间内大范围地进行搜索，增加全局搜索的能力。迭代后期，动态因子ω减小，使跳出局部最优的能力得到增强。改进后的异花授粉公式为

(7)

2.3 正弦余弦步长因子μ

花授粉算法局部搜索机制中步长因子ε为(0，1)中的随机数，算法迭代到后期容易导致求解精度低，易陷入局部最优等问题，所以本文提出了正弦余弦步长因子μ

(8)

r1由式(9)计算可得，即

(9)

式中:a=1;r2∈[0,2π];r3为[0,1]之间的随机数。

图1为步长因子随迭代时间t变化图。由图1可知:若迭代初期出现自花授粉的过程，较大的步长因子，使得算法前期具有较好的跳出局部最优的能力;随着迭代次数增加，动态概率Pa逐渐减小，使得算法后期主要进行自花授粉过程；在算法后期，随着迭代次数的增加，正余弦步长因子的精度数量级也不断增加，有效地提高了算法的求解精度。改进后的自花授粉公式为

(10)

图1 步长因子变化图Fig.1 Variation of step factor

2.4 实现步骤

1) 初始化算法中各个参数。初始化花粉种群规模N、最大迭代次数Tmax,根据式(3)定义异花授粉和自花授粉转换概率Pa。

2) 初始化花粉种群。寻找当前最优花粉和其所处地位置gb，并计算出其适应度值f(gb)。

3) 进入主循环过程，随机产生一个随机数rand(·)，如果rand(·)>Pa,则按照式(7)进行异花授粉，更新当前花粉位置; 否则,根据式(10)进行自花授粉，并更新花粉位置。

5) 与最优花粉进行比较，如果f(xn)

6) 若当前花粉不是种群中最后一个花粉，则选择下一个花粉，并返回步骤4)；否则，转至步骤7)。

7) 满足算法的终止条件(达到最大迭代次数)，则进行步骤8);否则进入步骤3)，继续进入下一代搜索。

8) 输出最优的花粉个体xn和全局最优解f(xn)。

3 实验仿真与分析

为了验证算法的有效性与可行性，从Benchmarks测试函数中选取了7个典型函数进行测试，并从4个方面分析其性能。测试函数与算法参数见表1和表2，表1中测试函数最优值均为0。

表1 测试函数Tab.1 Test functions

表2 算法参数Tab.2 Algorithm parameters

3.1 算法收敛曲线

图2～8分别为4种算法在f1(x)～f7(x)函数中的收敛曲线图，各函数维数均为10。

图2 f1(x)函数收敛曲线Fig.2 Convergence curve of function f1(x)

图3 f2(x)函数收敛曲线Fig.3 Convergence curve of function f2(x)

图4 f3(x)函数收敛曲线Fig.4 Convergence curve of function f3(x)

图5 f4(x)函数收敛曲线Fig.5 Convergence curve of function f4(x)

图7 f6(x)函数收敛曲线Fig.7 Convergence curve of function f6(x)

图8 f7(x)函数收敛曲线Fig.8 Convergence curve of function f7(x)

由图2～8可知：HLFPA算法在收敛速度上明显优于CS算法、FPA算法和ASCSA算法，且在50代左右都可以收敛到全局最优，表明HLFPA算法具有较快的收敛速度和较好的收敛精度。f1(x)～f3(x)为多峰函数，存在多个局部极小点，可用于测试算法的跳出局部最优和寻优能力。由图2～4可以看出：HLFPA算法具有较强的寻优能力，有效克服了易陷入局部最优的缺点。f4(x)～f7(x)为单峰函数，用于测试算法的收敛速度。由图5～8可以看出：HLFPA算法在50代左右可以收敛到全局最优。可见，无论单峰还是多峰的高维函数，HLFPA算法都表现出了较好的寻优能力和较快的收敛速度。

3.2 算法求解精度比较

在维数分别为50、100的条件下，用4种算法对f1(x)～f7(x)函数进行仿真实验，结果如表3～9。

表3 f1(x)函数仿真结果Tab.3 Simulation resutls of f1(x)

表4 f2(x)函数仿真结果Tab.4 Simulation resutls of f2(x)

表5 f3(x)函数仿真结果Tab.5 Simulation results of f3(x)

表6 f4(x)函数仿真结果Tab.6 Simulation results of f4(x)

表7 f5(x)函数仿真结果Tab.7 Simulation results of f5(x)

表8 f6(x)函数仿真结果Tab.8 Simulation results of f6(x)

表9 f7(x)函数仿真结果Tab.9 Simulation results of f7(x)

f1(x)为复杂的多峰函数，常常导致算法在求解时陷入局部最优。由表3可见，HLFPA算法在求解精度上和稳定性上远远高于其他3种算法,但是在后期求解时也陷入了局部最优8.88×10-6。f2(x)为典型的非线性多模态函数,且图像跌宕起伏不定。由表4可见，其他3种算法随着维度的增加，寻优能力逐渐减弱，但HLFPA算法均可以收敛到全局最优位置，表现出卓越的寻优能力。

f3(x)为典型的多模态函数，不仅搜索区域大，而且存在许多局部极小点，通常被用来测试智能算法跳出局部最优的能力。由表5可见，HLFPA算法可以收敛到全局最优，表现出了较好的搜索性能和跳出局部最优的能力。f4(x)～f7(x)均为高维单峰函数，常用于评价算法后期的搜索性能和寻优能力。HLFPA算法在维数为50、100的情况下，均可以收敛到全局最优，HLFPA算法的标准差也远远优于其他3种算法(表6～9)，说明HLFPA算法具有更强的稳定性。

4 结 语

HLFPA算法是针对FPA存在的不足进行的优化改进。将固定转换概率改为随迭代减小的动态转换概率，更好地平衡了2种搜索机制的转换；在异花授粉母系花粉位置引入新型变化因子，提升了算法跳出局部最优的能力；在局部搜索更新公式中引入新型正余弦步长因子，提高了算法的收敛精度。实验结果表明，改进后的 FPA算法具有较快的收敛速度、较高的寻优精度，且适用于高维复杂函数求解问题。改进后的花授粉算法对二维函数的优化效果一般，下一步将在花授粉算法的参数设置和应用方面做进一步研究。