花朵授粉算法(FPA, flower pollination algorithm)是一种新型的元启发式智能优化算法^[1]，它采用莱维飞行机制模拟植物通过鸟类、蜜蜂等进行异花传粉的过程，并通过控制参数完成植物异花传粉和自花传粉之间的转换。FPA算法实现简单、寻优解构新颖、参数较少，具有较大的研究价值，现已成功应用于多个领域^[2-4]。Yang等^[2]用其解决多目标优化问题，得到满意的结果；Rodrigues^[3]提出一种二进制编码的花朵授粉算法，并用于解决特征提取问题；王生生等^[4]将FPA与K-means相结合，并将新算法成功用于解决混合数据聚类问题。

但是，FPA在实际应用中仍存在易早熟、全局收敛能力不足、搜索精度低等问题。为此，国内外学者对其进行了改进：Bekdaᶊ等^[5]将花朵授粉算法应用于桁架结构设计优化。崔丽群等^[6]采用和声算法的最优解作为FPA的初始解，并通过折射原理丰富算法种群的多样性，提升了算法的寻优精度；肖辉辉等^[7]在花朵授粉算法中融入复合形法的思想，利用该思想将种群中最差的个体通过种群中心进行反射，使其变为较好的解，有效改善了解的质量。Wang等^[8]为消除维数对算法性能的影响，从各个维度对解改进，并引入局部领域搜索策略，提升了基本FPA的寻优速度和搜索精度；肖辉辉等^[9]提出具有入侵杂草策略的花朵授粉算法，利用入侵杂草算法中的繁殖操作动态增加种群的多样性，最后利用改进的竞争生成操作丰富了种群和多样性，能够在一定程度上避免算法陷入局部极值；肖辉辉等^[10]利用量子行为的相干、叠加和并行等特征丰富了花朵个体的形态，扩大算法的搜索广度，有效避免了算法陷入局部最优。这些方法在一定程度上提高了算法的寻优性能，但是在算法稳定性、搜索精度和收敛速度等方面仍有待改进。

为提高FPA算法的全局寻优能力，引入小生境技术，并结合混沌搜索策略对算法进行改进：首先，小生境技术使各子种群互相排斥，追逐各自搜索范围内的极值点，动态形成独立的搜索空间，避免协同中的种群过度汇聚，从而确保了种群的多样性；其次，采用混沌搜索策略对算法的局部寻优能力进行优化，利用混沌的无序性和遍历性等特点提升算法的搜索精度。实验表明，应用小生境混沌搜索策略的花朵授粉算法在全局收敛能力和寻优精度上都有所改善，证明了文中改进措施的有效性。

1 花朵授粉算法

自然界中，显花植物的授粉方式可分为自花授粉和异花授粉。异花授粉一般借助传播者(鸟、蜜蜂)等完成，这些携带着植物花粉的传播者能够飞行很远，因此，异花授粉能够克服花朵之间距离的限制，FPA算法将这种授粉方式称为全局寻优。自花授粉是模拟植物自交的过程，FPA算法将这种授粉方式称为局部寻优。自花授粉和异花授粉之间的转换通过转换概率p调节。为简化问题，FPA算法假设每株植物仅开一朵花，每朵花只产生一个花粉配子，对应一个解。根据显花植物传粉过程，FPA还需假定具有以下规则：

规则1：异花授粉需借助传播者(鸟、蜜蜂)等完成，飞行方式为莱维飞行；

规则2：自花授粉指借助风等非生物条件的授粉方式，称之为局部寻优；

规则3：花的常性即繁衍概率，与涉及的两朵花的相似性成比例；

规则4：转换概率p∈[0，1]，由于风等传播者或其他自然因素的影响，植物自花授粉和异花授粉之间发生的概率存在不确定性，在算法中起重要作用。文献[11]中经过大量的实验发现，p值取0.8时，算法的寻优效果最好。

2 应用小生境混沌搜索策略的花朵授粉算法 2.1 小生境技术

