基于族群机制的花朵授粉算法

Vol. 42，No. 4Apr ，2017

1002-064004-0023-06文章编号：（2017）

火力与指挥控制

Fire Control &Command Control 第42卷第4期2017年4月

基于族群机制的花朵授粉算法*

2

肖辉辉1，，段艳明1

（1. 河池学院计算机与信息工程学院，广西宜州546300；2. 江西财经大学信息管理学院，南昌330013）

摘

要：针对花朵授粉算法易陷入局部极值、收敛速度慢等不足，提出一种具有族群机制的花朵授粉算法。该算

法把种群分成多个族群，各族群的最优个体再组成新的种群，进而促进种群间的信息交流，有效地协调种群进化过程中的全局搜索和局部搜索能力，避免个体的早熟收敛，提高算法的全局寻优能力及收敛速度。通过8个CEC2005benchmark 测试函数进行测试比较，仿真结果表明，改进算法的寻优性能明显优于基本的花朵授粉算法、粒子群算法和蝙蝠算法，其收敛精度、收敛速度、鲁棒性均较对比算法有较大提高。

关键词：花朵授粉算法，寻优性能，收敛速度，族群机制，适应度值中图分类号：TP391

文献标识码：A

Improved Flower Pollination Algorithm

Based on Ethnic Group Mechanism

2

XIAO Hui-hui 1，，DUAN Yan-ming 1

（1. School of Computer and Information Engineering ，Hechi University ，Yizhou 546300，China ；

2. School of Information and Technology ，Jiangxi University of Finance and Economics ，Nanchang 330013，China ）

Abstract ：In order to overcome the problems of easily relapsing into local extremum and low speed

of convergence ，a improved flower pollination algorithm based on ethnic group mechanism is presented in the paper. The algorithm divided the population into multiple ethnic groups ，and the optimal individual of those ethnic groups formed a new population ，so as to promote the information communication between the populations ，effectively coordinate the global search and local search in the process of population evolution. It can effectively avoid local optimum ，and enhance the capacity of global optimization ，improve the convergence speed. The comparison and analysis results of the 8CEC2005benchmark functions ，the simulation results show that the proposed algorithm has the advantages of better global searching ability ，faster convergence and more precise convergence than those of the basic flower pollination algorithm ，particle swarm algorithm and bat algorithm.

flower pollination algorithm ，optimization ability ，convergence speed ，ethnic group Key words ：

mechanism ，fitness

0引言

启发式群智能优化算法———花朵授粉算法（Flower

［1］

Pollination Algorithm ，FPA ）。FPA 算法实现简单，易于各种语言编码，需要调节的参数较少，其中转换概率参数p 能较好地平衡局部寻优和全局寻优，

受自然界中显花植物花朵授粉过程的启发，英国剑桥大学学者Yang 于2012年提出一种新型元

收稿日期：2016-02-25

修回日期：2016-03-16

国家自然科学基金（61173146）；广西自然科学基金（2013GXNSFBA019022）；校级青年科研基金（XJ2015QN003）；*基金项目：

江西省研究生创新基金（YC2015-B054）；河池学院计算机网络与软件新技术重点实验室基金资助项目（院科研（2013）3号）

作者简介：肖辉辉（1977-），男，江西永新人，副教授，博士生。研究方向：智能计算、情感计算。

·23·

同时，该算法中所采用的莱维飞行机制提高了算法的寻优效果。FPA 算法正用于不少领域：Yang 于2013年用其来解决多目标优化问题［2］，并取得了较好的结果；El-henawy I 等人于2014年用其解决大整数规划问题［3］；Marwa Sharawi 等人于2014年用其优化无线传感器网络生命周期问题［4］；R. Prathi-ba 等人于2014年用其优化电力调度问题［5］。但因其提出时间短，目前国内外对该算法的研究还处于初级阶段，算法理论尚未成熟，研究成果也较少，因此，对FPA 的研究迫切而有价值。

