一种惯性权重自适应的粒子群优化算法

2017年第30卷第3期ElectronicSci.＆Tech./Mar.15，2017协议·算法及仿真收稿日期:2016-04-16作者简介:罗华(1992－)，男，硕士研究生。研究方向:群智能等。doi:10.16180/j.cnki.issn1007－7820.2017.03.009一种惯性权重自适应的粒子群优化算法罗华(上海理工大学光电信息与计算机学院，上海200093)摘要针对基本粒子群算法的早熟收敛性，在寻优过程中易陷入局部极值。提出一种自适应惯性权重的粒子群优化算法，该算法利用了粒子聚集度、迭代次数来动态的改变惯性权重，以此来平衡局部寻优能力和全局寻优能力，使达到自适应，并使用典型测试函数Griewank和Sphere进行了仿真测试，以此验证改进策略的效果。实验表明，对于多峰函数，与基本粒子群相比较，改进的粒子群优化算法在收敛速度和收敛精度上均高于基本粒子群算法以及一些常见的改进算法。关键词粒子群优化;自适应;惯性权重;聚集度中图分类号TP301.6文献标识码A文章编号1007－7820(2017)03－030－04AInertiaWeightAdaptiveParticleSwarmOptimizationAlgorithmLUOHua(SchoolofOptical－ElectricalandComputerEngineering，UniversityofShanghaiforScienceandTechnology，Shanghai200093，China)AbstractMainlyforthebasicparticleswarmalgorithmofprematureconvergence，Easytofallintolocalmini-maintheoptimizationprocess．Inthispaper，aparticleswarmoptimizationalgorithmofadaptiveinertiaweight，Thealgorithmusetheparticleconcentration，Thenumberofiterationstodynamicallychanginginertiaweight，Inordertobalancethelocaloptimizationandglobaloptimizationability，Maketoachieveadaptive，AndusethetypicaltestfunctionsGriewankandSpherehascarriedonthesimulationtest，Toverifytheimprovementstrategy．simulationre-sultsshow，Formultimodalfunction，Comparedwiththebasicparticleswarm，Theimprovedparticleswarmoptimiza-tionalgorithminconvergencespeedandhigherthanthebasicparticleswarmalgorithmconvergenceprecisionandsomeofthecommonalgorithm．Keywordsparticleswarmoptimization;adaptive;inertiaweight;degreeofaggregation粒子群算法的思想源于对鸟类觅食运动行为的模拟，对鸟群简化社会模型的研究。1987年，Reynolds根据鸟类群体飞行的特点，提出用于模拟鸟类聚集飞行的行为，Reynolds提出了3个规则来作为鸟群个体的简单行为:(1)避免碰撞。避免和临近的个体相碰撞;(2)速度一致。尽量和临近个体在速度上保持协调一致;(3)向中心聚集。尽量试图向自己所认为的群体中心靠近。1995年，Eberhart和Kennedy受到Biod模型的启发，对模型进行深入研究，提出了粒子群优化算法［1］，粒子群算法是典型的智能优化算法，自从提出以来，易实现和可调参数较少等优点吸引了大批学者进行研究，已经逐渐应用到很多行业当中，但是粒子群算法本身也存在容易陷入局部极值、进化后期的收敛速度慢、精度低、易早熟收敛等缺点，目前主要集中在算法的改进和算法研究上［1－6］，所以出现了诸多改进的粒子群算法，有线性递减惯性权重策略(LDIW)［7］、非线性惯性权重策略(NLIW)［8］、模糊惯性权重策略(FIW)［9］、随机惯性权重策略(RIW)［10］等，不同策略在实现起来都在一定程度上使粒子群收敛速度加快，但还是避免不了陷入局部极值中。本文在非线性惯性权重策略基础下，基于基本粒子群算法引入了惯性权重自适应、聚集距离、迭代次数相结合的概念。并且通过经典测试函数仿真验证，在迭代过程中动态改变惯性权重，使其能够摆脱局部极值的干扰，在加快了算法收敛的速度的同时，跟其他优化算法比起来还保持了精度。1基本粒子群算法和惯性权重的分析Eberhart和Kennedy提出基本的粒子群算法如下v(t+1)v(t)+c1r1(pbestij－xij)+c2r2(gbestij－xij)(1)xij(t+1)=xij(t)+vij(t+1)(2)03ChaoXing罗华，等:一种惯性权重自适应的粒子群优化算法协议·算法及仿真提出的粒子群算法的基础上在速度项中增加了惯性权重系数来平衡全局搜索和局部搜索能力，修改后的新的粒子群算法如［6］v(t+1)=ωv(t)+c1r1(pbestij(t)－xij(t))+c2r2(gbestij－x(t))(3)位置更新公式如下xij(t+1)=xij(t)+vij(t+1)(4)式中，ω是惯性权重，惯性权重是最重要的进化参数，其决定了粒子先前飞行速度对当前飞行速度的影响程度，当惯性权重较大时，整体的全局搜索能力加强，局部搜索能力减弱;当惯性权重较小时，整体的局部搜索能力加强。因此可通过调整惯性权重的值来实现粒子全局搜索和局部搜索，恰当的调整惯性权重可以调高算法性能，提高寻优能力，同时还能减少迭代次数［11］。vij(t+1)代表当前迭代的速度，pbestij(t)和gbestij(t)分别代表个体当前找到的最有位置和整体粒子目前找到的最优位置;c1、c2是非负的学习因子;r1、r2是［0，1］区间的随机数。因此，如何寻找合适的惯性权重值，使之在搜索精度和搜索速度方面起到恰当的协调作用，成为业界学者的一个焦点，主要分为线性策略和非线性策略两种［12］。已有线性调整和非线性惯性权重策略。即随进化过程，线性的减少ω的值。这样可使算法在进化初期探索能力较强，能在较大范围的解空间内搜索，并不断搜索新的区域，然后到后期逐渐收敛到较好的区域并进行更精细地搜索，以加快收敛速度［13］ω=(ω1－ω2)×(T－t)/T+ω2(5)其中，ω1和ω2分别是惯性权重的初始值和终端值;T和t分别是当前进化代数和最大进化代数。Shi等人的研究表明，当ω从0.9线性减小到0.4时粒子群算法可以获得满意的优化结果［14］。为了改善递减策略中存在的缺陷，提出了先增后减的策略［15］ω(t)=1×t/tmax+0.40≤t/tmax≤0.5－1×t/tmax+1.40.5≤t/tmax≤{1(6)经过实验分析，像这样的先增后减的策略，前期有较快的收敛性，后期的局部搜索能力也不错。2本文提出的惯性权重调整策略本文提出的调整策略利用到了已有的平均聚集距离和最大聚集距离［8］Mean=(∑mi=1∑Dd=1(pid－xid)槡2)m(8)Max=maxi=1，2，3，4(∑Di=1(pid－xid)槡2)(9)其中，Mean代表平均聚集距离;Max代表最大聚集距离;m代表粒子群的粒子个数;D代表每个粒子的维数;pid代表粒子群目前搜索到的最优位置;xid代表每个粒子目前搜索到的最优位置。在整个粒子群寻优过程中迭代次数也在影响着最后寻优的结果，所以本文在改进的时候就利用了迭代次数对寻优过程的影响，将迭代的影响与聚集度结合起来，来实现惯性权重的动态调整。由于传统的非线性策略要么只是考虑到迭代对算法的影响，要么就利用迭代次数再给定一个控制因子来动态的调整惯性权重，这样虽然能优化算法，但没有真正的智能化，利用聚集距离来及时的判断与全局最优的距离，如果最大聚集距离Mean过大，说明整个粒子群是分散的，就需要增大ω，增强粒子群的全局搜索能力，相反，若Mean在减小，说明粒子群整体在收敛，这时就要减小ω，增强它的局部搜索能力。在此，提出一个定理C=MeanMan(10)这里的C代表聚集距离的变化过程，假定:(1)迭代开始时Mean＜Max;(2)在规定范围内，如果粒子群趋于收敛，平均距离会逐渐缩小，MeanMax比值减小，若整体趋于发散，C就会趋于1。因为当粒子群达到整体最优的时，并不是所有的粒子都能达到这个点，仍有一小部分粒子偏离了最优点，所以假定粒子群在达到最优状态时，仍有n≥1个粒子偏离最优点。这样就不会出现理想状态下随着粒子的收敛，Max也在变小，最后MeanMax趋于1的情况。最后再利用迭代次数对寻优过程的影响，使惯性权重不断的随着迭代次数和聚集距离的改变而改变。根据上述的定理以及分析，本文给出了如下的改进方法ttmax×k1×C0.5＜C＜10＜t＜tmax2C0.5＜C＜10＜t＜tmax2etmax－ttmax－k2×C0＜C＜0.5t＜tmax2(11)式中，k1、k2分别为1.2和2为控制因子;C为聚集距离变化率;t为当前的迭代次数;tmax为最大迭代次数。当前的迭代次数＜tmax2并且聚集距离变化率偏大时，说明在迭代初期粒子群比较分散，所以就增大ω，使整体偏向于全局搜索，加快搜索的速度，当迭代次数逐渐增大至＞tmax2，且聚集距离变化率C减小到0.5以下时，13ChaoXing协议·算法及仿真罗华，等:一种惯性权重自适应的粒子群优化算法说明粒子群正在逐渐收敛，为了能使粒子能找到更优的值，这时就减小ω的值，使粒子更加偏向于局部搜索。整个优化过程惯性权重都随着迭代次数和聚集距离变化率来改变，迭代过程中粒子比较聚集的时，惯性权重就减小，保证最优粒子对周围邻域进行精确搜索。粒子的聚集程度较低时就增大惯性权重，这样较差的粒子会自适应的加大搜索空间，防止聚集度过分上升。算法过程基本属于在前期根据聚集距离变化率增加惯性权重，迭代后期则逐渐减小惯性权重的先增后减的策略。算法流程如下:步骤1随机初始化每个粒子的位置和速度;步骤2先计算每个粒子的适应值，然后初始化个体极值和全局极值;步骤3根据式(8)，式(9)计算平均聚集距离和最大聚集距离，根据式(10)计算出聚集距离变化率，再根据式(11)计算惯性权重ω;步骤4根据式(3)，式(4)来更新粒子的速度与位置，迭代次数加1;步骤5若未满足循环结束的条件，则继续步骤2，若满足，则退出循环，并输出全局最优值。3实验与分析为了验证改进的可行性，使用了两个最典型的测试函数进行实例计算并且与基本粒子群算法作比较，来证明改进的效果。在实验中，取粒子数m=30，学习因子c1=c2=1.4962，D=50，改进的粒子群算法和基本粒子群算法参数一样，分别迭代500次，测试函数如下。表1实验所用测试函数和相关参数函数名维数解空间求解目标值Griewank50［－500，500］0.01Sphere50［－100，100］0.01(1)Griewank函数f(x)=14000∑ni=1x2i－Πni=1cos(xi槡i)+1(12)Griewank函数仿真结果如下。图1基本粒子群算法寻优过程与基本粒子群相比，改进的粒子群算法收敛速度更快了，在迭代约为10次时便可达到收敛，找到最优解，算法寻优效果大幅加强。图2改进的粒子群算法寻优过程(2)Sphere函数f(xi)=∑ni=1