混合变异花授粉算法

李焰华 赵齐辉 肖子雅

Abstract： Flower pollination algorithm is a new type of meta-heuristic optimization algorithm proposed by scholar Yang. It has the defects of being easy to fall into local optimum and low precision. In order to improve its optimization performance， a Hybrid Mutation Flower Pollination Algorithm（HMFPA） is proposed. The pollination algorithm designs chaotic random perturbation and exchange operator for the global pollination and local pollination processes respectively， which effectively balances the local search and global development of the algorithm， and the effectiveness of the algorithm are verified by using multiple standard test functions. The experimental results show that the various optimization indicators of the improved algorithm proposed in this paper are superior to the basic flower pollination algorithm and flower pollination algorithm based on differential evolution strategy.

引言

近些年来，受自然界中生物现象启发而产生的算法有很多，这些生物包括：布谷鸟、鱼、狼、蜜蜂等，这些算法人们称之为群智能算法。群智能算法受欢迎的程度取决于其做现实中优化问题的能力，函数优化便是检验算法的一种有效的工具。

生物启发式算法很多，像蚁群算法[1]、粒子群算法[2]、萤火虫算法[3]，这些算法受启发于自然现象和动物行为。这些算法鲁棒性好，并且是不需要求导数的优化方法，能够有效地解决一些优化问题。但也存在着收敛效率慢、运行时间长、容易陷入局部最优等问题。

花授粉（Flower Pollination Algorithm）[4]作为一种新兴元启发式算法，灵感也是来自于自然界的植物花授粉这一现象。FPA算法由于通用性强、鲁棒性好、编程简易，具有较好的稳定性，已成功应用于许多工程优化问题。Hari Mohan Dubey等人提出了一种改进的FPA算法[5]，并成功应用于短期水火电调度问题。Atul Mishra等人将花授粉应用到离散型问题领域[6]，用于装配序列规划问题求解。Ricardo Soto1成功地将花授粉算法应用于求解制造单元设计问题。FPA算法如此优秀的应用性能已成为人工智能一个新的热点。但是FPA也存在易陷入局部最优、理论基础薄弱、收敛性证明缺乏等问题。

鉴于花授粉算法存在的不足，相关学者也做出了许多改进，主要有混合其他算法和嵌入局部优化算子。Shifali Kalra等提出了一种混合萤火虫算法的花授粉算法[8]，并用于多模态函数优化，但求解的高维函数精度不是特别高；Meera Ramadas等提出了一种基于差分进化策略的花授粉算法[9]，并应用于数据聚类。本文分别针对花授粉算法的全局授粉和局部授粉，用混沌扰动和交流算子进行优化，较好地平衡了局部搜索和全局搜索的关系，并测试常用的标准函数，证明其函数优化性能优于FPA和DEFPA。

1基本花授粉算法

自然界的植物进行授粉大致可以分为有性授粉和无性授粉，有性授粉的过程需要借助载体（昆虫、蝴蝶、鸟类等）进行传播，而这些动物的飞行过程大致服从莱维分布；而无性授粉常常发生在那些雌雄一体的植物上，这些雌雄植物不需要载体进行花粉的传播，其依靠风或者雨雪进行传播。

1.1异花授粉过程

在全局授粉过程中，花粉是由‘媒介（例如昆虫）进行飞行而传播，鉴于此，可以把g*定義为当前种群中最优花粉所处的位置，则其位置xti更新公式如下： xt+1i=xti+Lxti-g*（1）其中：xt+1i代表花粉i在t+1循环时的位置；L代表授粉的强弱程度，其本质是一个服从莱维分布的步长因子，其遵循以下公式分布：L～λΓλsinπλ2π1s1+λ，（s≥s00）（2）其中，Γλ是标准伽马函数，并且分布较为合理。当s（s>0）为较大值时，一般情况下，取λ=3/2。

1.2自花授粉过程

当花粉进行自花授粉时，其位置xti更新公式如下：xt+1i=xti+εxtj-xtk（3）xtj和xtk是不同于花粉i的2个花粉的位置，ε∈U[0，1]。

1.3FPA的描述

基于以上分析，可以将FPA算法描述如下：