然而，FPA 算法与粒子群等群智能算法类似，也存在易陷入局部最优且进化后期收敛速度慢等不足，尤其对于多局部极值、高维的较复杂优化问题。针对FPA 算法的不足，国内外不少学者对其进行改进：Wang 等人［6］考虑到维数对算法的收敛速度和收敛精度的影响，提出对个体进行逐维改进和引入局部领域搜索策略思想来对算法进行改进；K. Lenin 等人［7］利用混沌策略改进和声算法增强其种群的多样性，再把和声算法的最优解作为花朵授粉算法的初始解。上述这些改进在一定程度上避免了局部极值，提高了算法的寻优能力，仍未使算法完全避免陷入局部极值，其收敛精度、稳定性、收敛速度等方面仍有待改进。

针对FPA 算法的局限性，本文提出一种具有族群机制的花朵授粉算法（Ethnic Group Flower Polli-nation Algorithm ，EGFPA ）。在EGFPA 算法中，引入了族群机制，把种群分成多个族群（子种群），对每个族群分两层进行寻优，第1层中按FPA 算法求解得到各族群的最优个体，各族群的最优个体组成第2层的种群，再对其进行FPA 寻优，最后得到优化问题的全局最优值。族群机制使种群间进行信息交流，增强种群的多样性，从而使算法很大程度上避免陷入局部最优，提高收敛速度。通过8个CEC2005benchmark 测试函数的仿真实验结果，验证了改进算法的有效性和优越性，EGFPA 算法能够在一定程度上有效地避免早熟收敛，提高收敛速度，其寻优精度、寻优速度、鲁棒性均明显优于基本的花朵授粉算法。

1基于族群机制的花朵授粉算法（EGFPA ）

标准花朵授粉算法分成全局授粉和局部授粉

两部分，两者之间的转换由转换概率P 沂［0，1］控制。FPA 算法中，需假设每颗显花植物仅仅只开一朵花，且每朵花仅仅产生一个花粉配子，一朵花或·24·

一个配子对应于优化问题中的一个解，模拟自然界中显花植物花朵传粉的过程，文献［1］描述了标准的花朵授粉算法的实现步骤。1.1族群机制

传统的进化群体是随机而无序的，群体间缺乏信息共享，而族群机制是一种针对群体结构的调控机制，通过对族群进化过程的控制，实现对群体结构演变过程的调控［8］。把种群分成族群能从群体中筛选出典型个体，从中发现有用的信息，并利用这些先进信息来调整群体的结构，促进群体间的信息交流、提高算法的收敛速度。因此，族群机制利用族群间的信息交流能提高群体的全局搜索能力，族群内部的繁殖过程则能提高算法的局部搜索能力。因此，族群机制能有效地平衡算法的全局搜索和局部搜索，避免个体的早熟收敛，进而提高算法的寻优能力。族群机制有以下特点［9］：

（1）根据群体进化状态的描述角度来确定族群的分类规则。不同的分类规则生成不同的族群结构，如群智能算法中的适应度值、个体的编码方式等都可以是描述群体的角度。

（2）族群描述了种群个体与种群族群间的映射关系。这种映射关系仅仅是逻辑从属关系，并不是实质上地将个体从群体中孤立出来，个体依然是算法的进化主体，只是分散在族群中。

（3）族群依附于群体，其结构随群体的分类规则而改变。

鉴于以上分析，族群机制的伪代码可表示为：①随机初始n=m×r 个种群，其中m 为族群数，

r 为每个族群的种群个体数；

最多迭代次数N _iter；②for i =1to N _iter③for j =1to m ④对族群按某种算法进行寻优，得到该族群的最优个体；

⑤end

⑥对所有族群的最优个体组成新的种群，按某种算法进行寻优，得到全局最优个体；⑦end

1.2EGFPA 算法的实现步骤

