粒子群算法的改进及其在求解约束优化问题中的应用

JOURNALOFJILINUNIVERSITY(SCIENCEEDITION)

Vol.43　No.4

July　2005

粒子群算法的改进及其在求解约束优化问题中的应用

刘华蓥,林玉娥,王淑云

1

1

2

(1.大庆石油学院计算机与信息技术学院,黑龙江省大庆163318;2.吉林大学数学学院,长春130012)

摘要:在用粒子群算法求解约束优化问题时,处理好约束条件是取得好的优化效果的关键.通过对约束问题特征和粒子群算法结构的研究,提出求解约束优化问题一种改进的粒子群算法,该算法让每个粒子都具有双适应值,通过双适应值决定粒子优劣,并提出了自适应保留不可行粒子的策略.实验证明,改进的算法是可行的,且在精度与稳定性上明显优于采用罚函数的粒子群算法和遗传算法等算法.关键词:粒子群优化算法;双适应值;自适应

中图分类号:TP301　　文献标识码:A　　文章编号:1671254(2005)0420472205

AModifiedParticleSwarmOptimizationfor

SolvingConstrainedOptimizationProblems

LIUHua2ying,LINYu2e,WANGShu2yun

1

1

2

(1.CollegeofComputerandInformationTechnology,DaqingPetroleumInstitute,Daqing163318,HeilongjiangProvince,China;2.CollegeofMathematics,JilinUniversity,Changchun130012,China)

Abstract:Intryingtosolveconstrainedoptimizationproblemsbyparticleswarmoptimization,thewaytohan2dletheconstrainedconditionsisthekeyfactorforsuccess.Somefeaturesofparticleswarmoptimizationandalargenumberofconstrainedoptimizationproblemsaretakenintoaccountandthenanewmethodisproposed,whichmeanstoseparatetheobjectivefunctionsfromitsconstrainedfunctions.Therefore,everyparticleofparticleswarmoptimizationhasdoublefitnessvalueswhethertheparticleisbetterornotwillbedecidedbyitstwofitnessvalues.Thestrategytokeepafixedproportionofinfeasibleindividualsisusedinthisnewmethod.NumericalresultsshowthattheimprovedPSOisfeasibleandcangetmorepreciseresultsthanparticleswarmoptimizationbyusingpenaltyfunctionsandgeneticalgorithmandotheroptimizationalgorithms.Keywords:particleswarmoptimization;doublefitnessvalue;adaptive

对于约束优化问题,大多数算法都基于梯度的概念,要求目标函数和约束条件可微,而且一般只

[1,2]

能求得局部最优解.粒子群优化算法(ParticleSwarmOptimaziton,简称PSO),由于其具有容易理解、易于实现、不要求目标函数和约束条件可微,并能以较大概率求得全局最优解的特点,目前已在许多优化问题中得到成功应用

[3～5]

.

当用PSO算法求解约束优化问题时,如何处理约束条件是得到好的优化结果的关键.惩罚函数法是处理约束条件最常用的方法,通过在适应值函数上添加一个惩罚项,即将原来的约束问题变成无约束问题.惩罚函数法简单易行,但选择适当的惩罚因子却不是一件容易的事,若选的过小,则惩罚项在目标函数中所占比例较小,较难产生可行解;若选的过大,则将会较早地收敛于某个局部最优点.

收稿日期:2004211220.

作者简介:刘华蓥(1969～),女,汉族,硕士,副教授,从事智能计算的研究,E2mail:liuhuaying2000@yahoo.com.cn.

　第4期　　　　　　刘华蓥,等:粒子群算法的改进及其在求解约束优化问题中的应用　　　473

本文结合PSO算法及约束优化问题的特点,提出了比较个体优劣的一个新准则将约束条件与目标

函数分离,并引入自适应保持群体中不可行解比例的策略,二者相结合得到了处理约束条件的一种新方法,将这种方法和基本的PSO算法相结合,得到了求解约束优化问题的一种改进的PSO算法.