（1）初始化：给定种群值、自花授粉和异花授粉的转换概率、以及最大迭代次数和ε的值，随机给定一个最优值位置。

（2）基于概率p选择自花授粉和异花授粉：randp则进行自花授粉，按照公式（3）进行解的更新；f（xnew）

（3）最优值评估：将得出的新解与随机产生的最优花粉进行比较，若f（xnew）f（g*），返回（2）。

（4）判断是否达到最大迭代次数。

（5）输出最优花粉个体和g*。

2混合变异花授粉算法

由于花授粉算法是通过转换概率p来进行自花授粉和异花授粉的切换过程，因此异花授粉的过程是与最优解存在一定的关系。也就是说个体与最优解之间存在着信息交流，但是自花授粉之间是不存在信息交流与共享的。基于此，首先将异花授粉的过程中引入混沌算法进行随机扰动，扩大种群多样性；自花授粉的过程引入交流算子，以增强种群之间的信息交流，有效地避免了算法陷入局部最优。

2.1异花授粉随机扰动策略

混沌算法是一种常用的全局优化算法，引入logistic映射对全局授粉的花粉个体进行随机扰动，用来增强种群的多样性，算法如公式（4）所示：xt+1i=μ*xti*1-xti（4）μ=4为完全混沌状态。一般来说，混沌算法作为优化设计的常用机制，具有遍历性和随机性的特点。混沌算法的引入有效地避免了算法陷入局部最优。

2.2自花授粉的交流算子

针对自花授粉采用交流算子增强种群之间的信息交流，使得花粉粒子不断地靠近最优个体g*。这样做有利于增加局部授粉中种群的信息共享程度，以避免算法陷入局部最优，提高全局搜索最优值的能力，定义如下：xt+1i=k*xti+（1-k）*g*（5）其中，k=rand（0，1）。

2.3HMFPA算法描述

HMFPA算法流程描述如下：

Step 1：定义目标函数f（x），x=（x1，x2，…，xd）TStep 2： 花粉种群初始化，随机产生初始最优解。

Step 3：定义转换概率p。

Step 4：设定迭代终止的条件（一个固定的迭代次数或者需要达到的目标精度）。

Step 5：如果rand

Step 6：如果rand>p，进行自花授粉，并将种群引入交流算子。

Step 7：评价产生的新解，如果优于产生的随机解，则替代掉；否则转到Step 4-Step 6。

Step 8：更新找到的最优解。

3测试与仿真

本文选取p=0.8，max t=2 000，n=20，并与差分进化策略的花授粉算法[10]进行比较，独立运行30次。

3.1测试函数

各测试函数的形式及取值情况如下所述。

（1）minf1x=∑ni=1x2i， 当-5.12≤xi≤5.12，该函数全局最小值是0。

（2）minf2x=∑ni=1x2i-10cos2πxi+10，当-10≤xi≤10，该函数全局最小值是0。

（3）minf3x=-20exp-0.21n∑ni=1x2i-exp1n∑ni=1（cos 2πxi）+20+e，当-32.768≤xi≤32.768，该函数全局最小值是0。

（4） minf4x=14 000∑ni=1x2i-∏ni=1cosxii+1，当-600≤xi≤600，该函数全局最小值是0。

（5）minf5x=∑n-1i=1[100（xi+1-x2i）2+（xi-1）2]，-2.048≤xi≤2.048，该函数全局最小值是0。

（6）minf6x=sin2x21+x22-0.51+0.001（x21+x22）2，-100≤xi≤100，该函数全局最小值是-1。

（7）minf7x=0.01+∑5i=11i+（xi-1）2-1，-10≤xi≤10，该函数全局最小值是0.436。

（8）minf8x=x21+x22-cos18x1-cos18x2，-100≤xi≤100，该函数全局最小值是-2。

（9）minf9x=∑ni=1xi+∏ni=1xi，-10≤xi≤10，该函数全局最小值是0。

（10）minf10x=∑ni=1x2i+12∑ni=1ixi2+12∑ni=1ixi4，-5≤xi≤5，该函数全局最小值是0。

各函数测试结果的对比见表1。

3.2结果分析

表1给出了3种算法的测试结果。