EGFPA 算法分为两层，第1层为族群内部寻优，各族群不进行信息交流，独立按FPA 算法寻优求解该族群最优个体；所有族群的最优个体构成第2层，在这层中各族群的最优个体使得各族群之间进行信息交流，在第2层中求解到全局最优个体。假设种群数为n ，族群（子种群）数为m ，则每个族群有r=n/m 个种群个体（花朵），在族群内部，花朵按

FPA 算法进行进化，每个族群（i i =1，2，…，m ）

中最优花朵（局部最优值）为best pi ，整个种群的最优个体（全局最优值）为best g =min（best pi ），i =1，2，…，m 。

EGFPA 算法的具体实施步骤如下：Step 1初始化EGFPA 算法的参数：种群数n ，族群数m ，转换概率p ，最多迭代数N _iter，维数d ；

Step 2随机初始化m 个族群，每个族群有r =n /m 个种群个体；

Step 3m 个族群第1层迭代寻优：各个族群独立寻优，计算每个族群内个体的适应度值，并求解出每个族群的最优解和最优值；

Step 4若转换概率p >rand，按式（1）对每个族群的解进行更新，并进行越界处理

；

（1）

其中，

分别是第k +1代、第k 代的解，g *是

全局最优解，L 是步长，L 的计算用式

（2）

：（2）

其中，

是标准的伽马函数。

Step 5若转换概率p

群的解进行更新，并进行越界处理

；

（3）

其中，∈ 是［0，1］上服从均匀分布的随机数，X j k 、X l k 是同植物种类的不同花朵的花粉。

Step 6求解Step 4或者Step 5的各族群内部最优的花朵个体，组成第2个层次中的花朵种群，并记录其最优值和最优解；

Step 7对Step 6中得到各族群最优个体（m 个花朵），若转换概率p >rand，按式（1）对解进行更新，并进行越界处理；

Step 8若转换概率p

Step 9计算Step 7或Step 8的适应度值，并更新全局最优值和全局最优解；

Step 10计算Step 9的适应度值，并更新全局最优值及全局最优解；

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

2实验仿真与分析

为了验证本文算法的正确性和有效性，通过对8个包括单峰、多峰、低维、高维的测试函数进行仿真来验证算法的改进效果，并与FPA 、PSO 及BA 算法进行比较。测试函数选用CEC2005benchmark 测试函数中的一部分，测试函数如下［9-11］：

①Sphere 函数

，x i ∈ ［-5.12，5.12］，i =1，2，…，n

该函数是一个单峰函数，函数在x *=（0，0，…，

0）处取得全局min （f （1x

））=0。②Rastrigrin 函数

，

x i 该函∈ 数［是一个-5.12，5.12多峰函］，i =1数，，2函，…数，在n x *=（0，0，…，0）处取得全局min （f （2x

））=0。③Ackley 函数

x i 该∈ 函［-32.768数是一个，32.768多峰函］，数i =1，在，2，x …*=（，0n ，0，…，0）处取得全局最小值f min （x ）=0。

④Griewank 函数

，

x i 该函数∈ ［是一个-600，多600峰函］，i =1数，，2在，…x *，=（n 0，0，…，0）处取得全局最小值f min （x ）=0。

⑤Rosenbrock 函数

，

x i 该函数∈ ［是一个-2.048单，2.048峰函］数，i ，=1在，x 2*，=（…0，，n 0，…，0）处取得全局最小值f min （x ）=0。

⑥Schaffer F6函数

，

x i 该函数的是一个∈ ［-100，100二维多］，i =1峰函，

2数，在x *=（0，0，…，0）处取得全局最小值f min （x ）=-1。

⑦，x i ∈ ［-10，10］，i =1，

2，…，n

该函数是一个多峰函数，在x *=（0，0，…，0）处取得全局min （f （7x

））=0。⑧，x i ∈

［-5，5］，i =1，2，…，n

该函数是一个多峰函数，在x *=（0，0，…，0）处取

·25·

得全局min （f （））=0。8x