1　粒子群优化算法

PSO算法与其他进化类算法相似,也采用“群体”与“进化”的概念,同样也依据个体(粒子)的适

应值大小进行操作.不同的是,粒子群算法不像其他进化算法那样对于个体使用进化算子,而是将每个个体看作是在n维搜索空间中的一个没有重量和体积的粒子,并在搜索空间中以一定的速度飞行.每个粒子的飞行速度由其本身的飞行经验和群体的飞行经验调整.假设在一个n维的目标搜索空间中,有m个粒子组成一个群落,其中第i个粒子表示为一个n维向量xi=(xi1,xi2,…,xin)(i=1,2,…,

m),即第i个粒子在n维搜索空间中的位置是xi,每个粒子的位置代表一个潜在的解.将xi带入一个

目标函数就可以计算其适应值,根据适应值的大小衡量xi的优劣.第i个粒子的“飞翔”速度也是一个

n维向量,记为vi=(vi1,vi2,…,vin).记第i个粒子最终搜索到的最优位置为pi=(pi1,pi2,…,pin),整个

粒子群最终搜索到的最优位置为pg=(pg1,pg2,…,pgn).每个粒子的位置和速度按下述方程迭代:

vij(t+1)=wvij(t)+c1r1j(t)(pij(t)-xij(t))+c2r2j(t)(pgj(t)-xij(t)),xij(t+1)=xij(t)+vij(t+1),

(1.1)(1.2)

其中,j表示粒子维数(i=1,2,…,n),i表示第i个粒子(i=1,2,…,m),t表示第t代,c1和c2为加速度常数,通常取值于0～2,c1调节粒子向自身最优位置飞行的步长,c2调节粒子向全局最优位置飞行的步长.r1j～U(0,1),r2j～U(0,1)为两个相互的随机函数.

为了减小在进化过程中粒子离开搜索空间的可能性,vij通常限定于一定范围内,即vij∈

[-vmax,vmax].如果问题的搜索空间限定在[-xmax,xmax]内,则可设定vmax=kxmax(0.1≤k≤1).迭代中

若粒子的位置和速度超出了对其限定的范围,则取边界值.pij(t)-xij(t)表示粒子i目前位置到其最终搜索到最优位置的距离,pgj(t)-xij(t)表示粒子i目前位置到整个粒子群最终搜索到最优位置的距离.方程(1.1)用于计算粒子速度,如当前是t时刻,则粒子在t+1时刻速度是由当前时刻的速度、位置与该粒子的局部最优位置距离、当前位置与全局最优位置距离三部分共同决定.方程(1.2)用于计算粒子速度更新后的位置,它由粒子当前位置和粒子更新后的速度两部分决定.所有粒子的初始位置和速度随机产生,然后根据式(1.1),(1.2)进行迭代,不断变化它们的速度和位置,直至找到满意解为止

(粒子的位置即是要寻找的解).

2　处理约束条件的分离比较方法

求解带有约束条件的极值问题称为约束优化问题,一般形式表示为

minf(x),

gj(x)≥0,

j=1,…,q;p=1,…,m;

u

s.t.hp(x)=0,xi≤xi≤xi,

l

(2.1)

i=1,…,n,

n

n

这里x=(x1,…,xn)∈R是n维实向量,f(x)为目标(适应值)函数,gj表示第j个不等式约束,hp表

示第p个等式约束,变量xi在区间[x,x]中取值.S=条件的可行解构成的可行域记为FΑS.

liui

∏[x,x

li

i=1

ui

]表示搜索空间,S中所有满足约束

当对带有约束条件的问题进行优化处理时,无论采用何种优化算法,约束条件的处理方法都是一个非常重要的环节.目前,使用最广泛处理约束条件的方法是惩罚函数法,但对于要解决的约束优化问题,事先确定适当的罚因子很困难,往往需要通过多次实验不断进行调整.文献[6]将分离方法的思想与遗传算法中广泛使用的竞争选择方法相结合,引入了不需要罚因子而直接比较个体优劣的分离

