一种保证全局收敛的PSO算法

1、引言。微粒群算法（PSO）的进化方程为：v(t+1)=wv(t)+cr×(p−x(t))+cr×(p−x(t))(1a)ii11ii22gix(t+1)=x(t)+v(t+1)(1b)iii其中p表示第i个微粒所经历过的最好位置，p表示所有微粒所经历过的最好位置，w、c、c为ig12常数，r,r∈[0,1]均匀分布的随机数。1 2PSO算法自提出以来，其收敛性问题一直是研究的重要方面。早期的研究大多采用代数方法，感谢阅读分析pg、pi保持不变时，PSO算法进化方程的收敛性条件[1][2]，即PSO算法收敛时参数w、c1、谢谢阅读c2应满足的条件。理论上已证明[3]：假设pg、pi在进化中保持不变，则当精品文档放心下载（+w−ϕ）2−4w<2（ϕ=ϕ+ϕ，ϕ=cr，ϕ=cr）时，PSO算法的xt2i1211122于p与p的加权中心，即x(t)→ϕp+ϕp、p在进化过程中根据其1i2g。而在实际上，pgiiϕgi适应值而不断更新，可以证明[2]，只要参数满足上述条件，PSO算法的收敛是完全保证的，但收敛的全局最优性或局部最优性则无法保证。感谢阅读有关PSO算法的全局收敛性研究，大多针对典型优化问题进行仿真实验研究，给出全局最优性的实验结果。F.Solis和R.Wets对随机优化算法提出了其全局收敛须满足的条件[4]，FransVanDenBergh博士利用该条件对基本PSO算法和保证收敛的PSO算法（GCPSO）的全局收敛性和局部收敛性进行了研究[5]，指出基本PSO算法不能保证全局或局部收敛，而GCPSO则属于局部收敛。谢谢阅读本文在对基本PSO算法进行分析的基础上，提出了一种能够保证以概率1全局收敛的PSO算法变型，并利用F.Solis和R.Wets的研究结果对其全局收敛性进行了证明。最后以典型优化问题的实例仿真对该算法进行了验证。谢谢阅读2、PSO算法的变型。在（1a）、（1b）所描述的基本PSO算法中，当w=0时，微粒的飞行速度只取决于微粒的当精品文档放心下载前位置x(t)、历史最好位置p和微粒群的历史最好位置p，速度本身无记忆性。这样，对于精品文档放心下载i i g位于全局最好位置的微粒将保持静止，而其它微粒则趋向它本身最好位置p和全局最好位置p精品文档放心下载i g的加权中心。也就是说，微粒群将收缩到当前的全局最好位置，更像一个局部算法；当w≠0时，使得微粒具有了扩展搜索空间的趋势，即具有一定的全局搜索能力。w越大，全局搜索能力越强。精品文档放心下载根据上述分析，当w=0时，（1a）、（1b）描述的进化方程为谢谢阅读x(t+1)=x(t)+cr(p−x(t))+cr(p −x(t))（2）谢谢阅读i i 11 i i 22 g i与基本PSO算法相比，（2）式描述的进化方程使得全局搜索能力减弱，而局部搜索能力加强。精品文档放心下载2同时，当x(t)=p=p时，第j个微粒将停止进化。为了改善（2）式的全局搜索能力，可保jjg留p作为微粒群的历史最好位置，而在搜索空间S重新随机产生微粒j的位置x(t+1)，其它感谢阅读g j微粒i以（2）式进化产生x(t+1)（i≠j）,则感谢阅读i=x(t+1)，j jpp,f(p)<f(x(t+1))=iii(3)ix(t+1),f(p)≥f(x(t+1))iiip'=argmin{f(p)|i−−−−=1,S}gip=argmin{f(p'),f(p)}（4）ggg若p =p，则随机产生的微粒j处于历史最好位置，无法按（2）式进化，继续在搜索空间S精品文档放心下载g j随机产生，其它微粒在更新p、p后按（2）式进化；若p ≠p，且p未更新，则所有微粒精品文档放心下载g i g j g均按（2）式进化；若p ≠p，且p已更新，即存在k≠j,使得x(t+1)=p=p，则微粒k谢谢阅读g j g k k g停止进化，在搜索空间S重新随机产生，其余微粒在更新p、p后按（2）式进化。这样在进谢谢阅读g i化的某些代，至少有一个微粒j满足x(t)=p =p，也就是说，至少有一个微粒需在S中重精品文档放心下载j j g新随机产生，这样就势必增强了全局搜索能力。为了与基本PSO算法相区别，上述算法称之为随机PSO算法（SPSO）。感谢阅读3、SPSO算法的收敛性分析。对于任意优化算法，其收敛性分析主要包括算法所产生的解序列是否收敛、收敛速度以及收敛的全局最优性或局部最优性等。感谢阅读3.1SPSO算法的微粒进化轨迹分析。由（2）式可得：x(t+1)=(1−ϕ)x(t)+ϕp+ϕp（5）ii1i2g当p、p固定时，上式为一简单的线性差分方程，当x(0)=x时，其解为：giii0x(t)=k+(x−k)(1−ϕ)t（6）ii0其中，ϕp+ϕpk=1i2g（7）ϕ3（6）式是在假设随着t的变化而p、p固定不变的情况下得到的。但在SPSO算法的进化过程精品文档放心下载g i中，p、p则随时可能更新，因此，（6）、（7）式仅在新的更好位置产生之前有效。一旦产生谢谢阅读g i新的更好位置（p或者p），微粒的运动轨迹方程将按照新的p、p，并将当前位置作为初谢谢阅读g i g i始点重新计算，也就是说（6）式中k,xi0的值重新设置。谢谢阅读从（6）式可以看出，当|1−ϕ|<1时，（5）式所描述的进化方程线性收敛，即当t→∞时，谢谢阅读x(t)→ϕp+ϕpg。根据|1−ϕ|<1，可得：0<c+c<2。也就是说，当0<c+c<21i2iϕ1212时，SPSO算法的进化方程线性渐近收敛。定理1：当|1−ϕ|<1时，limx(t)=pt→∞ig证明：由（6）式知，当|1−ϕ|<1时，limx(t)=k=ϕp+ϕp1i2g，而t→∞iϕx(t+1)=x(t)−(+ϕ)x(t)+ϕp+ϕp当t→+∞时，ϕii12i1i2glimx(t+1)=limx(t)，则t→+∞it→+∞i−(ϕ+ϕ)limx(t)+ϕp+ϕp=012t→+∞i1i2g由于ϕϕ为随机变量，显然只有当limx(t)=p=p时，上式满足。12t→+∞iig3.2SPSO算法的全局收敛性。F.Solis和R.Wets在文献[4]中证明了随机优化算法以概率1收敛于全局最优解的条件，为了分析方便，首先给出其主要结论。感谢阅读假设1：若f(D(z,ξ))≤f(z),ξ∈S,则f(D(z,ξ))≤f(ξ)感谢阅读其中D为产生问题解的函数，ξ为从概率空间(Rn,B,μ)产生的随机向量，f为目标函数，S谢谢阅读k为Rn的子集，表示问题的约束空间。μ为B上的概率度量，B为Rn子集的σ域。精品文档放心下载k假设2：若对S的任意Borel子集A，有v(A)>0，则谢谢阅读∏∞(1−μ[A])=0 （8）k=0其中：v(A)为子集A的n维闭包，μk(A)为由μk产生A的概率。精品文档放心下载定理2：设f为一可测函数，S为Rn的一可测子集，{z}∞为随机算法产生的解序列，则当满精品文档放心下载k 04足假设1和假设2时，有limP[z∈R]=1k→+∞kε其中Rε为全局最优点集合。也就是说，对一个随机优化算法，只要能够满足假设1与假设2，则就可以保证以概率1收敛于全局最优解。下面对SPSO算法分析其是否满足上述假设。感谢阅读在SPSO算法中，其解序列为{p}，其中t为进化代数，p为第t代时的微粒群最好位g,tg,t置。对SPSO算法定义函数D为p,f(p)≤f(x(t))D(px（9）(t))=g,tg,tig,tix(t),f(p)>f(x(t))ig,ti则很容易证明其满足假设1。为了满足假设2，规模为S的微粒群的样本空间的并必须包含S，即感谢阅读S⊆USM,t=1其中M为t代时微粒i的样本空间的支撑集。对于满足x(t)=p=p的微粒j,M=S。而i,tjkgi,t对于其它微粒i:M=x(t−1)+ϕ(p−x(t−1))i,ti1ii+ϕ(p−x(t−1))2gi由于0≤ϕ≤c,0≤ϕ≤c，则Mi,t为一具有顶点ϕ=ϕ=0和ϕ=c,ϕ=c的超矩形1122121122max(c|p−x(t−1)|,c|p−x(t−1)|)时，v[MIS]<v(s)，其中diam(S)表体，且当1ii2gi0.5×diam(S)<i,t示S的长度。由定理1，当t→∞时，M的长度趋于0。因此，随着t的增长，每一Mi,t的i,t闭包v[M]在逐渐变小，其并集UM的闭包v[UM]也在变小。因而存在N，使得t>Ni,ti≠ji,ti≠ji,t时，v[UM∩S]<v[S]。也就是说仅有进化方程（2）的PSO算法不满足假设2。i≠ji,t但由于MS=S，定义S的Borel子集A=M,则有v[A]>0，=S，所以UMi,ti,ti,t=1[A]=∑Sμ[A]=1，从而满足假设2。由定理2，SPSO算法以概率1收敛于全局最优解。谢谢阅读t i,t=0从上述分析可以看出，SPSO算法与基本PSO算法相比，去掉了微粒先前的速度项，使得速度本身失去记忆性，从而减弱了全局搜索能力。但这样也使得在进化的每一代均至少有一个微精品文档放心下载5粒由于处于微粒群的历史最好位置而停止进化，利用停止进化的微粒改善全局搜索能力是SPSO算法的基本思想。在收敛性方面，SPSO算法与PSO算法具有几乎完全相同的性质，即在参数的谢谢阅读一定范围内均能保证x(t)收敛于群体历史最好位置。对于收敛的全局最优性，基本PSO算法无感谢阅读i法保证，而SPSO算法当进化代数t→∞时能保证依概率1收敛于全局最优解。但是，在实际应用中，如何改善停止进化微粒的产生方式，以达到在有限进化代数内搜索到全局最优解的目的是值得研究的问题。感谢阅读4、停止进化微粒的产生 。为了使微粒j以较大概率位于最优点附近，可采用其它一些非群体随机优化方法进行生成，如模拟退火方法[6]，遗传算法[7]等。精品文档放心下载（1）利用模拟退火方法产生停止进化微粒模拟退火算法（simulatedannealing）是基于MenteCarlo迭代求解策略的一种随机优化算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法在某一出温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性的跳出并最终趋于全局最优。感谢阅读以当前代历史最好位置pg为初始状态，即xtp，并选择初始温度T=T，采用下j()=g0式产生下一状态：x'(t+1)=x(t)+ηξ（10）jj其中η为扰动幅值参数，ξ为随机变量，一般可服从柯西分布、正态分布或均匀分布。计算感谢阅读f'=f(x'(t+1)),f=f(x(t))，=f'−f，jjjjjj'(t+1),min{1,e−/Tγx(t+1)xk=jj（11）jx(t),otherwisej其中γ∈[0,1]均匀分布的随机变量。jT=λT,0<λ<1（12）k+1k（2）利用遗传算法产生停止进化微粒停止进化微粒的产生还可以利用遗传算法在整个搜索空间进行搜索，在给定的进化代数内得到的最优解作为其的位置。在我们的实验中，遗传算法为最优保存遗传算法，其中，杂交、变异、选择算子分别为算术杂交、均匀性变异、转轮法选择。它们分别为：感谢阅读算术杂交算子设x=(x,x,...,x)和y=(y,y,...,y)是两个父向量，结果为 w=(w,w,...,w)、谢谢阅读1 2 n 1 2 n 1 2 nv=(v,v,...,v)，且α为介于0，1之间的随机数，则有感谢阅读1 2 n jw=αx+(1−α)y（13）jjjjj6v=αy+(1−α)x（14）jjjjj均匀性变异算子x=(x,x,...,x)为父向量，y=(y,y,...,y)为其变异结果。均匀性变异是先在父向谢谢阅读1 2 n 1 2 n量中随机选择一个分量，假设为第k个，然后，在其定义域区间[a,b]中均匀随机取一个数x'谢谢阅读j j k来代替x，即kx,i≠ky=i',i=k（15）kxk转轮法选择算子f先计算个体的相对适应值j记为pj，随机生成数r∈[0,1]，若∑fjp+p+...+p<r≤p+p+...+p（16）12j−112j则选择个体j。为了进一步提高算法效率，我们引入了混沌随机数发生器。混沌是一种普遍的非线性现象，具有很独特的性质：（1）随机性，即混沌具有类似随机变量的杂乱表现；（2）遍历性，即混沌能够不重复的历经一定范围内的所有状态；（3）规律性，即混沌是由确定性的迭代式产生的。介于确定性和随机性之间，混沌具有丰富的时空动态，系统动态的演变可导致吸引子的转移。最重要的是，混沌的便历性特点可作为搜索过程中避免陷入局部极小的一种优化机制，这与模拟退火的概率性劣向转移存在明显的区别。精品文档放心下载其中一种非常有名的混沌序列为Logistic序列，在参数为x =0.2027和a=4.0的情况下，精品文档放心下载0其迭代方程为x=ax(1−x)（13）k+1kk我们在利用遗传算法产生停止进化微粒的算法中使用了基于Logistic序列的随机数发生器。感谢阅读由于模拟退火方法和最优保存遗传算法本身具有很好的全局收敛性，因而采用该方法生成微粒j并依（10）、（11）式进行状态更新对于SPSO算法的全局收敛性不会产生负面影响。精品文档放心下载5、实例计算 。为了验证本文算法的有效性，分别采用基本PSO算法和SPSO算法对下列函数的最小化问题进行实例计算。谢谢阅读（1） Goldstein-Price函数f(x)=[1+(x+x+1)2(19−14x+3x2−14x+6xx+3x2)]112112122×[30+(2x−3x)2(18−32x+12x2+48x−36xx2+27x2)]，−2≤x,x≤2121121212（2） J.D.Schaffer函数7f(X)=sin2x2+x2−0.5≤10012−0.5，−100≤x,x2[1+0.001(x2+x2)]21212函数f（图1）的最优状态和最优值为f(0,−1)=3。f（图2）的全局极小点是（0，0）；132而在距全局极小点约3.14范围内的隆起有无限多全局极大点，取值为-0.990283，因此很容易陷入局部极小点。由于该函数的强烈震荡性质以及它的全局最优点被局部最优点所包围的特性使得一般算法很难找到它的全局最优解。谢谢阅读图1、函数f的图像 图2、函数f的图像1 2在基本PSO算法中，w从1.0到0.4随进化而线性减少，c =c=1.8。在SPSO算法中，精品文档放心下载1 2取c=c =0.5，对停止进化微粒分别采用模拟退火和遗传算法两种方法分别对上述问题进行谢谢阅读1 250次仿真计算，群体规模为20，最大进化代数为500，遗传算法中的杂交概率为0.75，变异概率为0.1，模拟退火的初始温度为500，其计算结果如表1所示。为了比较三个算法的性能，精品文档放心下载我们在相同的初始条件下，对两个测试函数进行计算，对于函数f而言，每隔5代记录一次当谢谢阅读1前最优解，测试的最大进化代数为100；对于函数f而言，每隔25代纪录一次当前最优解，测谢谢阅读2试的最大进化代数为500。结果如图3、4所示。精品文档放心下载函数 算法 误差 平均收敛率 平均收敛代数F1PSO0.00001100186.94F1SPSO10.000018811.886364F1SPSO20.0000110018.54F2PSO0.17621.973684F2SPSO10.1526.807692F2SPSO20.19672.958333表1：实例计算结果8图3、三种算法在函数f中的表现 图4、三种算法在函数f中的表现谢谢阅读1 2其中，PSO表示基本的微粒群算法，SPSO1表示停止进化微粒的产生方式为模拟退火算法，SPSO2表示停止进化微粒的产生方式为遗传算法及基于混沌的随机数发生器。感谢阅读从表1中可以看出，不论对于函数f还是f，SPSO1的进化速度最快，平均收敛代数最小，谢谢阅读1 2不到PSO的6.36%，即使与SPSO2相比还少35.89%；但其平均收敛率最低（约为其它两种算法精品文档放心下载88%），这是由于我们所选的初始温度太低而导致的结果，同时为了表明使用模拟退火算法计算停止进化微粒的产生方式能迅速增加随机微粒群算法的局部收敛性能，当然，如果提高算法的初始温度，并调节其降温过程，SPSO1的平均收敛率会提高。而对于SPSO2而言，对于两个测试函数，其平均收敛率最高，这表明使用最优保存遗传算法计算停止进化微粒的产生方式能有效的提高随机微粒群算法的全局收敛能力。但对局部收敛能力的提高是极其有限的，这一点可以从谢谢阅读平均收敛代数来看，对于函数f 而言，SPSO2的平均收敛代数仅为PSO的10%，而对于函数f感谢阅读1 2而言，S