新授粉方式的花授粉算法

段艳明，肖辉辉，林 芳

河池学院 计算机与信息工程学院，广西 河池 546300

1 引言

花授粉算法（Flower Pollination Algorithm，FPA）[1]是由Yang提出的一种源于显花植物花授粉的群体随机优化技术。其主要由全局授粉（全局搜索）和局部授粉（局部搜索）构成，且通过转换概率 p能够较好地解决探索和开发之间的平衡问题。由于花授粉算法概念简单、容易实现及寻优效率较高等优点，从提出之日起，该算法得到众多学者的关注，使其在许多领域获得广泛的应用[2-12]。FPA的寻优性能主要受其授粉方式、进化策略以及参数p值的选择影响。为了提高FPA的全局优化能力，诸多学者对其进行了改进研究，对目前已出版的有关文献梳理可知，当前国内外学者对其改进研究主要可以归纳为以下几个方面。

一方面是对转换概率 p调整策略和参数设置。在FPA算法中，关键参数p对该算法的寻优性能具有较大的影响。为此，Valenzuela等[13]提出一种模糊逻辑花授粉算法，该算法通过模糊推理系统来调整转换概率p的值，实验结果显示该策略能提高FPA算法解的质量，且其性能要优于对比算法。Draa[14]对基本FPA算法中的转换概率参数p的不同取值进行了丰富的定量分析实验，得出当 p=0.2时，在绝大部分测试函数上，传统的FPA算法性能表现最优。Mahdad等[15]提出了一种新的自适应分割授粉算法来解决带安全约束的安全优化功率流问题，并取得较好的效果。在该算法中，作者把迭代过程分为3个阶段，每个阶段转换概率p采用不同的计算公式，使其在进化过程中随机地进行动态调整，采用此策略改善了FPA算法的性能。Łukasik等[16]对花授粉算法进行了详细阐述并对关键参数 p的取值进行了讨论；算法在优化单模态函数时，p的取值对优化结果影响不大；而在求解复杂的多模态函数时，p在[0.5，0.8]之间取值比较好；最后针对FPA与PSO算法的寻优性能进行了对比分析，实验结果表明，PSO算法进化前期的收敛速度要优于FPA算法，后期其收敛速度和个体差异性要差于FPA算法。

基上述可知，当前对参数p的研究，并没有对其取值范围进行探讨，而p的取值范围在运用自适应调整机制时，对算法的性能具有较大的影响。同时，目前虽已有文献对p的取值进行动态调整策略研究，但在其动态调整过程中，没有考虑适应度值的影响。在进化过程中，考虑种群个体的位置信息，有利于提高算法的优化性能。针对上述存在的这些问题，本文将对p的有效取值范围和自适应调整策略进行研究。

另一方面是融入其他机制的改进花授粉算法：在现有的众多群智能算法中，各种算法都存在各自的优缺点。如何把这些算法融合在一起，使其取长补短，构造超大规模的优秀群智能算法，这是当前群智能算法研究的热点。Zhou等[17]把精英反向学习机制引入到FPA算法全局搜索部分，增加种群的多样性，扩展算法的探索领域；在局部搜索引入自适应贪婪策略，改善算法的局部搜索能力；同时采用了动态转换概率方法。算法在收敛速度和计算精度等方面获得了较好的改进。Chakraborty等[18]把差分算法（Differential Evolution，DE）融合到FPA算法中，首先利用DE算法优化初始种群，优化后的种群作为FPA算法的初始解；其次，为了增加算法的稳定性，消除参数p对算法性能的影响，受粒子群的启发，作者通过两个动态权重参数把全局搜索和局部搜索进行整合。改进算法的全局优化能力要优于基本FPA算法。Draa[14]利用反向学习策略对FPA算法进行改进，提高FPA算法的求解精度，实验结果表明该方法改善了FPA算法解的质量。

Kerta等[19]把蚁群算法与FPA算法进行融合，并用于实现电力追踪以解决电力系统超载的监视问题，识别出引起超载的主要原因；在IEEE 14路系统上验证了该算法的有效性和可行性。Xu等[20]针对带莱维飞行策略的FPA算法具有良好的探测能力，但存在较弱的开采能力的问题，把单纯形法融入到FPA算法的局部搜索中以增强FPA算法的局部搜索性能；利用改进算法对混沌系统的参数进行优化，取得较好的结果，与对比算法相比也具有一定的竞争力。

上述改进策略虽然在一定程度上改善了基本FPA算法的优化性能，但这些改进措施在解决高维多峰复杂优化问题时效果仍然不太理想，而且一些改进举措改变了FPA算法的进化思想，一些改进机制较大地增加了算法的时间复杂度。

通过对FPA深入分析发现，FPA的优化性能主要取决于以下3个方面：（1）探测未知领域的能力；（2）防止早熟的能力；（3）快速收敛的能力。同时，由于FPA的全局搜索策略中的Lévy机制和最优个体策略相互制约，削弱了其全局搜索能力；p取固定值，影响了FPA的性能；在局部授粉部分，FPA利用随机变异策略随机产生新的个体，使得其收敛速度慢。

