基于改进微粒群算法的约束优化问题研究

基于改进微粒群算法的约束优化问题研究

非线性约束优化问题的解决方法可分为确定方法和随机性方法。不确定性方法通常需要函数的导数和其他信息。对目标函数和限制函数的连续性和可微性有很高的要求。它只能适用于分析性更好的函数，并且很难用于复杂的工程优化问题。函数分析的随机性要求很低。一般只使用函数值，一般用于复杂工程的优化问题，适应于面宽的一般问题。颗粒矩阵算法（pso）是一种随机算法，对优化函数没有连续的微要求。文献指出标准PSO算法不是全局收敛算法,容易陷入局部最优.为此,本文为标准PSO算法设计了一种新的适应度函数,能使算法更容易找到全局最优解.首先使用动态罚函数法将约束优化问题转化为无约束优化问题,然后将改进的微粒群算法应用于问题求解.该算法在优化目标函数的分析性质上没有特殊要求甚至可以将传统优化方法无法表达的问题描述为目标函数.1微量元素的演化微粒群算法(PSO)作为一种演化算法,也是基于群体的.它将每个个体视为无体积的微粒,在搜索空间中以变速飞行,其飞行速度根据该微粒本身的历史经验以及同伴的历史经验进行动态调整.PSO可用下面5元组形式表示:PSO=(Npopu,Kiter,V,P,Ffit).其中Npopu为群体规模;Kiter为演化代数;V和P分别表示所有微粒的速度空间和位置空间;Ffit为适应度,从位置空间映射到实数空间.设在d维空间中有m个微粒,第i个微粒表示为xi=(xi1,xi2,…,xid),i=1…m,它经历过的历史最好位置(个体适应度最小的位置)记为pi=(pi1,pi2,…,pid),i=1…m,记群体中所有微粒经历过的最好位置(群体适应度)为Pg=(g1,g2,…,gd).对第k代的第i个微粒,微粒群算法根据如下公式计算第k+1代的速度和位置:vk+1iik+1=ωvkiik+c1r1(pi-xkiik)+c2r2(pg-xi),i=1…m,(1)xk+1iik+1=xkiik+vk+1iik+1,i=1…m.式中:r1和r2为上的随机系数,ω为惯性权重,c1和c2为加速权重,通常c1被称为是认知加速权重,而c2被称社会加速权重.微粒群速度vi由最大速度vmax所限制,即若有vi>vmax,则令vi=vmax,以防止所谓微粒群爆炸的极端无序的现象出现.2改进的微群算法2.1改进推动pso算法标准微粒群算法中每一代的所有微粒都使用相同的随机系数r1和r2,这样对算法的随机搜索能力有所限制,不利于算法的全局寻优.本文对不同的微粒采用不同的随机系数,记为分布式动态随机系数ri1和ri2.惯性权重ω用来控制历史速度对当前速度的影响程度,平衡PSO算法的全局搜索能力和局部搜索能力.它的选取对PSO算法的收敛性有很大的影响.若ω较小,会加速算法对新区域的搜索能力,当然ω过大也会导致微粒群爆炸现象;若ω较小,则会增强算法对当前区域的搜索能力.适当的ω值可使算法在全局搜索能力和局部搜索能力两者之间取得平衡,使算法更优.数值试验表明,行之有效的方法是在ω初始化使取较大的值以加快全局搜索,随后将ω逐代减小,以获得更为精细的结果.这样式(1)被修正为vk+1iik+1=ωvkiik+c1ri1(pi-xkiik)+c2ri2(pg-xi).2.2适应度函数的性质在优化问题中,一般选取目标函数或与目标函数单调性完全相同的其他函数作为适应度Ffit.标准PSO算法有过早收敛的可能性,由于标准PSO算法不是全局收敛算法,容易陷入局部最优.为使算法更容易摆脱局部极小点,设计了一个新的适应度函数如下:F(x,x¯)=12[f(x)+f(x¯)−|f(x)−f(x¯)|].(2)F(x,x¯)=12[f(x)+f(x¯)-|f(x)-f(x¯)|].(2)其中f(x)是原问题的目标函数,x¯x¯是目前找到的最好点.容易证明,此函数可去掉比x¯x¯差的局部极小点,从而使局部极小点的数目在演化过程中不断大量地减少,使算法更容易摆脱局部极小点.定理式(2)给出的适应度函数可去掉比目前最好点x¯x¯差的局部极小点.证明设x*是比x¯x¯差的局部极小点,即f(x∗)>f(x¯)f(x*)>f(x¯).将x*代入式(2),则F(x∗,x¯)=12[f(x∗)+f(x¯)−|f(x∗)−f(x¯)|]=12[f(x∗)+f(x¯)−f(x∗)+f(x¯)]=f(x¯).F(x*,x¯)=12[f(x*)+f(x¯)-|f(x*)-f(x¯)|]=12[f(x*)+f(x¯)-f(x*)+f(x¯)]=f(x¯).证毕.利用函数F(x,x¯x¯)作为适应度函数,可引导算法更容易、更快的找到全局最优解.3基于约束的转化由于无约束优化问题的求解方法很多,一种很自然的想法就是设法将约束问题转化为无约束问题求解.其中罚函数法应用最为广泛.具体做法是,根据约束的特点,构造某种惩罚函数,然后把它加到目标函数中去,将约束优化问题转化为无约束优化问题来求解.这种惩罚策略,对于在无约束问题求解过程中那些企图违反约束的迭代点给予很大的目标函数值(对于极小化而言是一种惩罚).迫使一系列无约束问题的极小点或者无限的靠近可行域,或者一直在可行域内移动,直到迭代点列收敛到原约束问题的极小点.将转化后的无约束优化问题表示为G(x)=F(x,x¯)+H(x)h(k),x∈S⊂Rn.G(x)=F(x,x¯)+Η(x)h(k),x∈S⊂Rn.式中F(x,x¯x¯)为适应度函数,h(x)为惩罚力度,k为迭代代数,H(x)为惩罚因子,定义为H(x)=Σi=1mμ(φi(x))φi(x)δ(φi(x)).(3)Η(x)=Σi=1mμ(φi(x))φi(x)δ(φi(x)).(3)式中φi(x)=max{0,gi(x)},gi(x)为式中约束函数,而函数h(·),μ(·),δ(·)依赖于具体问题.4各创建题数量的算例取加速权重c1=c2=1.46;惯性权重ω从0.88逐代线性递减到0.07;最大速率vmax=2.92;群体规模Npopu=10010;演化代数kiter=1000;容忍限度设为10-6,即若约束函数gi(x)>10-6,目标函数就会获得相应的惩罚.式(3)惩罚因子H(x)中,若φi(x)<1,取δ(φi(x))<1,否则取δ(φi(x))=2;若φi(x)<0.001,取μ(φi(x))=10,若0.001≤φi(x)≤0.1,取μ(φi(x))=20,若0.1≤φi(x)≤1,取μ(φi(x))=100,否则,取μ(φi(x))=300;对于问题1,设h(x)=k√h(x)=k,对于问题2至6,设h(x)=k32,kh(x)=k32,k为演化代数.测试算例如下.问题1:f(x)=(x1−x2)2+(x2−1)2,s.t.x1=2x2−1,x214+x22≤0.f(x)=(x1-x2)2+(x2-1)2,s.t.x1=2x2-1,x124+x22≤0.问题2:f(x)=(x1−10)3+(x2−30)3,s.t.100−(x1−5)2−(x2−5)2≤0,(x1−6)2−(x2−5)2−82.81≤0,13≤x1≤100,0≤x2≤100.f(x)=(x1-10)3+(x2-30)3,s.t.100-(x1-5)2-(x2-5)2≤0,(x1-6)2-(x2-5)2-82.81≤0,13≤x1≤100,0≤x2≤100.问题3:f(x)=(x1-10)2+5(x2-12)2+x4334+3(x4-11)2+10x6556+x4774-4x6x7-10x6-8x7,s.t.-127+2x2112+3x4224+x3+4x2442+5x5≤0,-282+7x1+3x2+10x2332+x4-x5≤0,-196+23x1+x2222+6x2662-8x7≤04x2112+x2222-3x1x2+2x2332+5x6-11x7≤0,-10≤xi≤10,i=1,…,7问题4、5:f(x)=5.3578547x2332+0.8356891x1x5+37.23239x1-40792.141,s.t.0≤85.334407+0.0056858T1+T2x1x4-0.002253x3x5≤92,90≤80.51249+0.0071317x2x5+0.0029955x1x2+0.0021813x2332≤110,20≤9.300961+0.0047026x3x5+0.0012547x1x3+0.0019085x3x4≤0.25,78≤x1≤102,33≤x2≤45,27≤xi≤45,i=3,4,5.在问题4中T1=x2x5,T2=0.0006262,在问题5中T1=x2x3,T2=0.00026.问题6:f(x,y)=−10.5x1−7.5x2−3.5x3−2.5x4−1.5x5−10y−0.5Σi=13x2i,s.t.6x1+3x2+3x3+2x4+x5−6.5≤010x1+10x3+y≤20,0≤xi≤1,i=1,⋯5,y≥0.f(x,y)