474　　吉林大学学报(理学版)　　　第43卷　比较方法,即将要处理问题的目标函数和其约束条件分离,并通过一定的规则进行比较选优,对于两个给定的解个体,当两个解个体都可行时,通过比较它们的适应值f(x)来判断优劣;当二者之中有一个可行而另一个不可行时,则无条件地认为可行解的个体为优;当这两个解个体都不可行时,则根据它们所对应的作为违反约束的度量函数值直接判定它们的优劣,违反约束越小的个体越好.这种分离比较方法既可以避免选择罚因子,同时也达到了使任一可行解个体优于任一不可行解个体的目的.

3　采用双适应值比较法与自适应保留不可行解改进的PSO算法

3.1　PSO算法中的双适应值比较法

考虑到PSO算法与遗传算法都是根据适应值大小确定其个体优劣的,把处理约束条件的分离比较方法引入到PSO算法中.PSO算法中每个粒子均有一个适应值,其适应值可由目标函数来度量.对于最小化问题,适应值小者为优.对于约束优化问题(2.1),采用分离目标函数与约束条件的方法,于是,原来的问题可转化为

q

mj

fitness(i)=f(x),voilation(i)=

∑max(0,g(x))

j=1

+

p=1

∑h

p

(x),i=1,2,…,n,

(3.1)

其中,i指第i个粒子,fitness(i)对应于所求问题的目标函数值;voilation(i)对应于所求问题约束条件,由所有的约束条件共同构成,该值反映了每个粒子与约束边界的接近程度.这两个函数一起作为粒子的适应函数,每个粒子的优劣将由这两个函数值按一定规则共同决定,因此每个粒子均具有双适应值,这种方法称为双适应值比较法.3.2　PSO算法中粒子的比较准则考虑到存在一大类约束优化问题,其最优解位于约束边界上或附近,即在最优点处不等式约束的全部或大部分取为等号,对于这类问题,当目标函数f(x)连续时,在最优解附近的不可行解的适应值很可能优于位于可行域F内部的一个可行解的适应值,而这样的不可行解对找到最优解都是很有帮助的.鉴于PSO算法是一种群体搜索策略,从提高优化效率的角度考虑,让一部分接近边界的不可行解与可行解按照它们的适应值进行比较,以便在群体中保留一定比例的不可行解个体.因此,我们采用下列比较准则:首先给定一个常数ε>0.

(1)当两个粒子i和j都可行时,比较它们之间的适应值finess(i)和fitness(j),适应值小的个体为优(对最小化问题);

(2)当两个粒子i和j都不可行时,比较voilation(i)和voilation(j),voilation小的个体为优(最大化和最小化问题都采用该规则);

(3)当i粒子可行而j粒子不可行时,如果voilation(j)<ε,则比较它们的适应值fitness(i)和fitness(j),适应值小的个体为优(对最小化问题);否则,i粒子为优.3.3　保持不可行解粒子的自适应策略

如果让所有可行解粒子无条件地优于不可行解粒子,则在群体中很难保持一定比例的不可行解粒子,从而无法发挥不可行解的作用.我们的最终目的是求得可行解,在群体中保持不可行解是为了更好地搜索可行的最优解,因此,将不可行解的比例控制在一个适当水平是必要的.由于PSO算法的进化过程是一个动态的自适应过程,相应的控制策略也应当设计成自适应的.由上述比较准则可知:ε越大,群体中不可行解的比例就可能越高,为了将不可行解的比例保持在一个固定的水平p>0,可引入如下自适应调整ε的策略:

ε1.2,当不可行解所占比例小于p时;

ε=0.8(3.2)ε,当不可行解所占比例大于p时;