为此，本文提出一种新授粉方式的花授粉算法（Flower Pollination Algorithm with New pollination Methods，NMFPA）。NMFPA采用惯性权重、两组随机个体差异矢量和Lévy机制构建新的全局搜索策略，提高算法的全局探索能力；利用信息共享机制、FPA/rand/1和FPA/best/2融合的局部搜索策略，增强算法的局部开发能力；运用基于高斯变异的最优个体引导策略，提高算法的搜索速度和精度。利用非均匀变异机制增加种群的多样性，有效防止算法早熟，提升算法的全局优化性能。同时，为了增强算法更具灵活性和健壮性等性能，本文对参数p的取值采用一种新的动态调整策略。

通过NMFPA算法对4类经典测试函数的求解，实验结果验证了其具有良好的收敛能力和竞争力。同时，为了进一步检验NMFPA算法求解实际工程问题时，其优化能力是否同样表现良好，利用NMFPA算法对置换流水车间调度问题进行求解，仿真实验结果显示，NMFPA算法的优化能力与对比算法相比，也具有一定的优势。

2 花授粉算法

2.1 FPA存在的不足

花授粉算法作为一种新型群智能优化算法，运用参数 p对算法进化过程中的全局授粉（全局搜索）和局部授粉（局部搜索）之间的相互转换进行了动态控制，较好地解决了勘探与开采之间的平衡问题，且该算法的勘探部分利用了莱维飞行策略，使得其具有较强的探索能力。该算法的核心是由基于Lévy飞行的随机游动（全局授粉）和偏好随机游动（局部授粉）构成，其仿生机理阐述见文献[21]。但由于其搜索方程等方面存在一些不足，使得该算法存在以下缺点：

缺点一：FPA算法在全局授粉部分利用超级花朵（最优个体g*）信息来引导其他花朵的进化方向，加快算法的收敛速度。但在优化具有多个局部最优值的高维复杂多模态问题时，如果最优个体一旦陷入搜索空间中的一些局部最优，则其他个体因最优个体的吸引迅速移向最优个体所在的局部最优位置，的值趋近于0，这使得，造成种群中的个体位置无法得到更新，所有个体都将停滞进化而无法跳出局部最优，算法的全局搜索能力严重削弱，以至于算法无法找到全局最优解。

缺点二：从FPA局部授粉方式可知，新个体的产生是在现有个体的基础上加上两个随机个体的差分向量。在算法进化过程中，随着演化不断深入，种群收敛到一个小范围内，个体之间的差异性越来越小，并且由于和是随机选取的两个个体，如果两个个体的位置非常近，则的值接近于0，这使得种群很难再探索到更好的个体位置，算法的局部搜索能力下降，尤其在求解复杂的高维多模态问题时，这种情况更为突出。另外，FPA算法的局部授粉部分采用了标准差分进化（DE/rand/1）算法的随机变异思想，这导致算法的收敛速度慢。

缺点三：依据FPA算法思想，算法的每次迭代都是根据转换概率 p的值随机地选取全局搜索或者局部搜索，这导致算法丢失了进化方向和远离全局最优解，影响了算法的优化性能。

2.2 参数p对FPA性能影响分析

参数 p是FPA算法的关键参数，为了研究 p的取值范围对FPA性能影响的敏感性，本文取表1中的部分测试函数进行实验，实验结果如图1所示，限于篇幅，仅给出了四个代表性函数（分别来自四类不同的函数）的取值变化图。

表1 本文使用的实验测试函数

图1 p在4个函数上的取值变化图

实验参数设置：p初值0.0，步长0.01，终值1.0，函数维数D=30，种群50，迭代次数1 000；为防止偶然性带来的实验误差，对每个 p值，独立运行30次，并计算其平均值。

从图1中可知：

（1）在优化四类不同的函数时，FPA的性能对 p的取值是敏感的。

（2）p=0.0或1.0时，对于大部分函数而言，其对应的适应度值是最差的。

（3）p在[0.2，0.9]之间取值，FPA的性能较好。

（4）p的取值依赖于不同的优化问题，p取固定的值，不利于提高FPA算法解的质量。

3 新授粉方式的花授粉算法

从花授粉算法的仿生原理可以发现，该算法的收敛能力受到其搜索方程、演化策略和参数设置的影响。本文对其搜索方程和进化机制进行分析，挖掘其存在的不足，为其改进提供理论依据；同时分析参数p的取值是否对算法的性能具有敏感性，为今后求解优化问题时，参数的设置和调整策略提供参考。下面从转换概率p、搜索方程和进化策略三个方面对FPA算法进行改进，提高其优化性能。

3.1 自适应调整的转换概率p

从2.2节可知，参数 p对FPA性能的影响较大，且其取值依赖于求解问题。同时，依据FPA算法的仿生原理可知，若算法中的参数p在优化过程中取固定的值，如果 p取值较大，算法侧重于全局搜索，导致算法收敛速度慢，如果p取值较小，算法容易陷入局部极值，甚至找不到最优值，从而影响算法的全局优化能力。针对该问题，本文对p采用自适应调整策略，其计算公式为：

