基于多种群的改进粒子群算法多模态优化

谢红侠　马晓伟　陈晓晓　邢强

摘要：

针对多模态函数寻优过程中开发与探索能力难以平衡的问题，提出一种基于多种群的改进粒子群算法（EMSPSO）。该算法在基于种群的粒子群算法（SPSO）的基础上改进了种群生成策略，通过在个体最优值中选择种子，将粒子群分为若干独立进化的种群，增强了算法收敛的稳定性；为了提高粒子的利用率、算法的全局搜索能力和搜索效率，引入冗余粒子重新初始化策略；同时为了防止算法在寻优的过程中遗漏适应度较优的极值点，对速度更新公式进行改进，使算法的开发与探索能力得到了有效的均衡。最后选用6个典型的测试函数进行对比实验，实验结果表明，EMSPSO具有较高的多模态寻优成功率与较优的全局极值搜索性能。

关键词：

多模态函数优化；粒子群算法；小生境技术；多种群；冗余粒子

中图分类号：

TP18

文献标志码：A

Abstract：

It is difficult to balance local development and global exploration in a multimodal function optimization process， therefore， an Enhanced MultiSpeciesbased Particle Swarm Optimization （EMSPSO） was proposed. An improved multispecies evolution strategy was introduced to Speciesbased Particle Swarm Optimization （SPSO）. Several species which evolved independently were established by selecting seed in the individual optimal values to improve the stability of algorithm convergence. A redundant particle reinitialization strategy was introduced to the algorithm in order to improve the utilization of the particles， and enhance global search capability and search efficiency of the algorithm. Meanwhile， in order to prevent missing optimal extreme points in the optimization process， the rate update formula was also improved to effectively balance the local development and global exploration capability of the algorithm. Finally， six typical test functions were selected to test the performance of EMSPSO. The experimental results show that， EMSPSO has high multimodal optimization success rate and optimal performance of global extremum search.

英文关键词Key words：

multimodal function optimization； Particle Swarm Optimization （PSO） algorithm； niche technology； multispecies； redundant particle

0引言

在现实生活中很多实际问题都可以抽象为数值函数寻优问题，有一些问题如神经网络集成、组合投资等，不仅要在解空间中找出全局最优解，还要尽可能多地找出有意义的局部最优解，为问题的解决提供足够的信息，此类问题被称为多模态优化问题[1-2]，抽象出的函数为多模态函数（multimodal function），而解决此类问题的过程便是多模态函数的寻优。

粒子群算法（Particle Swarm Optimization， PSO）[3]是Kennedy与Eberhard观察模仿鸟类迁徙觅食的群体行为，于1995年提出的一种群体智能优化技术。标准的PSO是单极值搜索的算法，一次只能搜索到一个极值点，对多模态问题并不适用。小生境（niche）技术[4]是一种仿生技术，将自然界中种群的概念与群体智能算法相结合，通过一定的方法，将整个种群划分为许多个独立的子种群，每个子种群可以独立地进化。近几年，将小生境技术与群体智能算法相结合，提出了一些适用于多模态優化问题的寻优方法。将小生境技术与遗传算法（Genetic Algorithm， GA）相结合提出了小生境遗传算法（Niche Genetic Algorithm， NGA）[5]与种群保护遗传算法（Species Conserving Genetic Algorithm， SCGA）[6]等多模态优化算法，但这些基于遗传算法的多模态优化方法大多存在计算开销大、收敛速度慢、局部搜索精度低的缺陷[7]。将小生境技术与粒子群相结合，文献[8]提出了基于种群的粒子群算法（Speciesbased PSO， SPSO），将粒子群划分为个数自适应的种群各自独立进化将粒子群划分为数个种群各自独立进化，种群的数目在进化过程中不断变化，但是在极值点分布较分散的情况下有可能会漏掉某些较优的解；并且SPSO在每一代的粒子中生成种群种子，这使得粒子在收敛过程中抖动，导致算法稳定性降低。文献[9]提出了一种基于k均值聚类算法的粒子群算法（kmeansbased PSO， kPSO），使用贝叶斯信息规则和标准k均值聚类算法自动识别聚类数

目；但是该算法需要预先设置参数c与集群之间的步数，降低了该算法的实用价值。文献[10]提出了多分组粒子群算法（MultiGrouped PSO， MGPSO），为搜索到的每一个极值分配一个随进化代数增加不断减小的区域来避免最优解重叠；但是如果在种群没有足够收敛之前极值范围变得太小，那么很可能会导致某些种群找不到极值点。

为了提高多模态粒子群算法的搜索性能，在SPSO的基础上提出了一种基于多种群的改进粒子群算法（Enhanced MultiSpeciesbased Particle Swarm Optimization， EMSPSO）。该算法一方面改进了种群生成策略，通过在个体最优值中选择种群种子，减少了粒子在搜索过程中的抖动，使得算法更加稳定；另一方面引入了冗余粒子重新初始化策略，提高了粒子的利用率，增强了算法的全局搜索能力；此外对速度更新公式进行了改进，使算法在收敛速度与全局搜索能力之间取得平衡。