函数f6x、 f7（x）、 f8x均属于低维函数。这类函数局部震荡较为强烈，有很多的局部最优值将全局最优值包围起来，因此很难穿过局部最小值找到全局最小值，因此常用來测试算法的全局最优值开采能力。HMFPA在这3个函数的寻优中均迅速找到了最优值，并且收敛迅速。DEFPA仅仅是在求解f8x时不存在误差，其在f6x、 f7x不能每次都寻找到最优值。

函数f1x、 f9x此类函数属于高维单峰函数。全局最优值较为容易求得，常用来测试算法的收敛速度。f1x的优化HMFPA比DEFPA高了近200个数量级，优化性能的提升非常显著；f9x的优化基本稳定在10-107，远远高于DEFPA的10～30。

函数f2x、 f3x、 f4x、 f10x此类函数为高维多峰函数。属于典型的多模态非线性函数。该函数均存在较多的局部最小点，寻找其全局最小值较为困难。f2x的优化HMFPA和DEFPA均值直接搜索到了其最小值。f3x的优化HMFPA求解要优于EDFPA，其结果大致是10～16。EDFPA并没有直接搜索到f4x的最小值，但是HMFPA在30次测试中结果均为0。f10x的适应度值达到了10～210，寻优的结果较为理想，也优于DEFPA的寻优结果。

f5x即Rosenbrock函数的求解结果不令人满意。该函数是复杂单峰函数，HMFPA难以找到搜索的方向，这是一个需要改进的地方。

综上所述，HMFPA在处理各种复杂函数之间存在一定的优势，不易陷入局部最优。

4结束语

花授粉算法是一种较新颖的群智能算法，已成功运用在大量实际工程问题之中，并且优化函数具有收敛迅速、效率高、能够较快的捕捉极值等优点，但也存在易陷入局部收敛等问题。本文针对花授粉算法的2个关键步骤分别进行优化，兼顾了全局寻优和局部寻优，使得算法无论在处理简单函数还是高维多峰函数都存在一定的优势。仿真结果表明算法的寻优性得到提升、稳定性得到提高，并且优于差分进化策略的花授粉算法，表明本文提出的算法在函数优化方面存在一定的优势。后續工作可以将花授粉算法应用到求解组合优化问题中，例如：旅行商问题、项目调度问题等。

参考文献

[1] DORIGO M， BIRATTARI M， STUTZLE T. Ant colony optimization[J]. IEEE Computational Intelligence Magazine，2016，1（4）： 28-39.

[2] KENNEDY J. Particle swarm optimization[C]// Encyclopedia of Machine Learning. Berlin： Springer， 2010：760-766.

[3] YANG Xinshe. Firefly algorithms for multimodal optimization[C]// Stochastic algorithms： Foundations and applications. Berlin/ Heidelberg：Springer，2009：169-178.

[4] YANG Xinshe， KARAMANOGLU M， HE X S. Flower pollination algorithm： A novel approach for multiobjective optimization[J]. arXiv preprint arXiv：1408.5332，2014.

[5] DUBEY H M， PANIGRAHI B K， PANDIT M. Improved flower pollination algorithm for short term hydrothermal scheduling[C]// Swarm， Evolutionary， and Memetic Computing（SEMCCO 2014）. Switzerland： Springer， 2015：721-737.

[6] MISHRA A， DEB S. Assembly sequence optimization using a flower pollination algorithm-based approach[EB/OL].[2016-09-14]. Https：//DOI.ORG/10.1007/S10845-016-1261-7.

[7] KALRA S， ARORA S . Firefly algorithm yybridized with flower pollination algorithm for multimodal functions[C]//Proceedings of the International Congress on Information and Communication Technology. Singapore：Springer，2016：207-219.

[8] RAMADAS M， ABRAHAM A， KUMAR S. Using data clustering on ssFPA/DE- a search strategy flower pollination algorithm with differential evolution[C]//Proceedings of the 16th International Conference on Hybrid Intelligent Systems （HIS 2016）. Cham：Springer，2017：539-550.

[9] 肖辉辉，万常选，段艳明. 一种改进的新型元启发式花朵授粉算法[J]. 计算机应用研究，2016，33（1）：126-131.