其中，转换概率 p的取值范围为 p∈[0.2，0.9]，fmin,t和fmax,t分别为第t代种群中最小适应度值和最大适应度值，fi,t为当前个体的适应度值，N_iter为最大迭代次数，t为当前迭代次数，pmin是参数 p的最小值，pmax是参数p的最大值。

从公式（1）可知：

（1）p的取值是动态自适应变化的，且其取值同时考虑了迭代次数和种群个体的适应度值的作用。

（2）在进化初期，p的值较大，算法侧重于全局搜索，扩大算法搜索范围，使种群中的个体更靠近最优解，随着演化的深入，p的值越来越小，使算法倾向局部精细化搜索，有利于算法找到最优值。

3.2 带惯性权重的新全局授粉方式

依据FPA算法的仿生原理，FPA算法在全局授粉时，利用Lévy飞行和最优个体策略对种群中的个体同时施加影响，通过最优个体引导种群中的其他个体进行探索，有利于提高算法的性能，但在进化后期，由于最优个体对其他个体的吸引，使得种群个体具有强烈的趋同性，即减弱了种群个体的差异性。同时，智能算法中通常是利用最优个体策略提高算法的局部搜索能力[22]，采用Lévy飞行机制改善算法的全局搜索能力，而将两种策略融入到一起，势必引起相互抵触，影响算法的全局优化能力。另外，在FPA算法演化后期，由于种群个体的多样性快速丧失而使得FPA易陷入局部最优，影响了算法全局搜索能力。为了解决上述存在的问题，通过融入带惯性权重的思想对FPA算法的全局授粉方式进行改进，具体如下：

其中，rand∈[0，1]是服从均匀分布的随机数；i,i1,i2,i3,i4分别是从当前种群中随机选取的5个不同个体的下标；分别是第t+1代、第t代的解；γ是控制步长的缩放因子；L是对应于花粉传播者的Lévy飞行随机搜索步长；λ=3/2。θ和ω的计算公式分别为公式（4）和公式（5）：

其中，fmax,t为第t代种群中最大适应度值，fi,t为当前个体的适应度值，N_iter为最大迭代次数，t为当前迭代次数。

从NMFPA算法的设计思想可知，算法的演化初期，种群个体的差异性比较大，算法的探测能力较强，无需对个体进行大幅度扰动，而随着进化的不断深入，个体的多样性越来越小，算法的勘探能力被削弱了，影响了算法的优化性能。依据上述公式（5）可知，在算法的进化初期，变量t的值较小，则惯性权重ω的取值较小，对种群的扰动性较弱；当算法进入演化后期，变量t的值越来越大，惯性权重ω的值越来越大，对种群的扰动性较强，有利于增加种群的多样性，以增强算法的全局优化能力。公式（5）中的系数0.01，是经过大量实验获得的经验值。

带惯性权重的新全局授粉方式，在保留Lévy飞行机制的同时利用了两组随机个体的差异矢量，增加了算法的扰动性和算法在多维空间的探索能力。在进化后期，全局授粉部分采用带惯性权重的搜索机制，增加种群个体的多样性，有效避免算法早熟，提高算法优化性能。

3.3 融入精英与信息共享机制的新局部授粉方式

从花授粉算法的局部搜索方程可知：

（1）产生的新个体是在个体的原状态基础上加上一个扰动项，该扰动项是由一个均匀分布的随机数和两个随机个体差分矢量的乘积。虽然随机产生的子代能够较好地保持算法种群个体之间的差异性，使算法能够维持良好的持续优化能力，但也降低了算法的收敛速度。

（2）搜索策略没有充分利用种群信息，使算法在进化过程中种群个体之间的差异性过早地丢失，不能较好地解决“早熟”问题，影响了算法解的质量。

针对上述存在的问题，采用精英策略和信息共享机制对标准FPA算法的局部授粉方式进行改进，新的变异策略如下：

①FPA/rand/1变异策略：

②FPA/best/2变异策略：