在1维测试函数中，F1、F3为等峰函数，各有5个适应度为1.0的极大值，F1的极大值是均匀分布的，而F3的极大值不是均匀分布；F2为变峰函数，有5个适应度不同的极大值，最大适应度为1.0。在2维测试函数中，F4具有4个适应度为200的极大值，在解空间中分布较均匀。F5在解空间中含有若干极小值，在[0， 0]处存在全局最小值0，其余极小值在最小值周围对称分布，任意两个相邻极值之间距离相等，测试中只关心前13个极小值。F6是比较困难的多模态测试函数，在解空间中同样存在若干极小值，这里只关心其中8个全局最小值与8个全局次小值。两个全局最小值与两个全局次小值为一组，整个解空间中存在4组极值，每组内的极值间距只有0.98，而两组间的距离远大于0.98，极值的不均匀分布与数量众多的局部极值点给算法的搜索带来很大挑战。

4.2实验与结果分析

实验选用精度、成功率与收敛速度三个评价标准对算法的性能进行对比。对某一极值点的寻优精度用可使用找到的极值点pi与实际的极值点opti适应度差值的绝对值来表示，其计算公式如式（9）。

acci=f（pi）-f（opti）（9）

在实验中规定单峰误差ε=0.001，当某一极值点的acci≤ε，才认为此极值点被搜索到。式（10）定义了算法的平均误差（Average ErrorS， AES）[15]，N为适应度函数极值点的个数。AES体现了算法的全局平均精度，在一定的迭代次数下，平均误差越小，算法精度越高。

AES=1N∑Ni=1acci=1N∑Ni=1f（pi）-f（opti）（10）

成功率指的是在进行多次实验后，能成功找到所有期望极值点的实验次数与实验总的次数的比值，是评价多模态寻优算法搜索性能的重要指标。

收敛速度通过计算搜索到所有期望的极值点所需要的平均评价次数与运行时间来确定。在一次运行中，搜索到一定精度的解所需要的评价次数与运行时间减少，收敛速度越高。

SCGA的交叉概率Pc=0.6，变异概率Pm=0.05[6]；SPSO采用收缩因子PSO，收缩因子χ=0.7298，c1=c2=2.05[8]；EMSPSO使用与SPSO等价的参数，ω=χ，c1=c2=1.4961，c3采用双曲正切函数tanh加速。

c3=c3min+（c3max-c3min） 1-tanh（k-0.2Ngmax）2（11）

其中：c3min=0，c3max=0.15，Ngmax为最大迭代次数，k为当前迭代次数。种群距离σS、种群规模n和Ngmax是与测试函数相关的参数，参考文献[1，8]中参数的设置，其具体取值见表2。

在对比算法成功率的实验中，每一个测试函数都经过三种算法50次寻优，记录成功率如表3的成功率。SCGA局部搜索能力较弱，容易出现个别极值点搜索精度较低的情况，所以对每一个测试函数的搜索成功率都没有达到100%。SPSO的局部搜索能力比SCGA要强，但是全局搜索能力较弱，对于一维函数与简单的二维函数F4，能保持100%的成功率；但对于极值点较多分布较复杂的F5、F6，成功率就会严重下降。而EMSPSO由于改进了速度更新公式，增加了冗余粒子初始化策略，提高了算法的搜索能力，对复杂函数的寻优成功率要高于SPSO。

在算法精度的对比实验中，对每个测试函数都进行50次寻优，每次寻优都运行到此测试函数对应的最大迭代次数Ngmax，对50次实验的AES取平均值得到最终结果。由表3平均误差AES可以看出，对每个测试函数，EMSPSO的平均误差AES远小于SCGA与SPSO。这说明，在相同迭代次数下，EMSPSO解的精度远高于其余两种算法，EMSPSO具有更强的局部搜索能力与较快的收敛速度。

在收敛速度的对比實验中，同样对每个测试函数进行50次寻优。规定平均误差的阈值εg = 1E-4，在每次寻优时，当AES<εg时便停止迭代，记录此时的评价次数与运行时间，最后计算50次实验的平均值记录于表3。实验结果表明，虽然增加了冗余粒子初始化策略，在一次迭代中的评价次数可能比其他两种算法更多，但EMSPSO的评价次数与运行时间在大部分情况下要少于SCGA与SPSO。这是由于EMSPSO具有更快的收敛速度，能在较少的迭代次数下搜索

到平均误差小于εg的解。