ε,当不可行解所占比例等于p时.

　　在PSO算法中,每隔10代将根据式(3.2)对ε进行一次更新,从而保证了不可行解所占的比例.

4　参数设定与数值实验

为了测试改进的PSO算法对约束优化问题的求解性能,下面选择3个例子进行仿真实验.

　第4期　　　　　　刘华蓥,等:粒子群算法的改进及其在求解约束优化问题中的应用

[7]

　　　475

例4.1　非凸可行域的非线性约束优化问题:

2222

minf(x)=(x1+x2-11)+(x1+x2-7),

s.t.

g1(x)=4.84-(x1-0.05)-(x2-2.5)≥0,g2(x)=x1+(x2-2.5)-4.84≥0,　0≤x1,x2≤6.

2

　　例4.1的真实可行域为一个月牙形的狭窄空间,可行域面积仅占总的解空间面积的0.7%,目前3

已知其最优值f(x)=13.5908.本文算法的参数设置:群体规模设为80,p=0.2,ε=0.01,取加速权重c1=1.5,c2=2.5,惯性权重w=1.4.w将随着迭代次数的增加而逐渐减小,当w<0.4时,将令

w=0.4,即不再减小,以保证迭代后期粒子能够在一定的空间内探索到更好地解.在采用罚函数的

PSO算法中,惩罚因子设置为10,两种方法最大进化次数均为20次.分别进行了10次实验,两种方

8

法每次所得结果都很稳定,改进的PSO算法在进化到10次左右时,就得到最优值13.5908,而采用罚函数的PSO算法在15～20次时得最优值为14.4245.图1为两种PSO算法10次实验的平均进化过程曲线.

为了进一步验证改进的PSO算法优于采用罚函数的PSO算法,选择一个未知量多、约束条件也多[8]

的例子进行测试.

例4.2　

2242624

minf(x)=(x1-10)+5(x2-12)+x3+3(x4-11)+10x5+7x6+x7-4x6x7-10x6-8x7,

-127+2x1+3x2+x3+4x4+5x5≤0,2

4

2s.t.

-282+7x1+3x2+10x3+x4-x5≤0,-196+23x1+x2+6x6-8x7≤0,

22

2

2

2

2

4x1+x2-3x1x2+2x3+5x6-11x7≤0,　-10≤xi≤10,i=1,2,…,7.

　　已知例4.2最优值f(x)=680.6300573.取种群规模为150,进化200次,进行10次实验.改进的PSO算法每次都能在150次左右求得最优值680.632;而采用罚函数的PSO算法每次所得的结果很不稳定,最好结果为683.036,最差结果为831.354.图2为两种PSO算法10次实验的平均进化过程曲线.

3

从上面两组实验可以看出,改进的PSO算法不但收敛速度快,求解精度高,而且稳定性能也大大优于采用罚函数的粒子群算法.通过实验也发现,当问题变得复杂时,不需要调整算法的任何参数,只要适当的加大种群数量即可.

为了和遗传算法等其他一些算法进行比较,我们对下面的例子进行了测试.例4.3　

22

minf(x)=(x1-2)+(x2-1),

s.t.

g1(x)=x1-2x2+1=0,

g2(x)=-x1/4-x2=1>0,　0≤x1,x2≤10.

2

2

3

　　已知最优值为f(x)=1.393,取种群规模为80,采用改进的PSO算法进行10次实验,每次均能

476　　吉林大学学报(理学版)　　　第43卷　

在进化20次内收敛到最优值1.393465.表1列出了改进的PSO算法和遗传算法等其他算法所得结果的比较结果.

Table1　Thebestresultsbyusingfollowingmethods

ImprovedPSO

x1x2g1(x)g2(x)f(x)

Self2adaptivemultiplier

0.82280.91120.004-0.0431.3937

[9]

Gen

[10]

Homaifar

[11]

GRG

[12]

0.8228760.9114380

-0.000000461.393465