其中，i∈(1,2,…,NP（种群数））为当前个体的下标，r1，r2,r3和r4为4个不同的随机个体的下标，xbest,t为第t代种群中最优个体。δ,α,β是均值为0.5、标准偏差为0.1的高斯分布，通过缩放因子δ、α和β对算法的进化速度进行调节。

在新的局部搜索方法中，“FPA/rand/1”变异策略增加了算法种群个体的差异性，提高了算法优化能力，但算法的收敛速度在一定程度上降低了；“FPA/best/2”变异机制通过最优个体引导种群中其他个体的搜索方向，最优个体的有用信息有利于开发最优个体的搜索范围，提高算法的寻优效率，使其收敛速度与开发能力获得提升，但也容易导致算法陷入局部最优。因此，为了使其取长补短，更好提升算法的收敛能力，本文通过公式（4）的非线性递减概率规则来融合这两种变异策略。依据θ的表达式可知，在算法的进化初期，算法偏重于全局搜索；在进化后期，侧重于局部搜索，有利于提高算法的寻优性能。

另外，在FPA算法中个体之间缺乏信息交流，使其容易陷入局部极值，本文把信息共享机制融入到FPA的局部搜索中，即利用公式（8）来进行个体间的学习[23]，从而达到改善解的质量。

其中，f(xi)和 f(xj)分别表示个体xi和xj的目标函数适应度值，s=rand为学习步长，分别是个体i的最新状态和原始状态。

基于上述思想，构建FPA具有信息共享机制的新局部授粉方式：

通过公式（8）实现个体之间的信息交流；

if rand≥θthen

依据公式（7）执行变异，产生新的个体；

else

依据公式（6）执行变异，产生新的个体；

endif

其中θ的计算公式为公式（4）。

3.4 基于变异的改进策略

从FPA的构成可知，FPA是依据参数 p的值随机地选取全局搜索或者局部搜索，这容易导致产生的新个体偏离全局最优解的方向，影响FPA的收敛能力。为了解决该问题，本文在进入下一次迭代之前，利用基于高斯变异的最优个体对种群中的其他个体的进化方向进行引导，以达到提高算法的收敛性能。但是，由于在上述多个位置运用了最优个体策略，增加了FPA算法在收敛后期容易陷入局部极值风险，因此在个体进入下次演化之前，对个体进行非均匀变异，因为非均匀变异是一种能有效避免算法早熟的算子[24]。改进策略定义如下：

（1）基于高斯变异的最优个体改进策略：

其中，xbest为当前种群中最优个体；是第i个个体的新状态；t为当前迭代次数，N_iter为最大迭代次数；k∈(1,0]为递减变量，N(0,1)为高斯变异随机向量。

（2）非均匀变异。变异是种群个体能够持续进化的关键操作，而非均匀变异是对原有个体进行不同幅度的变异而产生新的个体。定义如下：

其中，t是当前迭代次数，Ub和Lb是解的上界和下界，r是[0，1]之间的随机数，b是决定非均匀度的系统参数，N_iter为最大迭代次数，是第i个个体的原始状态，是第i个个体的新状态。

3.5 NMFPA算法流程

根据3.1～3.4节描述的算法改进思想，提出NMFPA算法，算法的流程图如图2所示，具体步骤如下：

步骤1初始化参数，包括花朵种群数n、转换概率p、维数D、最大迭代次数N_iter等参数。

步骤2随机产生种群并计算出其对应的适应度值，同时记录种群中最好的适应度值及其对应的解。

图2 NMFPA流程图

步骤3采用公式（1）产生一个p值，若转换概率p＞rand，进行全局搜索，按公式（2）或（3）对个体位置进行更新，并对新解越界处理，计算种群个体的适应度值，并记录最优值和最优位置。

步骤4若转换概率 p＜rand，先利用个体信息共享策略，即公式（8）更新个体位置，并对新解越界处理，计算花朵个体的适应度值，并记录最优值和最优位置；再采用公式（6）或（7）对个体位置更新，且对新解进行越界处理，并计算花朵个体的适应度值，并记录最优值和最优位置。

步骤5按公式（9）和（10）进行个体位置更新，并对新解越界处理。

步骤6计算步骤5花朵个体的适应度值，并记录最优值和最优位置。

步骤7按公式（11）和（12）进行个体位置更新，并对新解越界处理；

步骤8计算步骤7花朵个体的适应度值，并记录最优值和最优位置。

步骤9判断结束条件，若满足，退出程序并输出最优值及最优解，否则，转步骤步骤3。

3.6 NMFPA时间复杂度分析

对改进算法的有效性和可行性进行衡量，除了算法的优化能力要有较大的提升，另一方面算法的时间复杂度也要低。与标准算法相比，运行的CPU时间应该不能太长。在元启发式算法中，其运行时间主要用在算法找到问题最优解或接近问题最优解所需要的迭代次数。

假设优化问题函数为 f(x)，解空间的维数为D，则根据FPA算法的描述和时间复杂度符号O的运算规则，FPA的时间复杂度为：T(FPA)=O(D+f(D))。

从NMFPA算法思想可知，公式（1）、公式（2）、公式（3）、公式（6）、公式（7）、公式（8）、公式（9）及公式（11）是改进的步骤，根据上文对这几个公式的描述和时间复杂度符号O的运算规则，可以推导出NMFPA算法时间复杂度：T（NMFPA）=T（FPA）+T（公式（1））+T（公式（2））+T（公式（3））+T（公式（6））+T（公式（7））+T（公式（8））+T（公式（9））+T（公式（11））=O(D+f(D))+O(D+f(D))+O(1)+O(1)+O(1)+O(1)+O(1)+O(D+f(D))+O(D+f(D))=O(D+f(D))，与FPA算法的时间复杂度属于同一数量级，说明改进策略对算法的时间复杂度影响较小。

3.7 NMFPA收敛性分析

依据NMFPA算法的思想可知，NMFPA算法属于随机优化算法，则其全局收敛性可利用随机优化算法的收敛准则进行判断。Solis等学者[25]对随机优化算法的收敛性进行了深入研究，提出了判断随机优化算法是否收敛的两条准则，其具体描述如下：

对于求解的最小优化问题 ＜S,f＞，算法A经过迭代k次后获得的解为xk，则下一次迭代后产生的新解为。其中，S是优化问题的可行解空间，f为求解问题对应的目标函数，ξ为算法A进化过程中已获得的解。

在Lebesgue测度空间定义搜索的下确界：

其中，ν(Χ)表示为在集合X上的Lebesgue测度，则其对应的最优解区域定义为：

其中，ε＞0，M 为充分大的正数，若算法A在最优解区域找到了一个点，则称算法A找到了误差为ε的可接受点。

准则H1 如果 f(A(x,ξ))≤f(x),ξ∈S ，则

准则H2如果对∀B∈S,s.t.v(B)＞0，则

其中，uk(B)是算法A第k次解在集合B上的概率测度。

定理1设 f是可测函数，且S为Rn上的可测度子集，是算法A产生的解序列，若算法A满足准则1和准则2，则有，即算法 A全局收敛。

定理2当花朵群体迭代次数趋于无穷，则花朵群体状态序列必将进入最优状态集G。

定理3 NMFPA算法收敛于全局最优解。

证明NMFPA算法在迭代过程中，算法A可描述为：

从上述描述可知NMFPA算法满足准则1。

其次，如果要使定理1中的准则2成立，则要求算法A持续无穷次未搜寻到B中的元素的概率为0。由Rε,M⊂S和定理2可知，NMFPA算法满足准则2。

为此，依据定理1可知，NMFPA算法全局收敛。

4 数值实验及分析

4.1 测试函数

为了验证NMFPA算法的优化能力，本文选取了22个经典测试函数进行仿真实验。在这22个测试函数[26-27]中，包括单峰多维函数(f1～f7)、多峰非旋转的高维函数(f8～f12)、带旋转的多峰高维函数(f13～f17)、偏移的单峰函数或偏移且旋转的多峰函数(f18～f22)，表1列出了本文所使用的测试函数的名称、搜索范围、维数和最优值。

4.2 实验设置

为了验证NMFPA算法在性能上的优势，除了与FPA算法进行对比，还将与目前有代表性的4种改进FPA算法从收敛精度和收敛速度、Friedman和Wilcoxon检验、鲁棒性及CPU运行时间四个方面进行实验对比分析。

（1）混合差分进化花授粉算法（hybrid Differential Evolution-Flower Pollination Algorithm，DE-FPA）[18]。

（2）基于精英反向学习花授粉算法（Elite Oppositionbased Flower Pollination Algorithm，EOFPA）[17]。

（3）改进花授粉算法（Modified Flower Pollination Algorithm，MFPA）[14]。

（4）基于广义反向学习的改进花授粉算法（Modified Generalised Oppsition-based Flower Pollination Algorithm，MGOFPA）[14]。

实验参数设置为：对于 f1～f17函数，所有算法的种群数设置为50，最大迭代次数设置为500；f18～f22测试函数最大迭代次数设置为3 000，算法的种群规模设置为100，所有测试函数的维数D=30。为了降低实验差错，每种算法在每个测试函数上独立运行30次。其余参数，对于EOFPA算法、MGOFPA算法和MFPA算法，取自于对应文献中，DE-FPA算法中的F=0.5、CR=0.9，其他参数来自其文献。FPA算法的转换概率p=0.8。

4.3 算法性能评价指标

本文采用优化均值误差(Mean_error)和标准方差(Std.Dev)评价算法的优化能力，其中优化均值误差计算公式如下：

其中，Mean_error表示优化均值误差，x表示算法得到的解，x*表示的是每个测试函数的理论最优解。从公式（13）可知，Mean_error的值越小，则解的质量越好。

同时，为了公平客观地对参与对比算法的收敛能力进行评价，利用Wilcoxon秩和检验（显著性水平a=0.05）分别对22个函数的实验结果进行统计分析。

4.4 与FPA以及改进FPA算法比较

4.4.1 算法的收敛精度和速度对比分析

实验结果如表2所示，表2中符号†、≈和‡分别表示NMFPA算法的实验结果优于、相当于和劣于对比算法，其中最优结果用加粗凸显。

对表2进行分析发现：NMFPA算法取得20个最优结果，DE-FPA、EOFPA、MFPA、MGOFPA与FPA分别获得2、12、0、1和0个最优结果。NMFPA与DE-FPA、EOFPA、MFPA、MGOFPA和FPA相比，分别多出18、8、20、19和20个最优结果，这证明NMFPA算法的优化性能显著优于对比算法。具体分析如下：

表2 6种算法的优化均值误差和标准差

（1）在单峰多维函数 (f1～f7)中，NMFPA、DE-FPA、EOFPA、MFPA、MGOFPA和FPA各自取得7、1、3、0、1和0个最佳结果，NMFPA获得的最优结果个数是所有算法中最多的，比对比算法中获得最好结果的EOFPA多4个，这说明NMFPA解决单峰多维问题的能力强于其他5种对比算法。

（2）对于多峰非旋转的高维函数(f8～f12)，在6个对比算法中，NMFPA在5个函数上取得的结果全部最优，而EOFPA获得3个，其余4种对比算法没有获得最优结果，NMFPA比EOFPA多2个最好结果，优势不明显，但从图3中函数 f9的收敛曲线可知，NMFPA算法的收敛速度要明显快于EOFPA算法；与其他4种算法相比，NMFPA在所有测试函数上的结果均优，优势非常显著，这表明新算法的收敛能力具有一定的竞争力。

（3）在带旋转的多峰高维函数(f13～f17)中，除了函数 f13和 f17外，NMFPA和EOFPA都能找到理论最优解，但对于函数 f13和 f17，NMFPA的收敛精度显著优于EOFPA，其精度高于EOFPA至少3个数量级；对于其他4种算法，在这5个函数上都没找理论最优解，且收敛精度远远逊色于NMFPA，证明NMFPA算法的优化能力比其他5种算法强。

（4）最后，在最复杂的带偏移的单峰函数或带偏移且旋转的多峰函数(f18～f22)中，对于函数 f21和 f22，NMFPA取得了最好的结果；对于函数 f18，NMFPA、DEFPA和EOFPA都取得了理论最优解，但NMFPA的结果明显好于其余3种算法；对于函数 f19，NMFPA逊色于DE-FPA和EOFPA，但优于其他3种算法；在函数 f20上，NMFPA稍差于EOFPA，但好于其他4种算法。这说明NMFPA更适合求解更复杂的优化问题。

同时借助表2中wilcoxon秩和检验“†”的数学统计结果，从表2的倒数第三行可知，NMFPA在22个测试函数上显著优于DE-FPA、MFPA、MGOFPA和FPA，分别在19、22、21和21个函数上表现更优。与EOFPA相比，NMFPA取得10个最优结果，10个结果两者相当，2个结果稍逊色于EOFPA。

综上分析，NMFPA算法的收敛精度总体上要显著好于对比算法，展示出良好的竞争力。

为了直观地进一步验证NMFPA算法的求精能力和收敛速度是否优于基本FPA和已有改进的FPA算法，限于篇幅，本节通过部分函数的收敛曲线图（如图3所示）和全局最优值方差分析对比图（如图4所示）进行检验。为了更好地观察和显示各种算法在各个函数上的收敛趋势，图3是对每个函数的优化均值误差取了以10为底的对数的收敛曲线图。图4是部分函数在固定迭代次数下，6种算法的全局最优值方差分析对比图。

图3 6种FPA算法在部分函数上的收敛曲线图

图4 6种FPA算法在部分函数上的全局最优值方差分析

从图3可以看出：NMFPA在4类函数上的收敛速度明显快于其他5种算法，特别在函数 f1上，NMFPA在迭代不到200次时，就已找到全局最优解，这表明本文提出的新算法的收敛速度和精度与其他算法相比，具有较好的竞争力。同时，从图4可知，对于多模函数 f13、f17和 f21，NMFPA的收敛精度显著优于其他5种算法，这也验证了表2的实验结果。

4.4.2 算法的Friedman和Wilcoxon检验

为了公平公正地对比各种算法的收敛性能，对多个算法的整体性能从数学统计意义上进行比较分析，采用Friedman检验对实验结果进行分析，算法秩均值越小，性能越好，排名越高。表3是6种算法在22个函数上的Friedman的检验结果，NMFPA算法的秩均值为1.61，排名第一，比FPA算法的秩均值小3.63，这表明本文采用的改进策略能有效地提高FPA算法的性能。

为判别NMFPA算法与对比算法之间是否存在显著性差异，采用Wilcoxon检验进行分析，实验结果如表4所示。从表4可知，NMFPA算法与其他算法的显著性差异较大，这证实运用本文提出的改进策略，能够有效提高FPA算法的全局优化能力。

表3 6种FPA的Friedman检验（D=30）

表4 NMFPA与其他5种FPA的Wilcoxon’s test（D=30）

从上述的实验结果表明，通过多种策略对FPA进行改进而构建的新算法与标准的FPA和现有改进的FPA算法相比，具有较强的竞争力。

4.4.3 算法的鲁棒性对比分析

衡量一个算法的优劣，算法的鲁棒性是其中一个重要的指标，本节对NMFPA算法的鲁棒性进行检验分析。在收敛精度固定下，检验其鲁棒性的优越性。

在表5中，对每个函数都设定了一个优化精度阈值，如果每种算法在迭代次数超过500(f1～f17)或3 000(f18～f22)次还没找到精度阈值，则认定本次寻优不成功，其余参数同上，SR=找到精度阈值的次数/总的运行次数，所有算法在每个函数上独立运行30次，计算其运行成功率(SR)和平均迭代次数(mean_iter)，实验结果如表5所示，其中“NA”表示寻优失利，最佳效果用加粗凸显。

对表5分析可知：

（1）在7个单峰函数(f1～f7)上，NMFPA的优化成功率明显优于DE-FPA、MFPA、MGOFPA和FPA；与EOFPA相比，本文算法在28.57%函数上表现更优，在71.43%函数上两者的优化成功率相当，NMFPA的优势不显著，但从其平均迭代次数，NMFPA在7个函数上均优于EOFPA，进一步验证了本文算法的收敛速度显著快于EOFPA。尤其对于经典的非凸病态单峰测试函数 f5，算法在进化过程中易陷入局部最优，求解难度非常大，本文算法的优化成功率达到76.67%，而其余算法为0，这表明NMFPA算法稳定性最好。

（2）对于多峰函数(f8～f12)，NMFPA在所有函数上均好于MFPA和FPA，与DE-FPA、EOFPA和MGOFPA相比，NMFPA取得最优结果分别多3、1和2个。尤其对于函数 f11而言，只有本文算法的收敛成功率达到100%，而其他算法都没有。这说明本文算法在优化多模态函数时，其鲁棒性表现最突出。

（3）对5个旋转函数(f13～f17)而言，NMFPA算法的鲁棒性优势更显著，其寻优成功率是所有对比算法中最好的，均获得最优结果，这证明本文算法在解决旋转问题时，其鲁棒性更优。

（4）在第4类更复杂的带偏移或带偏移且旋转的函数(f18～f22)中，NMFPA的优化成功率优于MFPA和MGOFPA；与DE-FPA和EOFPA相比，三者的寻优成功率优势相当；与FPA对比，NMFPA的鲁棒性与FPA相当，但其平均迭代次数要好于FPA。这说明NMFPA在解决更复杂的问题时，其稳定性也具有一定的优势。

从表5的最后一行可知，NMFPA的总的平均收敛成功率达到92.58%，是6种算法中最高的，其余5种算法中，寻优成功率最好的是EOFPA，其优化成功率为74.55%，NMFPA比其高出18.03%。FPA算法的总的平均寻优成功率只有18.64%，NMFPA与其相比，提高了73.94%，与其他4种算法相比，也至少高出53.34%，这表明NMFPA算法的鲁棒性最优。

表5 6种算法的寻优成功率及平均迭代次数

图5 6种FPA算法在部分函数上的最优适应度值比较图

为进一步直观地验证NMFPA算法的鲁棒性优于对比算法，由于篇幅所限，图5给出了部分函数的最优适应度值变化对比图，是对比算法在每个函数上独立运行30次下的最优适应度值变化对比图。

从图5可知，在6个测试函数上，除 f21外，NMFPA算法在每个函数上都没出现过波动现象，鲁棒性明显好于对比算法，尤其对于函数 f13和 f17函数，除NMFPA算法外，其他算法波动得非常厉害，这表明其他算法的稳定性要比NMFPA差，这也进一步佐证了表5的结果。对于函数 f21，所有函数都出现了一定程度的波动性，但NMFPA的计算精度是最优的。

综上述，NMFPA算法在4类测试函数上，鲁棒性明显好于对比算法，佐证了本文的改进策略是行之有效的。

4.4.4 算法的CPU运行时间比较分析

本节验证改进策略对FPA运行时间的影响。参与比较的算法同4.2节，其中，所有算法在每个函数上的最大迭代次数都是500，其他实验参数的设置同4.2节。实验环境是：处理器为Intel®Core™ i7-4790 CPU 3.6 GHz，内存为4.00 GB；在MATLAB R2014a进行仿真。表6给出了7种算法在部分函数上的平均CPU运行时间结果，其中表中MT为总的平均时间。

表6给出了6种算法在部分函数上的平均CPU运行时间结果，其中表中MT为总的平均时间。

对表6分析可知：

（1）NMFPA算法总的平均CPU时间要比EOFPA少1.921 9 s，这表明NMFPA算法与该算法相比，简单且高效。

表6 6种算法在函数上的平均CPU运行时间 s

（2）与其他4种算法相比，NMFPA算法总的平均CPU时间要稍多一些，但都在同一数量级上，且增加的时间在可承受的范围之内。NMFPA相对FPA而言，CPU的运行时间在一定程度上增加了一些。这是因为NMFPA在进入下次迭代之前，增加了最优个体引导策略和非均匀变异算子，使得NMFPA算法增加了时间消耗，但两者都属于同一数量级，实验结果验证了上述3.6节的理论分析结果。

4.5 策略分析

为了验证本文采用的各种策略的有效性，把各种主要的改进策略独立出来进行测试，以检验其是否行之有效。IFPA表示对基本FPA的全局搜索策和局部搜索进行改进后的算法；PIFPA表示是在IFPA基础上对参数p进行自适应调整的算法；WPIFPA表示是在PIFPA基础上对全局授粉部分增加了惯性权重的算法；NMFPA表示是在WPIFPA基础增加了变异策略后改进的算法。本节的实验参数设置为：FPA和IFPA的转换概率 p=0.8，PIFPA、WPIFPA和NMFPA中的 p均采用动态调整策略，所有算法的其他参数设置同4.2节。实验结果如表7所示，其中，最优结果用加粗凸显，rank表示每个算法在每个函数上优化性能的排序，sumrank表示每个算法在所有函数上收敛能力的排序和，其值反映该算法的综合性能，值越小，其对应的算法整体性能越优。

表7 5种算法的优化均值误差和标准差（D=30）

从表7可以看出，NMFPA、WPIFIPA、PIFPA、IFPA和FPA在22个函数上，分别获得21、9、3、1和0个最优结果，这表明本文提出的策略相互协作优化可以更好平衡算法的探测和开采，表现出良好的全局优化性能。

各策略的性能表现具体如下：

（1）IFPA与FPA相比，除 f8、f15和 f19～f22外，IFPA在16个函数上取得了更好的结果，这说明IFPA具有更优的全局搜索性能。由sumrank（IFPA）=67＜sumrank（FPA）=81可知，IFPA的综合性能比FPA更优。

（2）PIFPA在22个函数上，与IFPA相比，PIFPA在单模、多模、旋转和偏移或偏移且旋转的函数上分别取得5、4、4和3个最佳效果，这表明对参数 p进行自适应调整改进的PIFPA具有更好的收敛能力，且由sumrank（PIFPA）=49＜sumrank（IFPA）=67可知，PIFPA的整体性能更好。

（3）WPIFPA在单模、多模、旋转函数上明显优于PIFPA。对于偏移或带偏移且旋转的 f18、f20和 f22函数，两者的性能相当；在f19和 f21函数上，WPIFPA要比PIFPA逊色些；同时sumrank（WPIFPA）=37＜sumrank（PIFPA）=49。从上述分析可知，WPIFPA优化能力要优于PIFPA。

（4）对于单峰和偏移或带偏移且旋转函数，NMFPA分别获得6个和3个最优结果，明显好于WPIFPA。在其余2类函数上稍好于WPIPFA；同时，sumrank（NMFPA）=23＜sumrank（WPIFPA）=37。从上述分析可知，NMFPA的寻优性能要表现得更好。

综上述分析可知，NMFPA的寻优性能表现最突出，即本文提出的改进策略能在一定程度上提高算法的优化性能。同时，由表7中的wilcoxon秩和检验“†”的数学统计结果可知，NMFPA与FPA、IFPA、PIFPA和WPIFPA相比，分别在21、20、19和12个函数上表现更优。这表明本文提出的各种策略能相互协调优化可提升算法的全局优化能力。

4.6 NMFPA算法求解PFSP工程优化问题

为了检验NMFPA算法求解经典的置换流水车间调度（Permutation Flow Shop Scheduling Problem，PFSP）问题是否行之有效，本文采用了解决PFSP优化问题时，广泛利用的标准测试案例Car类[28]和Taillard类[29]中的部分测试案例进行实验仿真，并与传统的花授粉算法、惯性权重线性递减的粒子群算法（LWPSO）的实验结果进行对比分析。本节实验的参数设置为：对比算法的迭代次数和种群都设置为50，NMFPA和FPA算法的其他参数设置同4.2节，粒子群算法的惯性权重运用线性减少策略，且Wmax=0.9，Wmin=0.4，学习因子c1=c2=1.496 2。

实验结果如表8所示，其中Car1_11*5表示测试算例Car1在5台加工机器上有11个工件进行加工处理，C*表示所有工件加工完成所需时间的最小值。为了比较算法的优化能力，运用相对误差的最优值（Best Relative Error，BRE）、相对误差的平均值（Average Relative Error，ARE）、相对误差的最坏值（Worst Relative Error，WRE）三个性能指标对算法的优化能力进行度量[30]。

从表8中可知，在Car类测试实例上，NMFPA算法的性能在7个算例上要显著优于对比算法且都能找到理论最优解，只有在Car3_12*5算例上，NMFPA的ARE比LWPSO略差一些，但其他2项指标要好于LWPSO，且所有指标要优于标准的FPA算法；对于Taillard类，所有对比算法虽然都不能找到理论最优解，但NMFPA的整体性能明显好于其他2种比较算法。上述实验分析验证了用NMFPA解决实际工程优化问题时，是可行的且具有一定的优势。进一步说明本文提出的改进策略是可行且有效的。

为了更直观地证明NMFPA算法对PFSP问题的求解能力，图6显示了3种对比算法在部分测试算例上的收敛曲线图，从图6中可以直观清楚地看出，改进算法的寻优精度和收敛速度都要优于其他两种对比算法。这表明NMFPA算法比对比算法更适合解决PFSP问题，也进一步验证了改进策略的有效性。

表8 3种算法的测试算例结果

5 结束语

本文提出了一种新授粉方式的花授粉算法（NMFPA），其改进的策略包括了对基本FPA授粉方式的改进，转换概率 p自适应调整策略及进化策略的改进。对标准FPA授粉方式的改进，扩展探索范围和增加种群的多样性，提高FPA的全局优化能力，局部开发能力和搜索速度；转换概率 p采用动态调整策略，增强FPA的灵活性和健壮性等性能；基于高斯变异的最优个体策略用于引导其他个体的进化方向，提高FPA的收敛速度；利用非均匀变异策略防止FPA早熟，提高FPA的寻优性能。本文采用4类共22个测试函数进行仿真实验，将NMFPA与FPA、4种改进的FPA算法进行对比分析，实验结果表明NMFPA在解的质量，收敛速度和稳定性上表现出更优，是一种富有竞争力的新算法。同时，对本文提出的各种策略在4类不同函数上进行了性能分析，对比结果验证了不同策略均能在一定程度上提升算法的性能，且各种策略能够协调优化，更好地平衡算法的收敛精度和速度，提高了FPA的综合优化性能。最后，利用改进算法对PFSP问题进行求解，实验结果显示，新算法用来解决实际工程优化问题是可行的且也具有一定的优势。