肖辉辉，段艳明

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

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

肖辉辉1，2，段艳明1

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

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

花朵授粉算法，寻优性能，收敛速度，族群机制，适应度值

0 引言

受自然界中显花植物花朵授粉过程的启发，英国剑桥大学学者Yang于2012年提出一种新型元启发式群智能优化算法——花朵授粉算法（Flower Pollination Algorithm，FPA）［1］。FPA算法实现简单，易于各种语言编码，需要调节的参数较少，其中转换概率参数p能较好地平衡局部寻优和全局寻优，同时，该算法中所采用的莱维飞行机制提高了算法的寻优效果。FPA算法正用于不少领域:Yang于2013年用其来解决多目标优化问题［2］，并取得了较好的结果；El-henawy I等人于2014年用其解决大整数规划问题［3］；Marwa Sharawi等人于2014年用其优化无线传感器网络生命周期问题［4］；R.Prathiba等人于2014年用其优化电力调度问题［5］。但因其提出时间短，目前国内外对该算法的研究还处于初级阶段，算法理论尚未成熟，研究成果也较少，因此，对FPA的研究迫切而有价值。

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

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

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

标准花朵授粉算法分成全局授粉和局部授粉两部分，两者之间的转换由转换概率P∈［0，1］控制。FPA算法中，需假设每颗显花植物仅仅只开一朵花，且每朵花仅仅产生一个花粉配子，一朵花或一个配子对应于优化问题中的一个解，模拟自然界中显花植物花朵传粉的过程，文献［1］描述了标准的花朵授粉算法的实现步骤。

1.1 族群机制

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

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

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

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

鉴于以上分析，族群机制的伪代码可表示为:

①随机初始n=m×r个种群，其中m为族群数，r为每个族群的种群个体数；最多迭代次数N_iter；

②for i=1 to N_iter

③for j=1 to m

④对族群按某种算法进行寻优，得到该族群的最优个体；

⑤end

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

⑦end

1.2 EGFPA算法的实现步骤

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

EGFPA算法的具体实施步骤如下:

Step 1初始化EGFPA算法的参数:种群数n，族群数m，转换概率p，最多迭代数N_iter，维数d；

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

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

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

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

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

Step 8若转换概率p＜rand，按式（3）对解进行更新，并进行越界处理；

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

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

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

2 实验仿真与分析

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

①Sphere函数

该函数是一个单峰函数，函数在x*=（0，0，…，0）处取得全局min（f1（x））=0。

②Rastrigrin函数

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

③Ackley函数

该函数是一个多峰函数，在x*=（0，0，…，0）处取得全局最小值fmin（x）=0。

④Griewank函数

该函数是一个多峰函数，在x*=（0，0，…，0）处取得全局最小值fmin（x）=0。

⑤Rosenbrock函数

该函数是一个单峰函数，在x*=（0，0，…，0）处取得全局最小值fmin（x）=0。

⑥Schaffer F6函数

该函数的是一个二维多峰函数，在x*=（0，0，…，0）处取得全局最小值fmin（x）=-1。

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

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

本文实验的各种参数设置为: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算法参数: c1=c2=2，w=0.9，vmax（最大速度）=0.5；BA算法参数: A=0.25，r=0.5，alf=0.95，gama=0.05。

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

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

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

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

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

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

图14 种算法在函数f1～f8上的收敛曲线

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

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

2.3 族群个数对EGFPA算法的影响

族群间的信息传递可以提高种群间的协调能力，提高算法的收敛速度和收敛精度，族群个数在一定程度上影响着算法的性能，本节通过设置不同的族群数来验证其对EGFPA算法的影响程度，其他参数设置同2.1节，鉴于篇幅问题，仅选用函数f1、f3和f4进行测试，结果如下页表3所示。从表3可以看出，族群个数很大程度上影响着算法的性能，当族群个数为5和8时，EGFPA算法的性能提高速度较慢，对函数f1、f3和f4，最优值和优化均值均仅提高1个数量级；但当其族群个数增加到10和12时，EGFPA算法的性能提高速度较快，对于单峰函数f1，最优值提高了3个数量级，对于多峰函数f4的最优值也提高了2个数量级。因此，随着族群个数的增加，EGFPA算法的性能也逐步提高。当然，过多的族群个数也影响着算法的运行时间，经过反复测试，当族群个数为15时，算法的性能和运行时间之间的性能比最好。

3 结论

花朵授粉算法是一种新型的元启发式群智能算法，但FPA算法与现有的群智能算法一样，存在早熟收敛、收敛精度低、收敛速度慢等不足。为此，本文把族群机制作用于花朵授粉算法，增强种群的有效性和多样性，进而避免早熟收敛，提高其收敛速度和收敛精度。通过8个CEC2005 benchmark测试函数的测试，仿真结果表明，改进算法是可行和有效的，其收敛速度和寻优精度得到较大幅度地提高。由于花朵授粉算法的理论和应用研究还处于初始阶段，还有许多问题有待进一步研究，如算法的收敛性分析，参数设置的理论依据，以及与其他智能优化算法的有机融合等。

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

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

［1］YANG X S.Flower pollination algorithm for global optimization［C］//In:Unconventional Computation and Natural Computation.Berlin:Springer，2012:240-249.

［2］YANG X S，KARAMANOGLU M，HE X.Multi-objective 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 Technology&its Applications，2014，8（3）:65-71.

［4］MARWA S E.EMARY I A S，HESHAM El-M.Flower pollination optimization algorithm for wireless sensor network lifetime 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 dispatch problems［J］.International Journal of Engineering and Technology（IJET），2014，6（2）:1009-1016.

［6］WANG R，ZHOU Y Q.Flower pollination algorithm with dimension by dimension improvement［J］.Hindawi，2014:1-9.

［7］LENIN K，REDDY B R，KALAVATHI M S.Shrinkage of active 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.

Improved Flower Pollination Algorithm Based on Ethnic Group Mechanism

XIAO Hui-hui1，2，DUAN Yan-ming1
（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）

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 8 CEC2005 benchmark 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 mechanism，fitness

TP391

A

1002-0640（2017）04-0023-06

2016-02-25

2016-03-16

国家自然科学基金（61173146）；广西自然科学基金（2013GXNSFBA019022）；校级青年科研基金（XJ2015QN003）；江西省研究生创新基金（YC2015-B054）；河池学院计算机网络与软件新技术重点实验室基金资助项目（院科研（2013）3号）

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