小生境是生物学概念，指物种生存所必要的生存环境。生物进化过程中，总是与自己相同的物种生活中一起，共同繁衍后代，这就是小生境自然现象^[12]。不同小生境种群根据自身所处的环境自主选择不同的进化方向，种群间和内部存在相互竞争，有效保持了物种的多样性^[13]。

文中将小生境技术引入FPA算法，其基本思想是根据某种规则对种群进行初始化分类，划分出若干子种群，各个子种群在相对独立的搜索域对解空间内的局部最优点展开同步搜索，避免过早收敛。该技术的关键是对小生境的划分，文中的方法依据个体适应度来实现：1)定义所有个体的适应度值；2)根据适应度值大小对每个种群的个体进行排序，选择适应度最高的个体A=(a₁, a₂, a₃, …, a_k)为小生境的中心，并计算其他个体与中心的欧式距离，计算公式为

$ \left\| {{x_i} - {x_y}} \right\| = \sqrt {\sum\limits_{k = 1}^w {{{\left( {{x_{ik}} - {x_{jk}}} \right)}^2}} } , $

(1)

式中：k∈W; i=1, 2, …, W－1; j=i+1, …, W。

为减少计算量，提升迭代后期的求解精度，半径R需随着迭代次数逐渐增大，小生境数则应随之减少。文中半径的计算方法为

$ R = \max \left( {{d_{is}}} \right)\left[ {\left( {\frac{{{i_{t,\max }} - {i_t}}}{{{i_{t,\max }}}}} \right){u_n} \times \left( {{u_{\max }} - {u_{\min }}} \right) + {u_{\min }}} \right] - 1, $

(2)

$ \tilde R = \left( {\frac{{{i_{t,\max }} - {i_t}}}{{{i_{t,\max }}}}} \right){u_n} \times \left( {{u_{\max }} - {u_{\min }}} \right) + {u_{\min }}, $

(3)

$ R = \frac{{\max \left( {{d_{is}}} \right)}}{{\tilde R}}, $

(4)

式中：i_t为迭代次数；i_{t, max}为最大迭代次数；u_max、u_min与u_n表示算法的可调参数，用于调节算法迭代中分类的数量；d_is为每个个体距中心的欧式距离；${\tilde R}$为中间变量。

在算法运行过程中，通过小生境的动态聚类，各个子种群在相对独立的空间寻优，避免陷入局部极值，增强了算法的全局性。

2.2 混沌优化策略

混沌是非线性系统中特有的一种周期运动现象，运动行为介于规则和随机之间^[14]。由于混沌运动具有无序性和初值敏感性等特点，作为局部搜索算法时，能够很好地提升算法的搜索效率^[15]。相比于常用的Logistic映射，逻辑自映射函数产生的混沌序列遍历性更优，因此，文中利用其实现混沌优化，数学表达式

$ {y_{\left( {n + 1} \right),d}} = 1 - 2 \times y_{n,d}^2,n = 0,1, \cdots ,N,{y_{n,d}} \in \left( { - 1,1} \right)。$

(5)

只要方程式中的迭代初值不为0，混沌就会发生，混沌映射的定义域为(-1, 1)，且不为0，d表示搜索空间的维数。在搜索过程中的某一时刻，花朵i个体的结果位于D维空间中的位置为x_i。

Step 1:将花朵个体对应的解在空间位置的每一维映射至[－1, 1]上, 为

$ {L_{id}} = \frac{{2\left( {{y_{id}} - {a_{id}}} \right)}}{{\left( {{b_{id}} - {a_{id}}} \right)}} - 1,d = 1,2, \cdots ,D, $

(6)

式中, a_id和b_id分别表示花朵i第d维变量的搜索上界和下界。

Step 2:根据式(5)的载波操作，将混沌变量加载至待搜索的个体，从而得到混沌算子操作后的新个体。

Step 3:将获得的新混沌变量序列按照式(7)变换到原解空间中进行性能评价。

