首页 > 论文范文 > 自然科学论文 > 数学论文 > 拓扑论文 > 利用种群进化的改进粒子群算法的研究

利用种群进化的改进粒子群算法的研究

2020-07-11 366 上传者：管理员

摘要：针对多模态问题中收敛速度慢，粒子种群容易早熟的问题，提出一种利用种群进化的改进粒子群算法。该算法在经典多模态粒子群优化算法SPSO的基础上，通过对初始种群进行均匀化空间拉伸更新，同时，对每个新粒子进行梯度进化，加快了粒子种群收敛速度。为了避免种群早熟，漏掉部分极值点，引入环形拓扑模型提高种群交流能力，同时对速度更新公式做出改进。最后利用6个经典的测试函数对三种经典算法做对比实验，结果表明SRPSO具有加快收敛速度，提高寻优成功率的性能。

关键词：
多模态函数
小生境技术
拓扑
环形拓扑
粒子梯度进化
粒子群算法
群智能
加入收藏

在现实生活中，存在着实际的解决方案的空间，有多个全局最优解或者一个全局最优几个有意义的局部最优解的问题，他们统称为多模态函数优化问题。粒子群优化[1]算法是Kennedy和Eberhard于1995年通过对鸟类觅食行为的观察后提出的群体智能优化算法。自算法被提出后便受到广大学者的关注，因其较快的收敛能力和寻优能力而被广泛使用。然而，传统的智能优化算法是一个单极值算法，每次搜索只有一个极值点可以被找到，所以它不适合解决多模态问题。因此，研究人员为了解决多模态问题，纷纷推出将小生境技术引入粒子群算法中，使PSO能够处理多模态优化问题。例如，经典的基于种群的粒子群算法[2]，将整个粒子群划分为多个子种群并对粒子群进行单独寻优，针对标准的测试函数效果较好。但是SPSO必须依赖小生境参数r，需要拥有足够的先验知识才能解决实际问题，并且SPSO算法在最优解较为分散的情况下容易漏掉部分最优解，算法不稳定。针对需要提前设置小生境参数r，文献[3]提出了自适应小生境参数粒子群算法（ANPSO）。该算法在每一代中都重新自主确定参数r，且每个小生境种群中的粒子通过冯⋅诺依曼网络中表现最好的邻居粒子pbes更新自己的gbest。但ANPSO算法不够稳定，处理一些高维函数表现较差，计算量较大。为了提高多模态粒子群算法的优化能力，采用种群进化的多模态粒子群优化算法，其是基于SPSO和ANPSO提出的。这种算法一方面改变种群初始化方法，引导种群进化方向，提高了收敛速度；另一方面，环形拓扑的方式使得算法生产更加稳定的种群，使得算法更加稳定，增强了算法全局探索和局部搜索的能力。

1、粒子群算法基本理论

标准的粒子群算法会初始化一群随机粒子，设n个粒子形成的是D维种群。其中，第i个粒子的位置可以表示为Xi=(xi1,xi2,…,xiD)T。每一个粒子i的位置对应被测函数的一个适应值，适应值的大小体现了解的优劣。种群中的每个粒子i包含有参数位置Xi，速度Vi。其中，第i个粒子的速度可以用向量Vi=(vi1,vi2,…,viD)T表示。在每一次的迭代中粒子都需要根据两个极值来更新本身位置，分别是个体最佳位置pbesti，以及目前整个种群找到的最好的解——全局最优值gbesti。

粒子群算法的寻优过程是通过种群循环迭代进行的，而每一次迭代所有的粒子都根据式（1），式（2）更新粒子自身的速度和位置，直至达到终止条件后寻优结束。

式中：ω代表惯性权重[4]，对于算法的搜索能力有着较大影响，较大的ω有利全局搜索，较小的ω有利于局部搜索；k表示当前粒子迭代代数；r1和r2是[0,1]上的随机数，能够保持种群的多样性；c1和c2是学习因子（自知和社会学习因子），用来调节粒子向pbest和gbest运动的步长，如果值太小或者太大，会造成粒子远离最优解或者粒子抖动的问题；Xik+1代表粒子在第k+1代时的当前位置；pbestik是粒子i在第k代的个体极值最近位置；gbestik代表整个种群在第k代的全局极值点的位置。

为了提高搜索效率同时避免粒子飞出搜索空间，粒子在每一维上的速度都在[-Vmax,Vmax]中制约。而一般情况下Vmax都不会超过粒子的宽度范围。同理，粒子在每一维上的位置也都被限制在[-Xmax,Xmax]中间，若有粒子离开解空间时便需要通过此范围来重新更新粒子信息。

2、采用种群进化的改进粒子群算法

在SRPSO算法中，首先需要通过欧拉距离来确定若干个子种群划分[5]。采用欧氏距离来测量粒子之间的相对位置关系，然后利用与其距离就整体而言最近的粒子所有对应维度上的pbest数据来替代当前维度粒子的gbest信息。这样可以使得空间中距离相对比较近的粒子自动聚焦生成子种群。在种群当中，种群中心粒子设为xm，代表着种群迁移的核心，其位置的改变引导整个种群寻优效果的优劣。那么种群中心粒子xm是当前代种群中最优解的粒子，有且仅有一个，同时负责向某一极值点逼近。P=(pbest1,pbest2,…,pbestn)是所有当前子种群的个体最佳集合，将P中所有元素按照适应度值的优劣排序，依次按照适应度值好坏定义种群中心粒子，并判断后续元素是否属于前一种群，若没有，便继续定义，直至全部中心粒子都被确定[6]。