在图2中，图（a）显示了一维函数F2的AES收敛曲线，图（b）显示了二维函数F5的AES收敛曲线。可以看出，无论是一维函数还是二维函数，EMSPSO的收敛速度要高于SCGA与SPSO。尤其是在进化后期，EMSPSO的搜索精度会快速提高，说明算法具有较好的局部搜索能力；而且，EMSPSO的收敛曲线几乎没有抖动，而SPSO有很大波动，这表明EMSPSO具有更好的稳定性。

5结语

為了提高多模态粒子群优化算法的搜索性能，平衡算法的开发与探索能力，提出了一种基于多种群的改进粒子群算法。该算法在SPSO的基础上改进了种群生成策略，提高了算法收敛的稳定性。并在迭代寻优的过程中引入了冗余粒子重新初始化策略，提高了粒子的利用率和算法的搜索效率。同时改进了速度更新公式，有效地避免遗漏适应度较优的极值点，使算法的开发与探索能力得到均衡。文章对EMSPSO算法的计算复杂度进行分析，并将其与SCGA和SPSO进行了对比实验。理论分析与实验结果表明，EMSPSO具有更好的多模态寻优性能，对于解决多模态函数优化问题具有收敛速度快、搜索精度高、稳定性好的优点。

参考文献：

[1]

吕明伟.基于相似度模型的多模态粒子群优化算法研究[D].大连：大连理工大学，2013：10-13.（LYU M W. Research on multimodal particle swarm optimization algorithm based on similarity model [D]. Dalian： Dalian University of Technology， 2013， 10-13.）

[2]

刘宇，吕明伟，李维佳，等.基于物种的自适应多模态粒子群优化算法[J].山东大学学报（理学版），2011，46（5）：91-96.（LIU Y， LYU M W， LI W J， et al. Adaptively speciesbased multimodal particle swarm optimization [J]. Journal of Shandong University （Natural Science）， 2011， 46（5）： 91-96.）

[3]

KENNEDY J， EBERHART R. Particle swarm optimization [C]// Proceedings of the 1995 IEEE International Conference on Neural Networks. Piscataway， NJ： IEEE， 1995， 4： 1942-1948.

[4]

HORN J. The nature of niching： genetic algorithm and the evolution of optimal， cooperative population [D]. UrbanaChampaign： University of Illinois at UrbanaChampaign， 1997： 17-21.

[5]

WEI L， ZHAO M. A niche hybrid genetic algorithm for global optimization of continuous multimodal functions [J]. Applied Mathematics and Computation， 2005， 160（3）： 649-661.

[6]

LI J P， BALAZS M E， PARKS G T， et al. A species conserving genetic algorithm for multimodal function optimization [J]. Evolutionary Computation， 2002， 10（3）： 207-234.

[7]

陈娟，徐立鸿.动态小生境遗传算法在多模函数优化中的应用[J].同济大学学报（自然科学版），2006，34（5）：684-688.（CHEN J， XU L H. A dynamic niche genetic algorithm for multimodal function optimization [J]. Journal of Tongji University （Natural Science）， 2006， 34（5）： 684-688.）

[8]

LI X. Adaptively choosing neighbourhood bests using species in a particle swarm optimizer for multimodal function optimization [M]// DEB K. Genetic and Evolutionary Computation—GECCO 2004， LNCS 3102. Berlin： Springer， 2004：105-116.

[9]

PASSARO A， STARITA A. Particle swarm optimization for multimodal function： a clustering approach [J]. Journal of Artificial Evolution and Application， 2008， 2008（2）：Article No. 8.

[10]

SEO J H， IM C H， HEO C G， et al. Multimodal function optimization based on particle swarm optimization [J]. IEEE Transactions on Magnetics， 2006， 42（4）： 1095-1098.

[11]

CLERC M， KENNEDY J. The particle swarmexplosion， stability， and convergence in a multidimensional complex space [J]. IEEE Transactions on Evolutionary Computation， 2002， 6（1）： 58-73.

[12]

GOLDBERG D E， RICHARDSON J. Genetic algorithms with sharing for multimodal function optimization [C]// Genetic algorithms and their applications： Proceedings of the 2nd International Conference on Genetic Algorithms. Hillsdale， NJ： Lawrence Erlbaum Associates， 1987： 41-49.

[13]

IWAMATSU M. Multispecies particle swarm optimizer for multimodal function optimization [J]. IEICE Transactions on Information and Systems， 2006， E89D（3）：1181-1187.

[14]

PARROTT D， LI X. Locating and tracking multiple dynamic optima by a particle swarm model using speciation [J]. IEEE Transactions on Evolutionary Computation， 2006， 10（4）： 440-458.

[15]

吴江，胡捍英，吴瑛.面向应用的快速多峰寻优算法[J].计算机应用研究，2008，25（12）：3617-3620.（WU J， HU H Y， WU Y. Applicationoriented fast optimizer for multipeak searching [J]. Application Research of Computers， 2008， 25（12）： 3617-3620.）