0.80800.885440.0370.0521.4339

0.81020.90260.050.0251.4251

0.82290.91150.0001-0.00005151.3934

　　综上可见,处理好约束条件是用PSO算法求解约束优化问题时所面临的一个关键问题.本文结合

PSO算法的群体搜索特性,采用新的比较准则双适应值比较法来比较粒子的优劣,得到了求解约束优化问题改进的PSO算法.数值实验表明,它是一种便于实现、通用性强、高效稳健的方法,不仅优于采用罚函数的PSO算法,而且也优于遗传算法等其他一些算法,为利用PSO算法求解约束优化问题提供一条可行途径.

参考

文献[1]　KennedyJ,EberhartRC.ParticleSwarmOptimization[C].IEEEInternationalConferenceonNeuralNetworks.Perth,

Piscataway,NJ,Australia:IEEEServiceCenter,1995,Ⅳ:1942—1948.

[2]　ShiY,EberhartRC.AModifiedParticleSwarmOptimizer[C].

Anchorage,Alaska,1998:69—73.

[3]　EberhartRC,HuX.HumanTremorAnalyisUsingParticleSwarmOptimization[C].ProceedingoftheIEEECongress

onEvolutionaryComputation(CEC1999).Washinggon:IEEEPress,1999:1927—1930.

[4]　HUANGLan,WANGKang2ping,ZHOUChun2guang.ParticleSwarmOptimizationforTravelingSalesmanProblems

[J].JournalofJilinUniversity(ScienceEdition),2003,41(4):477—480.(黄　岚,王康平,周春光.粒子群优

IEEEInt’lConfonEvolutionaryComputation.

化算法求解旅行商问题[J].吉林大学学报(理学版),2003,41(4):477—480.)

[5]　ZHANGLi2biao,ZHOUChun2guang.ANovelEvolutionaryAlgorithmforSolvingConstrainedOptimizationProblems

[J].JournalofJilinUniversity(ScienceEdition),2004,42(4):534—540.(张利彪,周春光.求解约束优化问题

的一种新的进化算法[J].吉林大学学报(理学版),2004,42(4):534—540.)

[6]　PowellD,SkolnickM.UsingGeneticAlgorithmsinEngineeringDesignOptimizationwithNonlinearConstraints[C].

In:For2estS,ed.ProceedingSofthe5thInternationalConferenceonGeneticAlgorithms.Sanmateo,CA:MorganKaufmannPublishers,1993:424—430.

[7]　ZHANShi2chang.GeneticAlgorithmforConstrainedOptimizationProblemsWhichisBasedontheAnnealingInfeasible

Degree[J].JournalofBasicScienceandEngineering,2004,12(3):299—304.(詹士昌.基于退火不可行度的约

束优化问题遗传算法[J].应用基础与工程科学学报,2004,12(3):299—304.)

[8]　PANZheng2jun,KANGLi2shan.EvolutionaryComputation[M].Beijing:TsinghuaUniversityPress,2001.(潘正君,

康立山.演化计算[M].北京:清华大学出版社,2001.)

[9]　ZHANGChun2kai,SHAOHui2he.ApplicationofSelf2adaptiveMultiplierinEngineeringOptimizationProblem[J].

ControlandDecision,2001,16(6):669—672.

(张春慨,邵惠鹤.自适应乘子在工程优化问题中的应用[J].控

制与决策,2001,16(6):669—672.)

[10]　GenM,CHENGRun2wei.GeneticAlgorithmsandEngineeringDesign[M].NewYork:JohnWiley&SonaPress,

1997.

[11]　HomaifarA,LaiSHY,QiX.ConstrainedOptimizationviaGeneticAlgorithms[J].Simulation,1994,62(4):

242—254.

[12]　DavidMHimmelblau.AppliedNonlinearProgramming[M].NewYork:McGraw2HillPress,1972.

(责任编辑:赵立芹)