本文实验的各种参数设置为：EGFPA 算法参数：转换概率p =0.8，beta=1.5，种群个数n =120，族群个数m =15（2.1和2.2小节）；FPA 算法参数：转换概率p =0.8，beta=1.5，种群个数n =15；PSO 算法参数：

=0.5；BA 算法参数：c 1=c 2=2，w =0.9，v max （最大速度）

alf=0.95，gama=0.05。A =0.25，r =0.5，为了验证本文算法的寻优性能、有效性和正确

性，仿真实验方法为：①固定迭代次数，测试4种算法的寻优性能和收敛速度；②与参考文献算法对比，测试本文算法的鲁棒性和寻优精度；③分析族群个数对EGFPA 算法的影响。

函数维数

算法PSO

f 1

30

BA FPA EGFPA PSO

f 2

30

BA FPA EGFPA PSO

f 3

30

BA FPA EGFPA PSO

f 4

30

BA FPA EGFPA PSO

f 5

30

BA FPA EGFPA PSO

f 6

2

BA FPA EGFPA PSO

f 7

30

BA FPA EGFPA PSO

f 8

30

BA FPA EGFPA

最优值0.00240.00120.01741.6308e-162.986729.85927.74608.8914e-115.568217.75864.61002.2171e-101.3735e-05142.37760.10544.7073e-1526.323221.356426.17767.3569e-06-0.[**************]

-0.9218-0.9981-10.24450.93260.24231.0905e-100.00170.00130.00364.3651e-21

优化均值0.00520.00140.15235.6043e-1410.648374.633611.41051.4056e-037.454819.11417.69274.0385e-092.1944e-05633.52540.54602.5477e-1228.968538.202233.01333.6117e-03-0.9981-0.6123-0.99110.99920.36042.4783e+130.52155.5818e-080.00330.00150.02184.4923e-19

2.1固定迭代次数的性能分析

为了防止算法的偶然性带来的误差，对每个测试函数独立运行20次，计算其最优值、优化均值、最差值和标准方差，结果如表1所示，其中，寻优成功率=（找到最优解的次数）/总迭代次数。在实验中，假定：|实际求解的最优值－理论最优值|

从表1中可以看出，本文提出的EGFPA 算法的寻优性能很大程度上优于基本FPA 算法及BA 、PSO 算法。对于f 1、EGFPA 算f 3、f 4、f 7和f 85个函数，

最差值0.00900.00180.35164.7781e-1120.9027145.270516.60554.9800e-0011.028419.883211.70792.6463e-085.0111e-051.4105e+031.26943.5928e-0930.1366139.469468.53409.5083e-01-0.9903-0.5029-0.9903-0.99030.75354.4764e+141.46687.0196e-070.00630.00170.08542.6252e-18

标准方差0.00181.7472e-040.09311.2015e-124.623825.19452.79081.7268e-021.23600.67381.66316.2009e-097.7464e-06331.31980.31527.9357e-110.993429.40758.86774.4075e-020.00400.13120.00220.00220.11039.9973e+130.25921.5698e-070.00101.4193e-040.02027.4239e-19

寻优成功率/%

000100%00057%000100%100%00100%00043%80%0090%000100%000100%

表14种算法在固定迭代次数下的寻优性能比较

·26·

法的最优值、优化均值、最差值和标准方差均较

FPA 算法好，最多相差19个数量级，且寻优成功率都为100%，而除了函数f 4中的PSO 外，其他3种算法的寻优成功率都为0；对于函数f 2、EGFPA f 5和f 6，算法的最优值、优化均值、最差值和标准方差均较FPA 算法好，最多相差11个数量级，且寻优成功率也都较FPA 、BA 及PSO 算法要高。这表明无论从寻优精度、稳定性还是寻优成功率上看，EGFPA 算法都取得较大幅度的提高，同时也说明EGFPA 算法在搜索过程中在一定程度上更能有效地避免陷入局部极小，更好地进行全局优化。