尽管这种生成的子种群有着较强的独立性，但经过测试，PSO算法的寻优能力与种群分布有着很大的关系，自动生成的子种群容易重叠、交叉，易陷入早熟或漏掉部分极值点的情况。因此，初始种群的分布合理，中心粒子位置较全局均匀，粒子种群更能趋近于全局极值点和部分极值点，反之漏掉的概率较大。

因此，为了提高种群寻优能力，对初始化子种群中心粒子做均匀化空间处理。在解空间内，全体种群中心粒子以空间中心为参照，分别按照大于或小于中心位置相对应维数增加或减少迁移t个单位。经过测验，t的大小为将1个单位20倍的粒子个数n进行等份时效果最好。

在种群全部迁移成功后对种群进行一次梯度优化，引导子种群确定自身后续寻优方向。具体实现为对每一子种群中心粒子在其相应位置上进行梯度分解，若新粒子适应度大于原粒子适应度值，便取代原粒子，反之，保留原粒子信息。

PSO算法有很多不同的拓扑结构，主要常用的结构有环形结构、星型结构、四群集型和冯·诺依曼结构4种[7]。而不同的拓扑结构改变着种群粒子之间信息交流的方式且能够改变算法整体的收敛速度和收敛精度。故为了提高算法更好、更稳定的性能，利用环形拓扑结构来改变种群更新方式[8]:

式中：ω为惯性权重，上文已经提到，在此处权重随着迭代次数从1.2到0.4线性递减，其效果比设置固定权重具有更好的性能；lbestik表示粒子i在第k代的邻域最佳位置，即取pbestik-1,pbestik,pbestik+1适应度值最高的一个，环形结构PSO的每个粒子通过左右相邻粒子的邻域最优与种群中其他粒子共享最优解的信息；nbestik代表在第k代时与粒子i的距离小于e的已找到最优解的和，e为两个相邻小生境之间的最小距离[9]，此处取0.1;r3同样为[0,1]之间的随机数，若不存在与该粒子距离小于e,c3为0，否则为1。

3、实验分析

3.1测试函数

为了验证SRPSO的算法性能，验证改进策略的效果，将SRPSO与经典的SPSO,ANPSO进行实验对比。本文实验环境为IntelⓇCoreTMi7-3630QMCPU2.4GHz,8GBRAM的PC，操作系统为Windows10.0。同时选取4个一维多模态测试函数和2个二维多模态测试函数[10,11]，且测试函数的极值点个数和分布特性均不相同。测试函数详细信息如表1所示。

表1测试函数

3.2评价方法

针对多模函数优化问题，多选用成功率、平均迭代次数与精度三方面指标来进行算法对比。成功率为多次运算之后，寻出全部极值点的次数与总实验次数的比值。

精度用来评价算法搜索到的极值点与实际极值点的误差，所有通过搜索到的极值点与实际极值点比较，误差越小，精度越高。

平均迭代次数可以通过计算找到全部极值点所需平均迭代次数确定[12]:

式中：N为极值点个数；iteri为找到第i个极值点所需迭代次数。AIN值越小，算法效果越好。

3.3实验参数

对于F1～F4一维测试函数，采用相同的阈值εr，种群大小为n，小生境参数r，对F5,F6则设置不同参数[3]。如表2所示。

表2实验参数

3.4实验结果分析

在关于测试成功率实验中，对所有测试函数均进行50次寻优运算。记录如表3所示。

表3实验结果对比

对于F1～F4，三种算法的成功率均可达到100%，表现出很高的成功率。ANPSO与SRPSO不需要提前设置参数，而SPSO需要小生境参数r。对于极值点分布较多、较复杂的函数，ANPSO的成功率明显下降。但SPSO受制于r的设置，故成功率变化较为明显，如果没有很好的先验知识，除了标准测试函数较难在实际问题中使用。而SRPSO改进了速度更新策略，故其全局搜索能力加强，对极值点分布复杂的函数寻优效果更好。

同理，在测量精度（AR）的实验中，对50次寻优结果做分析比较可以看出，SRPSO的寻优平均精度要远小于SPSO与ANPSO，且相差较为明显。由此可以得到，SRPSO在寻优过程中，局部探索能力高于另外两种算法，精度较高。

在平均迭代次数（AIN）的对比数据中，设定测试精度ε=0.0001，当AR<ε时，停止运算。实验结果表明，初始化种群策略对于加快粒子收敛，全局搜索有着更高的能力，且SRPSO的评价次数小于另外两种算法，具有更快的收敛速度，减少了迭代次数。

4、结论

本文针对MFO问题提出的SRPSO算法在处理维数较低，极值点分布较简单的函数时，成功率与ANPSO和SPSO一样，但迭代次数与精度均高于另两种算法。在处理多维问题时，SRPSO与SPSO,ANPSO一样均出现成功率下降的情况，但精度依然较高，收敛速度依然较快。证明算法在全局探索与局部搜索方面均有较高的能力，避免陷入局部最优情况，对于求解MFO问题有着良好的效果。

参考文献:

[5]刘宇,吕明伟.基于物种的自适应多模态粒子群优化算法[J].山东大学学报(理学版),2011,46(5):91-96.

[6]谢红侠,马晓伟,陈晓晓,等.基于多种群的改进粒子群算法多模态优化[J].计算机应用,2016,36(9):2516-2520.

[9]吕明伟.基于相似度模型的多模态粒子群优化算法研究[D].大连:大连理工大学,2013:20-28.

王栋浩,靳其兵,牛亚旭.采用种群进化的粒子群多模态函数优化[J].现代电子技术,2020,43(13):106-109.

基金:国家自然科学基金资助项目(61673004);国家自然科学基金资助项目(62173132);中央高校基本业务专项基金资助(XK1802-4).