$ {{x'}_{id}} = 0.5 \times \left( {{b_{id}} - {a_{id}}} \right) \times {L_{id}} + 0.5 \times \left( {{b_{id}} - {a_{id}}} \right),d = 1,2, \cdots ,D。$

(7)

Step 4:若搜索到更优的解，将这个更优解的位置代替花朵i解的原先位置；否则，继续下一轮混沌搜索直到预先设定的搜索次数。

为进一步提高搜索效率，避免算法过早陷入局部最优，在算法的初期增大搜索范围；在算法搜索后期的减少搜索范围，以加快收敛速度。采用式(8)动态收缩搜索区域。

$ \begin{array}{l} {x_{\min ,j}} = \max \left\{ {{x_{\min ,j}},{x_{g,j}} - p \times \left( {{x_{\max ,j}} - {x_{\min ,j}}} \right)} \right\},\\ {x_{\max ,j}} = \max \left\{ {{x_{\max ,j}},{x_{g,j}} + p \times \left( {{x_{\max ,j}} - {x_{\min ,j}}} \right)} \right\}, \end{array} $

(8)

式中：[x_{min, j}, x_{max, j}]表示第j维变量的搜索范围；x_{g, j}表示最优花朵个体的第j维；式(9)为收缩因子ρ的计算方式；t为算法当前迭代次数。

$ \rho \left( t \right) = 1 - \frac{1}{{1 - \exp \left( { - 0.04t + 4} \right)}} 。$

(9)

同时为在运算速度和求解精度之间取得平衡，不需要对全部花朵进行混沌操作，选取部分优秀个体进行混沌优化。

2.3 算法流程

具有小生境混沌搜索策略的花朵授粉算法实现过程如下：

步骤1   初始化NCFPA各参数：花朵种群数n，种群规模m，转换概率p，最大迭代次数N_iter，精英群体比例L，混沌搜索迭代次数K，最大搜索次数或搜索精度ε。

步骤2   用小生境技术对种群进行分类，使用式(2)~式(4)选择小生境子种群的半径R，计算所有花朵种群中个体的适应度值，将欧氏距离在R范围内的进行标记，记录每个小生境中的最优花朵及其对应的最优解。

步骤3   若转换概率p>rand，按式(10)更新步骤2中的花朵个体对应的解，并进行越界处理。

$ X_i^{t + 1} = X_i^t + L\left( {{x_{{\rm{best}}}} - X_i^t} \right), $

(10)

式中：X_i^t+1、X_i^t分别是第t+1代、第t代花朵个体对应的解；x_best是全局最优解；L是步长，L的计算公式为

$ L \sim \frac{{\lambda \mathit{\Gamma }\left( \lambda \right)\sin \left( {{\rm{ \mathsf{ π} }}\lambda /2} \right)}}{{\rm{ \mathsf{ π} }}}\frac{1}{{{s^{1 + \lambda }}}},\left( {s > > {s_0} > 0} \right)。$

(11)

其中：λ=1.5，Γ(λ)是标准伽马函数。

步骤4   若转换概率p < rand，按式(12)更新解，并进行越界处理。

$ X_i^{t + 1} = X_i^t + \in \left( {X_j^t - X_k^t} \right), $

(12)

式中：∈是[0, 1]上服从均匀分布的随机数；X_j^t、X_k^t是相同植物上不同花朵的花粉。

步骤5   计算步骤3和步骤4的花朵个体的适应度值，并记录每个小生境种群中的最劣个体和最优个体。

步骤6   对各小生境的花朵种群进行评估:选取前n%适应度高的个体作为精英，采取2.1节混沌优化策略对精英个体进行优化；选取后n%适应度低的最差个体，重新初始化产生新的花朵个体对其替换。

步骤7   若迭代次数到达设定值，则初始化更新最劣的子种群。

步骤8   若算法满足终止条件，则输出最优解，否则转至步骤3。

3 仿真实验与分析

为验证文中提出的应用小生境混沌搜索策略的花朵授粉算法的性能，选取8个标准测试函数进行仿真测试，并与FPA、BA及DE算法进行求解对比。

3.1 标准测试函数

8个测试函数具体为Branin(f₁)、Schaffer F6(f₂)、Sphere(f₃)、Schwefel(f₄)、Rastrigin(f₅)、Griewank(f₆)、Ackley(f₇)、Rosenrock(f₈)。其中函数f₁~f₇均为非线性多峰函数，搜索空间中存在多个局部极值点，能够有效检验算法的全局搜索性能、群体多样性和跳出局部极值的能力；函数f₈是单峰函数，是测试算法全局收敛性能的经典函数。

3.2 算法参数设置

实验参数设置为：基本FPA和NCFPA的转换概率p=0.8。BA算法参数：脉冲音强A=0.25，脉冲率r=0.5，最低频率Q=0，最高频率Q=2。混沌搜索最大迭代次数：K=40，精英群体比例为15%；DE的参数设置：交叉概率CR=0.9，缩放因子F=0.8，变异概率G=0.8。所有算法的最大迭代次数均为N_iter=300，根据求解函数的维数，种群规模分别取m=20、30、40、60，所有算法独立运行30次。

3.3 算法寻优性能仿真效果及分析

表 1为4种算法在不同维度标准测试函数下的测试结果，图 1~图 8分别为相应的寻优效果图。

文中设定当求得的最优值和理论最优值间的相对误差低于1%时，算法找到最优解。结果表明：由于函数f₁、f₂的维度较低，4种对比算法均能找到最优解，但NCFPA的寻优成功率最高、寻优速度更快、稳定性更优，寻优曲线如图 1和图 2所示。对于函数f₃~f₇，由于函数形态均为高维、多峰，搜索空间中存在大量局部极值，BA和DE均未找到最优解，FPA仅在f₃(D=10)、f₄(D=10)2种情况下找到最优解；NCFPA不仅都能找到最优解，并且收敛的速度更快，寻优精度更高，寻优曲线如图 3~图 7所示。由于函数f₈(D=30)只为算法提供少量信息，BA、DE和FPA均陷入局部极值中，并且寻优精度较差。NCFPA不仅能够迅速地找到全局最优解，并且寻优成功率较高，寻优曲线如图 6所示。

仿真结果表明：DE、BA和FPA 3种算法在低维函数中的寻优性能总体近似；在高维复杂空间中，FPA寻优效果尽管略比DE和BA更优，但是3种算法都表现出易陷入局部最优、搜索精度不高和稳定性差等特点；在相同搜索条件下，NCFPA的寻优精度和鲁棒性均远优于DE、BA和基本FPA，表现出较好的全局寻优能力。

3.4 算法时间复杂度分析

文中将NCFPA与FPA算法在相同运行环境下，通过运行时间来观察文中改进算法是否满足时间复杂度较低的要求。试验采用f₅、f₆、f₇和f₈4个函数来测试并分析文中算法的时间复杂度，设置最大迭代次数N_iter=300，种群数m=60。2种算法均独立运行20次，计算在不同维数(10维，30维和100维)下的平均运行时间和最小运行时间，结果如表 2所示。

表 2中，NCFPA比FPA算法的平均运行时间略长一点，但NCFPA算法的平均运行时间和最小运行时间仍较短，可以看出NCFPA算法的时间复杂度较低。NCFPA算法在不同维度环境下的寻优精度都远高于FPA算法，表明改进算法是可行和有效的。

4 结论

将小生境技术和混沌优化策略应用花朵授粉算法中，利用小生境技术掌控花朵群体的全局搜索方向，竞争机制有助于维持种群的多样性，淘汰策略则能够不断更新子种群，两种策略的结合，成功地避免了算法的早熟收敛，提升了全局寻优能力。引入逻辑自映射混沌序列，丰富了花朵个体的性状，选取精英个体进行混沌优化，显著提高了算法的搜索精度，减少了算法迭代次数。仿真实验表明，NCFPA算法能够有效克服传统花朵授粉算法存在的全局收敛能力不足、寻优精度低和易早熟的缺陷。