为了更直观地反映出改进算法的寻优效果，图

1是4种算法对8个测试函数收敛曲线图（为了方便收敛曲线的显示和观察，对部分函数的目标函数值取以10为底的对数），形象展示了EGFPA 算法和FPA 、BA 、PSO 算法的对比适应度值的迭代下降过程和全局最优解的收敛速度。从图1中可以看出，对于8个测试函数，EGFPA 算法较FPA 、BA 、PSO 算法具有更高的寻优精度和更快的收敛速度。这表明，本文提出的EGFPA 算法具有更好的寻优能力，其收敛速度、优化精度明显优于FPA 、BA 和PSO 算法。

图14种算法在函数f 1～f 8上的收敛曲

线

2.2与参考文献算法性能比较

为了进一步验证本算法较好的稳定性和较高的寻优精度，证明本文改进算法的优势，限于篇幅，只选用函数f 1～f 5与参考文献中的CLIWO ［10］、CPSO ［10］、HMDE ［11］、LDWPSO ［11］、ABCMSS ［12］、C0-KH ［13］算法对比，为了文中前后数据的一致性，本节中的EGF-PA 数据来自2.1节，其结果如下页表2所示。由表2可知，EGFPA 算法的优化性能（优化均值、标准方差）较参考文献中的其他群智能优化算法有较大的提高。对于函数f 2，EGFPA 的优化均值、标准方差较参考文献［15］中的CO-KH 算法要差点，但好于其他参考文献算法；对于函数f 1、本文算法的优f 3和f 4，化均值、标准方差均远远优于参考文献算法，其中优化均值最多相差12个数量级，标准方差最多相差11个数量级；对于函数f 5，本文算法的优化均值、标准方差略好于参考文献算法。仿真结果表明，本文改进算法具有更强的鲁棒性和更高的收敛精度，也说明本文算法是有效的和可行的。2.3族群个数对EGFPA 算法的影响

族群间的信息传递可以提高种群间的协调能力，提高算法的收敛速度和收敛精度，族群个数在

一定程度上影响着算法的性能，本节通过设置不同

的族群数来验证其对EGFPA 算法的影响程度，其他参数设置同2.1节，鉴于篇幅问题，仅选用函数

结果如下页表3所示。从表3可f 1、f 3和f 4进行测试，以看出，族群个数很大程度上影响着算法的性能，

当族群个数为5和8时，EGFPA 算法的性能提高速度较慢，对函数f 1、最优值和优化均值均仅提f 3和f 4，

高1个数量级；但当其族群个数增加到10和12时，EGFPA 算法的性能提高速度较快，对于单峰函数f 1，最优值提高了3个数量级，对于多峰函数f 4的最优值也提高了2个数量级。因此，随着族群个数的增加，EGFPA 算法的性能也逐步提高。当然，过多的族群个数也影响着算法的运行时间，经过反复测试，当族群个数为15时，算法的性能和运行时间之间的性能比最好。

3结论

花朵授粉算法是一种新型的元启发式群智能算法，但FPA 算法与现有的群智能算法一样，存在早熟收敛、收敛精度低、收敛速度慢等不足。为此，本文把族群机制作用于花朵授粉算法，增强种群的

·27·

表2EGFPA 算法与参考文献算法的优化均值和标准方差比较

函数f 1f 2f 3f 4f 5

性能优化均值标准方差优化均值标准方差优化均值标准方差优化均值标准方差优化均值标准方差

EGFPA 5.6043e-141.2015e-121.4056e-031.7268e-024.0385e-096.2009e-092.5477e-127.9357e-113.6117e-034.4075e-02

CLIWO 6.391e-051.349e-05

--3.280e-023.600e-039.010e-027.340e-024.324e-011.948e-01

CPSO 1.2720e-069.4718e-074.7085e+008.4598e+001.2112e+001.0078e+003.7000e-037.5000e-033.8038e+015.8430e-01

