一种动态调整的改进微粒群算法

一种动态调整的改进微粒群算法【摘要】微粒群算法，是一种新型的进化计算方法，在不同领域有着广泛应用。通过研究基本微粒群算法发现，基本群算法在计算过程中应用测度为零的线性进行搜索过程中，则会较为早的进入早收敛现象，因此提出了改进版的微粒群算法，该算法在运算过程中可将极限位置进行动态化的调整，使得各个微粒的极限位置在其线性运动总形成的动态圆形分布。本文探讨了动态调整中的一种改进微粒群算法，并进行实例仿真，证明了方法的可靠性和有效性。【关键词】动态调整；改进；微粒群算法0.引言微粒群算法是一种以群智能方法为基础的演化计算技术。为提高算法的准确性和效率，许多专家做了大量的研究，并对微粒群算法做了不同的改进[1][2]。但是，在改进算法过程中，仅仅利用微粒位置向量对空间进行搜索，而微粒的速度向量会受到最大速度常数的限制，即收到位置向量的限制，进而影响到质量和速度向量信息的利用效率。本文通过探讨一种动态调整改进微粒群算法，提高计算准确性和计算效率。1.微粒群算法概述微粒群算法，是由美国社会学家JameKennedy和电气工程师RussellEberhart共同提出的一种基于模拟鸟类飞行和鱼群活动的随机优化计算方法[3]。该算法体现了简单、朴素的智能意识：鸟类应用简单的规制指导自身的飞行方向和速度，使得它们在飞行中不会发生碰撞。微粒群算法和其他进化计算法不同，它是把每一个个体作为一个N维度搜索空间中无质量和体积的微粒，并在该空间中按照一定的方向和速度飞行，该飞行速度是根据个体的飞行经验和群体飞行经验进行动态调整的。目前，对于微粒算法的研究主要有：算法参数的调整、结构浇筑、拓扑结构改进、混合算法改进及理论分析和微粒群应用[4]。2.基本微粒群算法的分析基本微粒群算法的描述是：其中，Vj（t）表示时刻微粒j速度向量；Xj表示t时刻微粒j位置向量；Pj表示t时刻微粒j历史最优位置向量，Pg表示t时刻种群历史最优位置向量，r1、r2是两个在0到1之间的随机分布值，w、c1及c2是常数。为了更好的进行分析，对上述式子进行变形：设β1=c1r1,β2=c2r2,A=A1+A2则PQ=A1Pj+A2Pg（3）把（3）带入（1）中可得到：Vj（t+1）=wVj（t）+β[PQ－Xj（t）]（4）由PQ定义可知，min｛Pj，Pg｝≤PQ≤max｛Pj，Pg｝，当Pj和Pg给定后，位于他们所形成的线段和全局可行解区域的各种可能的情况主要有四种（如图1、图2），图1中a到d情形分析：图1中的a和b两种情形是表示算法可能收敛到全局最优解的集合之中，其中集合A表示全局最优解的集合；a图表示全局最优Pg刚好在集合A之中，也就是Pg自身就是一个全局最优解，显然微粒j可能收敛到集合A之中；b图表示全局最优位置Pg和Pj所在位置形成的线段也刚好在集合A之内，微粒j也可能收敛到集合A之中；c图和d图都是全局最优位置Pj和Pg所在位置形成线段与集合A不相交，如此不管微粒j如何变化，只要Pj和Pk保持不变，那么会一直收敛不到集合A中去。图1不同Pj和Pg的分布情况相对图1中的c和d图的情况，给出了相应的解决方法（图2中a和b）。在图2中a情形，让微粒就不再仅仅收敛在Pj和Pg形成的线段上，还收敛在两者形成的某一个区域内。如此，因所形成区域可能和集合A相交，进而增加了微粒j进入全局最优解集A中的概率。对图2中b情形进行相同的分析。图2解决图1中c和d情形的方法3.动态调整改进微粒群算法分析根据r1和r2在0到1之间随机均匀分布，则β1=c1r1在[0，c1]上均匀分布，β2=c2r2在[0，c2]上均匀分布，从而β=β1+β2是[0，c1+c2]上的随机变量，而β可应用K、random表示，以限制β的变化范围，K是一个给定的数值，random是0到1间的随机数值。现在分析Pj和Pg构成的某一个区域，可设Pg=Pg1，Pg2，...Pgk，Pj=Pj1，Pj2...Pjk，其中Pjk和Pgk分别表示Pj和Pk两点在第k的维分量，定义Pj和Pg间的距离是：（5）为了保证搜索范围的测度在0以上，可考虑Z=（Pg1+Pj1/2，Pg2+Pj2/2，...Pgn+Pjn/2）作为圆心，ρ（Pg，Pj）/2作为半径的圆，结果在该圆中随机选择，则其搜索测度是πρ2（Pg，Pj）/4＞0，假设结果是PQ=（PQ1，PQ2，...PQn），那么得到：（6）式（6）中，random，random1及random2是在0到1间的三个随机数值，Pd是一个预设定的阀值。通过分析，可得出改进微粒算法的方程是：Vj（t＋1）＝wVj（t）＋β[PQ－Xj（t）]（7）Xj（t＋1）＝Xj（t）＋Vj（t＋1）（8）其中，β是0到K之间均匀分布的随机数值，PQ是由前面动态调整方案来确定的，可知改进微粒群算法的步骤和基本群粒法算法的步骤是基本一致的。参数选择直接关系到进化方程的运算：由PQk的定义可知：PQk＝β1Pjk/β＋β2Pgk/β＝αPjk＋（1－α）Pgk可把PQk看成Pjk和Pgk的凸组合，由此表明PQk是通过α来决定的，此时可不通过β1、β1及β2来决定PQk，因此算法的随机性是通过变量PQk来表现的，而是把β当作一个既定的数值来看。采用此计算方式，可把w、β看作为进化方程的系数。其中，w看作为速度Vjk（t）的权系数，β则看作为PQk－Xjk（t）的权系数。因Vjk（t）只和微粒j的即时速度存在关系，就是单个微粒的个体信息；PQk－Xjk（t）和群体以往最优位置与微粒j的以往最优位置存在关系，就是微粒间相互的交流信息。进而把w和β的取值看作为个体信息和交流信息的比例。假设参数β为0的话，那么微粒j的速度进化方程和个体信息存在关系，如果全局最优位置恰在其运动的直线上，那么算法可收敛到全局的最优点；要不然的话，算法就会搜索不到全局的最优位置。此时，算法具备一定的全局搜索能力。假设参数w为0的话，那么微粒j的微粒进化方程只和群体间交流信息存在关系，此时算法只在群体的以往最优位置和微粒j的历史最优位置构成区域范围中运行，是当作一个局部搜索的进化算法。所以，选择参数w和是保证算法全局搜索和局部搜索两个方面的平衡化[5]。通常情况下，在算法进行的初期，为避免出现早收敛现象，算法要最大可能的提高其全局搜索能力，在整个区域空间内进行搜索；在算法的后期，为达到最佳结果，则要最大提升局部搜索能力，所以，根据前文可知，如参数w＋β＝1，则表明Vjk（t＋1）作为Vjk（t）和PQk－Xjk（t）的凸组合。为满足这些要求，可设w随进化代数的增加线性逐步增加，也就是β要随着进化代数增加而线性递减，为了确保算法前期较强的全局搜索能力及后期的局部搜索能力。4.模拟实例运算证明为证明此研究中算法的准确性和有效性，分别应用基本PSO算法和本研究算法进行实例计算的对比。函数实例如下：在基本POS算法和本研究算法中，w从1线性减少到0.4，则c1和c2均为1.8，参数PQ取值为1/2，K的值取为1，分别对以上几个函数实例进行50次的模拟计算，群体规模是20，最大的进化代数是500，算法操作的终止条件和基本进化算法是一致的，可应用最大截止代数、算法在N代内群体以往最优位置变化极小，计算的结果如表1：表1两种计算方法的对比函数算法误差平均收敛的概率（%）平均收敛的代数当前最优解当前最差解f1PSO0.000011001480.0000100.000010f1本研究改进法0.000011001060.0000100.000010f2PSO0.000011002150.0000100.000010f2本研究改进法0.00001100990.0000100.000010f3PSO0.00001981843.0000013.000010f3本研究改进法0.00001981043.0000013.000010f4PSO0.00103067﹣0.990045﹣0.990283f4本研究改进法0.00109643﹣0.999911﹣0.990017再对其中两个实验函数f3和f4进行比较，如图3和图4。从具体函数来说，4个模拟实验函数所计算的结果表明，在收敛速度上，动态调整改进的微粒群算法比基本微粒群算法高25%以上，直接证明了动态调整微粒群算法具有非常高的可靠性和有效性。图3两种算法性能对比5.结语本文在剖析基本微粒群算法的前提下，提出了一种基于动态圆形的动态调整微粒群算法，通过函数实例模拟证明了该种动态调整算法不但收敛的速度较快，而且突破局部最优点的性能也得到了大幅度的提升。因该算法扩展了搜索的区域范围，进而可以有效的提升算法的全局收敛性，但也降低了算法的搜索效率[6]。所以，要实现两者关系的平衡，还需要进一步的进行研究。参考文献：[1]张沙清．基于改进微粒群算法的模具多项目动态调度[J]．计算机集成制造系统．2012，23（6）：144-146[2]崔志华．基于微分模型的改进微粒群算法[J]．急啊u树那就研究与发展．2014,11（7）:201-202[3]增建潮.一种动态调整的改进微粒群算法[J]．包装工程．2011，25（11）:169-171[4]崔琰．微粒群算法的改进及在动态环境中的应用[D]．太原科技大学.2011，16（05）:141-142[5]莫巨华.基于关键链的项目调度模型与算法[D].沈阳东北大学.2010,7（04）:104-105[6]J.Kennedy，R.C.Eberhart.ParticleswamoptimizationNeuralNetworksIndianapolis[J].IEEEServiceCenter.2011,6(11):125-127