HMDE 0.001-2.001e-033.103e-025.688e-051.065e-051.214e-09

-1.044e-032.560e-01

LDWPSO 0.001-5.723e-022.264e-011.718e-021.431e-016.286e-031.221e-022.5.8e-012.809e+00

ABCMSS 9.69544e-031.15439e-021.86923e+046.62239e+032.00206e+017.30774e-035.43404e+001.51866e+003.19845e+062.32362e+06

C0-KH --0.979e-060.235e-060.312e-040.519e-040.733e-030.168e-030.274e00.108e0

表3族群个数对算法的影响

函数

族群个数

5

f 1

810125

f 3

810125

f 4

81012

最优值2.3903e-074.2785e-085.1507e-107.9397e-134.1206e-078.4541e-083.7163e-087.2297e-092.2469e-091.5017e-103.2061e-112.9338e-13

优化均值1.5024e-062.4764e-077.0972e-081.3793e-105.6814e-065.2946e-061.4622e-071.3097e-082.2601e-081.0593e-098.3431e-105.7888e-11

flower algorithm for optimization ［J ］. International Conference on Computations Science ，2013（18）：861-868.

［3］EL-HENAWY I ，ISMAIL M. An improved chaotic flower

pollination algorithm for solving large integer programming problems ［J ］. International Journal of Digital Content Tech-nology &its Applications ，2014，8（3）：65-71.

［4］MARWA S E. EMARY I A S ，HESHAM El-M. Flower polli-nation optimization algorithm for wireless sensor network life-time global optimization ［J ］. International Journal of Soft Computing and Engineering （IJSCE ），2014，4（3）：54-59. ［5］PRATHIBA R ，BALASINGH M M ，SAKTHIVEL S. Flower

pollination algorithm applied for different economic load dis-patch problems ［J ］. International Journal of Engineering and Technology （IJET ），2014，6（2）：1009-1016.

［6］WANG R ，ZHOU Y Q. Flower pollination algorithm with di-mension by dimension improvement ［J ］. Hindawi ，2014：1-9. ［7］LENIN K ，REDDY B R ，KALAVATHI M S. Shrinkage of ac-tive power loss by hybridization of flower pollination algorithm with chaotic harmony search algorithm ［J ］. Control Theory and Informatics ，2014，4（8）：31-38.

［8］陈皓，崔杜武，崔颖，等. 族群进化算法［J ］. 计算机学报，

2010，21（5）：978-990.

［9］王迎菊. 混合型人工萤火虫群优化算法及应用研究［D ］.

南宁：广西民族大学，2012.

［10］刘挺，王联国. 基于云模型的入侵杂草优化算法［J ］. 计

算机工程，2014，40（12）：156-160.

［11］乔俊飞，傅嗣鹏，韩红桂. 基于混合变异策略的改进差分

进化算法及函数优化［J ］. 控制工程，2013，20（5）：943-947.

［12］王志刚. 一种改进搜索策略的人工蜂群算法［J ］. 计算机

仿真，2014，31（10）：291-295.

［13］王磊，张汉鹏. 基于混沌搜索与精英交叉算子的磷虾觅

食算法［J ］. 计算机工程，2015，41（3）：156-161.

有效性和多样性，进而避免早熟收敛，提高其收敛

速度和收敛精度。通过8个CEC2005benchmark 测试函数的测试，仿真结果表明，改进算法是可行和有效的，其收敛速度和寻优精度得到较大幅度地提高。由于花朵授粉算法的理论和应用研究还处于初始阶段，还有许多问题有待进一步研究，如算法的收敛性分析，参数设置的理论依据，以及与其他智能优化算法的有机融合等。

参考文献：

［1］YANG X S. Flower pollination algorithm for global optimiza-tion ［C ］//In：Unconventional Computation and Natural Com-putation.Berlin ：Springer ，2012：240-249.

［2］YANG X S ，KARAMANOGLU M ，HE X . Multi-objective

·28·