Stochastic convergence analysis and parameter selection of the standard particle swarm optimization

粒子群优化

InformationProcessingLetters102(2007)

8–16

/locate/ipl

Stochasticconvergenceanalysisandparameterselectionofthestandardparticleswarmoptimizationalgorithm

M.Jiang ,Y.P.Luo,S.Y.Yang

DepartmentofAutomation,TsinghuaUniversity,Beijing100084,ChinaReceived18January2006;receivedinrevisedform20October2006

Availableonline17November2006CommunicatedbyF.MeyeraufderHeide

Abstract

Thisletterpresentsaformalstochasticconvergenceanalysisofthestandardparticleswarmoptimization(PSO)algorithm,whichinvolveswithrandomness.Byregardingeachparticle’spositiononeachevolutionarystepasastochasticvector,thestandardPSOalgorithmdeterminedbynon-negativerealparametertuple{ω,c1,c2}isanalyzedusingstochasticprocesstheory.Thestochasticconvergentconditionoftheparticleswarmsystemandcorrespondingparameterselectionguidelinesarederived.©2006ElsevierB.V.Allrightsreserved.

Keywords:Particleswarmoptimization;Analysisofalgorithms;Stochasticconvergenceanalysis;Stochasticoptimization;Parameterselection

1.Introduction

Theparticleswarmoptimization(PSO)isanalgo-rithmfor ndingoptimalregionsofcomplexsearchspacesthroughtheinteractionofindividualsinapop-ulationofparticles[2].ItwasdevelopedbyKennedyandEberhart[3]basedonthesocialbehaviormetaphor.Thealgorithmsearchesasolutionspacebyadjustingthetrajectoriesofindividualvectors,called“particles”astheyareconceptualizedasmovingpointsinmultidi-mensionalspace.Eachparticleisassignedarandomizedvelocity.Theindividualparticlesareattractedstochas-ticallytowardthepositionsoftheirownbest tnessachievedsofarandthebest tnessachievedsofarbyanyoftheirneighbors.

*Correspondingauthor.

E-mailaddress:jming99@(M.Jiang).0020-0190/$–seefrontmatter©2006ElsevierB.V.Allrightsreserved.doi:10.1016/j.ipl.2006.10.005

Sincethe rstformalanalysisofasimpleparticleswarmsystempresentedbyOzcanandMohan[4,5],thePSOalgorithmhasbeentheoreticallyanalyzedbyvandenBergh[8],ClercandKennedy[2],Yasudaetal.[9],andTrelea[7].Althoughthoseresultsprovidein-sightsintohowparticleswarmsystemworks,allthoseanalysisdiscardtherandomnessinthestandardPSOal-gorithm,andareallbasedonasimpli eddeterministicalgorithm.Obviously,thoseanalyticalresultsmoreorlessdeviatefromtherealparticleswarmsystemduetothelossofrandomness.

Byregardingeachparticle’spositiononeachevo-lutionarystepasastochasticvector,thestandardPSOalgorithmcanbeanalyzedusingstochasticprocessthe-ory.Theexpectationandvarianceoftheparticle’sposi-tioninasimpli edone-particleone-dimensionalparti-cleswarmsystemiscalculated,andcorrespondingcon-vergencepropertyisanalyzed.Afterthat,thepresentworkgivesconvergenceanalysistothestandardpar-

粒子群优化

M.Jiangetal./InformationProcessingLetters102(2007)8–169

ticleswarmsystem,consideringtherandomin uencethoroughly.Asfartotheauthors’knowledge,thisisthe rstcontributiontoanalyzethestochasticstandardPSOalgorithm,insteadofasimpli eddeterministicone.ThetermConvergenceiswidelyusedinthisletter,withdifferentmeanings.Ifitisusedtodescribeade-terministicsequence{A(t)},t=0,1,...,Convergencereferstothepropertythatthelimit

t→∞

limA(t)=A

exists,whereAistheconvergentvalue(aconstant),andbothA(t)andAarescalarsorvectors.

Whendealingwithaparticleswarmsystem,becauseparticles’positionsinvolverandomness,thusnodeter-ministicconvergentresultcanbeobtained.Inthislet-ter,Convergenceofaparticleswarmisde nedasthe

propertythatfor inmeansquaretoP

i∈{1,2,...,M}, i(t)converges(i.e.limt→∞E|X X

i(t) P |2=0),whereMisthepopulationsizeoftheswarm,P

isapo-sitioninthesearchspace,andX

i(t)isthepositionoftheithparticleintheswarmattimet.Underthissitua-tion,itissaidthattheparticleswarmsystemconverges

toP

.GivenEX i(t)astheexpectationofX i(t)andDX

i(t)thevariance,obviouslyconvergesinmean theconditionthatX i(t)equalstoconvergestoP

square toP

thatEX i(t)andDXi(t)convergesto0simultane-ously.

Generallyspeaking,thisworkcanbeseenasanex-tensionofvandenBergh’swork[8],thoughtheper-spectivesaredifferent.Theresultderivedinthisletterextendsallabovementionedtheoreticalanalysisresults.Astochasticconvergentconditionofthestandardparti-cleswarmsystemisderived.Guidelinesforparameterselectionaredirectlygivenbytheanalysisresult,bothinformularandgraphicalform.

2.Particleswarmoptimizationalgorithm2.1.Standardalgorithm

ThestandardPSOalgorithmmaintainsapopula-tionofMparticles,thePSOformulaede neeachparticleasapotentialsolutiontoaproblemmensionalspace,withparticleirepresentedX

inD-di-i=(Xi1,Xi2,...,XiD),wherei=1,2,...,M.EachparticlealsomaintainsP

amemoryofitspreviousbestposition,i=(Pi1,Pi2,...,PiD),andmension,represented avelocityalongeachdi-i=(Vi1,Vi2,...,ViD).TheP

asV

vectoroftheparticlewiththebest tnessintheborhoodisdesignatedP

g.Ateachiteration,P neigh-gP

andthevectorofthecurrentparticlearecombinedtoadjustthevelocityoftheparticlealongeachdimension,and

thatvelocityisthenusedtocomputeanewpositionfortheparticle.Theportionoftheadjustmenttotheveloc-ityin uencedbytheindividual’spreviousbestpositionisconsideredthecognitioncomponent,andtheportionin uencedbythebestintheneighborhoodisthesocialcomponent[3].

Withoutlossofgenerality,consideraminimizationtaskandusesymbolftodenotetheobjectivefunctionthatisbeingminimized.TheupdateequationfortheddimensionofthepersonalbestpositionP

th

iispresentedinEq.(1),withthedependenceonthetimesteptmadeexplicit.

P1)=

Pid(t)iff(X i(t+1)) f(P i(t)),id

(t+Xdi

(t+1)iff(X i(t+1))<f(P i(t)).(1)InstandardPSOalgorithm[6],atiterationt,thedthdimensionofparticlei’svelocityandpositionareup-datedusingEqs.(2)and(3)separately,whereω,cc2arenon-negativeconstantrealparameters,r1d1and

,i

(t)andr2d,i(t)aretwoindependentuniformrandomnumbersdistributedintherange[0,1].

Vid(t+1)=ωVid(t)+cd dd

+c2r 1r1,i

(t)Pi(t) Xi(t)2d,i(t)Pgd(t) Xd

(t) i,

(2)Xdi(t+1)=Xd

i(t)+Vid(t+1).

(3)

Thevelocityupdateequationcanalsobedescribedus-ingEq.(4),whereχ, 1and 2arenon-negativecon-stantrealparameters[2].Obviously,bychoosingap-propriateparameters,Eqs.(2)and(4)areidentical.Inthisletter,Eqs.(1)–(3)areusedasstandardPSOupdateequations.

V)=χ V id(t+1id(t)+ 1r1d,i

(t)Pid(t) Xd

i(t)+ 2r2d ,i(t)Pgd(t) Xd

i(t).(4)Thereexistmanyfactorsthatwouldin uencethe

convergencepropertyandperformanceofPSOalgo-rithm,includingselectionofω,c1andc2,velocityclamping,positionclamping,topologyofneighbor-hood,etc.Thisletterfocusesonanalyzingtherela-tionshipbetweenconvergencepropertyofthestandardPSOalgorithmandtheparameterrangeofω,c1andc2.Factorssuchasvelocityclamping,positionclamping,topologyofneighborhooddomayin uencetheconver-gencepropertyandperformanceofthestandardPSOalgorithm,butthediscussionofthosefactorsisbeyondthescopeofthisletter.Atthesametime,thesituationwithvariableparametervaluesduringevolutionisalsonotdiscussedhere.Thatmeans,thestandardPSOalgo-rithmstudiedhereisonlydeterminedby xedparame-tertuple{ω,c1,c2}.Velocityandpositionclampingare

粒子群优化

10M.Jiangetal./InformationProcessingLetters102(2007)8–16

notconsidered,andstartopologyisinvestigated,i.e.,theneighborhoodofanyparticleisthewholeswarm.2.2.One-dimensionalalgorithm

Whentheparticleswarmoperatesontionproblem,thevaluesofP

anoptimiza-iandPgareconstantlyupdated,asthesystemevolvestowardanoptimum.

Foranalysis iandP

purpose,considerthesituationthatP

gkeepconstantduringaperiodoftime,thenallparticlesevolveindependently.Thus,onlyparti-cleineedstobestudied.Foriischosenarbitrarily,theresultcanbeappliedtoallotherparticles.Atthesametime,itappearsfromEqs.(2)and(3)thateachdimensionisupdatedindependentlyfromtheothers.Thus,withoutlossofgenerality,thealgorithmdescrip-tioncanbereducedtotheone-dimensionalcase.Byomittingparticleanddimensionnotations,andcon-sideringdiscretetimesituation,updateequationsbe-come:

Vt+1=ωVt+c1r1,t(Pi Xt)+c2r2,t(Pg Xt),(5)Xt+1=Xt+Vt+1.

(6)

Itshouldbenoticedthattheabovesimpli cationisonlyforanalysispurpose,theoriginalstandardalgorithmwillberecalledaftertheanalysisis nished.

Accordingto[8],bysubstitutingEq.(5)intoEq.(6),thefollowingnon-homogeneousrecurrencerelationisobtained:

Xt+1= 1+ω (c1r1,t+c2r2,t)

Xt

ωXt 1+c1r1,tPi+c2r2,tPg.

(7)

NoticethatthereexistrandomnumbersinEq.(7),andthatX0,X1arealsorandomnumbers,thuseachXtshouldberegardedasarandomvariable,andtheiter-ativeprocess{Xt}shouldberegardedasastochasticprocess.TheexpectationandvarianceofeachrandomvariableXtcanthenbecalculated,andtheconvergencepropertyoftheiterativeprocesscanbeanalyzed.3.Convergenceanalysis

Asstatedinlastsection,consideringtheone-particleone-dimensionalPSOalgorithmwith xedPiandPg,theparticle’spositionatiterationt,i.e.,Xtisarandomvariable,thusparticle’strajectorycanberegardedasastochasticprocess.Inthissection,particleposition’sexpectationandvariancewillbecalculated,whicharedeterministicprocessesratherthanstochasticprocesses,thusthecorrespondingguaranteedconvergenceproper-

tiescanbedirectlyanalyzed.TheanalysisisbasedonEq.(7)insteadofEqs.(5)and(6).Afterthat,theas-sumptionof xedPiisremoved,andtheconvergencepropertyofparticle’scognitionisanalyzed.Remem-berthatthoseanalysisarebasedonthesimpli edone-particleone-dimensionalPSOsystem.InSection3.4,theoriginalstandardM-particleD-dimensionalPSOsystemwillberecalled,andtheresultobtainedfromone-particleone-dimensionalPSOsystemcanbeap-pliedtoanalyzetheconvergentconditionofthestandardPSOsystem.

3.1.Convergenceanalysisoftheexpectationofparticle’sposition

Inthissubsection,theiterationequationofEXtisobtained,whereEXtistheexpectationofrandomvari-ableXt.Basedontheiterationequation,theconvergentconditionofsequence{EXt}isanalyzed.

AccordingtoEq.(7),iterationequationofsequence{EXt}canbeobtained.

EX+ω

ct+1=11+c2

2

EXt ωEXct 1+

1Pi+c2Pg

2.(8)Thecharacteristicequationoftheiterativeprocessshown

inEq.(8)is

λ2 1+ω c1+c2

2λ+ω=0.(9)

Theorem1.Givenω,c1,c2 0,ifandonlyif0 ω<1and0<c1+c2<4(1+ω),iterativeprocess{EXt}isguaranteedtoconvergeto(c1Pi+c2Pg)/(c1+c2).Proof.Theconvergentconditionofiterativeprocess{EXt}isthattheabsolutevalues(orcomplexmodulus)ofbotheigenvaluesλ1,λ2arelessthan1.Thatis,

1 c+c2 c1+c2 2 1+ω 12±1+ω 22 4ω <1.

Considertwocases.

(1)(1+ω c2

botheigenvalues)<4ω.

Here,|λ2|2=1(1+ω carecomplexnumbers.|λ1|2=

,|λ)2+1

[4ω (1+ω c2ω,somax{|λ)]=1|2|}<1requiresonlyω<1.tion(1)itselfrequires√ω>0and2(1+ω 2√Condi-<c1+c2<2(1+ω+2.

粒子群优化

M.Jiangetal./InformationProcessingLetters102(2007)8–16

11

(2)(1+ω c)2

4ω.

Here,botheigenvaluesarerealnumbers.Rememberthatω,c1,c2areallnon-negativerealnumbers,condi-tion(2)isequaltoω 0,2 2√andc1+c2 2(1+ω 2√

orc1+c. (12+(1ω++ω2Ifc1+c2 2√

,max{|λ1|,|λ2|}<1requiresonly

1

21+ω c1+c22+1+ω c 1+c222

4ω

<1.

Thus√itleadstoω<1and0<c1+c2 2(1+ω

2.Ifc1+c2 2(1+ω+2√

,max{|λ1|,|λ2|}<1requiresonly

1

c1+c2 21+ω 2 1+ω c1+c22

2 4ω

> 1.

Thusitleadstoω<1and2(1+ω+2√

c1+c2<4(1+ω).

Synthesizecases(1)and(2),theguaranteedconver-gentconditionofiterativeprocess{EXt}is0 ω<1and0<c1+c2<4(1+ω).

(10)

Wheniterativeprocess{EXt}isconvergent,thecon-vergentvalueEXcanbecalculatedω c)EX ωEX+cPusingEX=(1+

1i+c2Pg.ThatgetsEX=(c1Pi+c2Pg)/(c1+c2).2

Asamatteroffact,if0 ω<1andc1=c2=0,

thenXt=X0+ω(1 ωt)

notconsideredV0.Thatisnotaninterestingcase,andisconvergentinthisletter.Sim-ilarresultscanbefoundin[7–9],butnoneofthoseresultsexplicitlytakesparticle’spositionasastochasticvariable,sothoseresultsaresomewhatvagueincon-cept,andareasonableexplanationishardtobegiven.Fromaboveanalysis,itisnowclearwhatthoseresultsactuallymean.

3.2.Convergenceanalysisofthevarianceofparticle’sposition

Asweknow,asequenceofstochasticvariablesmaynotconvergeevenifcorrespondingexpectationsequenceconverges.Tofurtherstudytheconvergenceproperty,thevariancesequenceshouldbestudied.Inthissubsection,theiterationequationofDXtisob-tained,whereDXtisthevarianceofrandomvariableXt.Basedontheiterationequation,theconvergentcon-ditionofsequence{DXt}isanalyzed.InordertomaketheprocedureofcalculatingDXt

clear,somesymbolsshouldbeintroduced rstly.Letν=(c1+c2)/2,μ=(c1Pi+c2Pg)/(c1+c2),ψ=1+ω ν,Rt=c1r1,t+c2r2,t ν,Qt=((c1c2)/(c1+c2))(r2,t r1,t)(Pg Pi),andYt=Xt μ,thenfromEq.(7),itgets

Yt+1=(ψ Rt)Yt ωYt 1+Qt.

(11)

Obviously,Ytisalsoarandomvariable,andDYμ.Sincert=DXt,EYt=EXt 1,t,r2,taretwoinde-pendentuniformrandomnumbersrangedin[0,1]obviousthatERt=EQt=0,DRt=ERt2=1,it(c2is

1+c2E(R2t=EQ2t=1),DQ(c1c2

/(c1+c2))2(Pg Pi)2,andtQt)=(c1c2(c2 c1)/12(c1+c2))(Pg Pi).No-ticethatDRt,DQtandE(RtQt)areconstants,letR=DRt,Q=DQt,andT=E(RtQt).

NoticethatYt,Yt 1arebothindependentonRt,QbutYtandYt 1aredependent.ThusEY2t,

asfollows:

t2+1,EYt+2,and

E(Yt+1Yt)canbecalculatedEYt2+1=(ψ2+R)EYt2+ω2EYt2

1+Q

2ωψE(YtYt 1) 2TEYt,

(12)EYt2+2=(ψ2+R)EYt2+1+ω2EYt2

+Q

2ωψE(Yt+1Yt) 2TEYt+1,

(13)E(Yt+1Yt)=ψEYt2 ωE(YtYt 1).

(14)

Then,(12) ω+(13)iscalculatedtoeliminateitemsE(Yt+1Yt)andE(YtYt 1),get

EYt2+2+ωEYt2

+1

=(ψ2+R) EYt2+1

+ωEYt2

+ω2 EY t2+ωEYt2 1

+Q(1+ω) 2ωψ2EYt2 2T(EYt+1+ωEYt).

(15)SubstituteDYt=EYt2 (EYt)2,EYt+2=ψEYt+1 ωEYt,andωEYt 1=ψEYt EYt+1intoEq.(15),theiterationequationofDYtisobtained.

DYt+2=(ψ2+R ω)DYt++ω3DYt 1+R 1 ω(ψ2 R ω)DY(EYt+1)2+ω(EYt)2

t

2T(EYt+1+ωEYt)+Q(1+ω).

(16)

RememberthatDYt=DXt,EYt=EXt μ,theiter-ationequationofDXtcanbeobtained.DXt+2=(ψ2+R ω)DXt+1

ω(ψ2 R ω)DXt+ω3DXt 1

+R

(EXt+1 μ)2+ω(EXt μ)2

2T

EXt+1 μ+ω(EXt μ) +Q(1+ω).

(17)

粒子群优化

12M.Jiangetal./InformationProcessingLetters102(2007)8–16

ThecharacteristicequationoftheiterativeprocessshowninEq.(17)is

λ3 (ψ2+R ω)λ2+ω(ψ2 R ω)λ ω3=0.

(18)Theiterationequationandcharacteristicequationofit-erativeprocess{DXt}arebothquitecomplex,anditishardtoanalyzethesetwoequationsdirectly.Fortu-nately,theconvergentconditionoftheiterativeprocess{DXt}de nedinEq.(17)iscomparativelysimple.Beforediscussingconvergencepropertyofiterativeprocess{DXt},anauxiliarytheoremisintroduced.Letf(λ)=λ3 (ψ2+R ω)λ2+ω(ψ2 R ω)λ ω3,andλ1,λ2,λ3arethreerootsofthecharacteristicequa-tion(18).

Theorem2.Given0 ω<1andc1+c2>0,thenf(1)>0isthenecessaryandsuf cientconditionofmax{|λ1|,|λ2|,|λ3|}<1.

Proof.Ifω=0,thentwoamongthreeeigenvaluesarezeros.Withoutlossofgenerality,letλcan1isbeequaleasily2=tofobtainedλ3=0,thenλ1=ψ2+R>0.Italso(1)>0.thatf(1)=1 λ1.Thus|λ1|<Consideranotherspecialcase.Ifψ=0,i.e.,c(1+ω),thenωλ1+c2=212== ωandλ2,λ1√0,0.itObviously,3arerootsofequationλ2 Rλ getsmax|{|λλ1|=ω<1.SinceR>0andω2 2|,|λ3|}=(R+√.Thus,theconvergentconditionis1(R+)<1.Thisleadsto1 R ω2>0.Atthispoint,f(1)=(1 R ω2)(1+ω).Obvi-ously,1 R ω2>0andf(1)>0areequal,somax{|λ2|,|λ3|}<1isequaltof(1)>0.

Nowconsidergeneralsituationswhen0<ω<1,c1+c2>0andc1+c2=2(1+ω).Inordertogoonwiththeproof,somefunctionvaluesshouldbeevalu-ated rstly.f(0)= ω3<0;

f(ω)= 2ω2R<0;

f( ω)= 2ψ2ω2<0.

Basedonpropertyofcubicequationwithoneunknown,itisknownthatλ1λ2λ3=ω3>0.Thismeansthatthecharacteristicequation(18)hasthreepositiveroots,oronepositiverootandtwonegativeroots.

Toprovethenecessity,reductiontoabsurdityisadopted.f(1)shouldnotequaltozero,otherwise1istheeigenvalue,violatingconditionmax{|λ1|,|λ2|,|λ3|}<1.Thenassumef(1)<0.Accordingtoconclusionsinelementarymathematics,becausef( ω),f(0),f(ω)andf(1)havethesamesign,thenumberofrootsintheinterval( ω,0),(0,ω),and(ω,1)mustallbeeven.

Thustheremustbeatleastonerootlocatedininterval(1,∞)tosatisfyλ1λ<2λ1.

3=ω3>0,violatingconditionmax{|λ1|,|λ2|,|λ3|}Nowthesuf ciency.Sincef(1)>0andf(ω)<0,sothenumberofthecharacteristicequation’srootsintheinterval(ω,1)shouldbeodd.Thenumberofrootsintheinterval(ω,1)couldnotbe3,forthiswillcauseλ1λ2λ3>ω3,sothenumbercouldonlybe1.Withoutlossofgenerality,lettherootbeλ1.Becausef( ω),f(0)andf(ω)havethesamesign,thenum-berofrootsintheinterval( ω,0),(0,ω)mustallbeeven.Thus,theothertworootsλ2,λ3canbothbelo-catedintheinterval( ω,0)or(0,ω);orbelocatedininterval( ∞, ω)or(1,∞).Obviously,λ2,λ3can-notbelocatedininterval( ∞, ω)or(1,∞),forthatcause|λ1λ2λ3|>ω3.Thus,λ2,λ3canonlybelocatedintheinterval( ω,0)or(0,ω).Apparently,max{|λ1|,|λ2|,|λ3|}<1issatis ed.2

Nowtheparameterrangetoguaranteethecon-vergenceofsequence{DXt}canbecalculatedusingf(1)>0,where

f(1)= (c1+c2)ω2

+

1 2126c1+6c2+12c1c2ω+c1+c2 13c211 3c21

2 2

c1c2.

LetA=c1+c2,B= (1c21+1c22+1c1c2),C=1c21+

1c22+1

c1c2 c1 c2.Knowingthatf(1)>0andωisarealnumber,itiseasytogetthatbothAω20shouldbesatis ed.That+Bωis,

+C<0andB2 4AC g(c1,c2)=(c1+c2)4 48(c1+c2)3

+2(c1c2+72)(c1+c2)2

+24c1c2(c1+c2)+c21c2

2

0,(19)

c21+c22

+3c1c2 √1212(c12)

<ω<

c21+c22

+3c1c2+√1212(c.(20)

12)

Asamatteroffact,Eqs.(19)and(20)impliesthatc1+c2<4(1+ω);or,inotherwords,f(1)>0impliesthatc1+c2<4(1+ω).Thisisbecause

g(c1,c2)<g(c1,c2)+2+c2)= 3(c1+c2)2(c12

2(c+c12(c 12)2 1+c2) c1c2 and2(c1+c2)2 12(c1+c2) c1c2<0holdsintheparameterrangedeterminedbyEq.(19).Thus,

粒子群优化

M.Jiangetal./InformationProcessingLetters102(2007)8–1613

c21+c22

+3c1c2 √1212(c12)

2>

c1+c22+3c1c2+2(c1+c2)2 12(c1+c2) c1c212(c12)

=1

4

(c1+c2) 1and(c2+c2+3cc √12(c+c)implies112121<ωthat2

2c1+c2<4(1+ω).

Theorem3.Givenω,c+c1,c2 0,ifandonlyif0 ω<1,c12>0andf(1)>0areallsatis edto-gether,iterative1process{DXt}isguaranteedtovergeto(c1c2/(c1+c2))2(Pg Pi)2con-(1+ω)/f(1),

wheref(1)= (c1+c2)ω2+(1c21+1c22+1c1c2)ω+

c1+c2 1c21 1c22 1c1c2.Proof.TheiterationequationofDXt,Eq.(17),con-tainsitemsrelatedtoEXt,thustheconditionshownin

Theorem1shouldbesatis ed rstlytomakeDXtcon-vergent.Asstatedabove,f(1)>0impliesthatc1+c2<4(1+ω).Thusconditions0 ω<1,c1+c2>0,andf(1)>0togethermakesurethattheconditionsstatedinTheorem1aresatis ed.

AfterEXtisconvergent,theconvergentconditionofiterativeprocess{DXt}isthattheabsolutevalues(orcomplexmodulus)ofthethreeeigenvaluesλ1,λ2,λ3arealllessthan1.Theorem2provesthat,given0 ω<1andc1+c2>0,f(1)>0isthenecessaryandsuf cientconditionofmax{|λ+c1|,|λ2|,|λ3|}<1.

Thus,0 ω<1,c12>0,andf(1)>0togethergivethenecessaryandsuf cientconditiontoguaranteeiterativeprocess{DX{DXt}convergent.Ifiterativeprocesst}isconvergent,theconvergentvaluecanbecal-culatedusing

DX=(ψ2+R ω)DX ω(ψ2 R ω)DX

+ω3

DX+Q(1+ω)

+R

(EX μ)2+ω(EX μ)2

2T EX μ+ω(EX μ) .

ThatgetsDX=1(c1c2/(c1+c2))2(Pg Pi)2(1+

ω)/f(1).2

3.3.Convergenceanalysisofparticle’scognitionInandP

aboveanalysis,itissupposedthatthevaluesofP

igkeepconstant,whichisnotthecaselemsolving.Here,theassumptionthatP

inrealprob-ikeepscon-stantP

isremoved.Thatis,duringtheevolutionprocess,iisconstantlyupdatedaccordingtoEq.(1).ButthevalueofP

gisstillsupposedtokeepconstantandbethebestpositionfoundsofar.Asamatteroffact,thisas-sumptionisreasonable,becausethevalueofP

gonlyin uencesthe nalconvergentposition,anditdoesnotin uencetheconvergencepropertyatall.

Herewestillfocusontheone-dimensionalone-par-ticlesimpli edPSOsystem.TherelationshipbetweenPiandPgisgiveninthefollowingtheorem.

Theorem4.Givenω,c1,c2 0,ifiterativeprocess{DXt}isguaranteedtoconvergeandf(1)<c2(1+ω)

theniterativeprocess{P,i(t)}willconvergetoPgwithprobability1.

Proof.Iftheiterativeprocess{DXt}isguaranteedtoconverge,theniterativeprocess{EXt}isalsoguaran-teedtoconverge.SoXtwillconvergetoarandomdistri-butionwithexpectationEX=(c1Pi+c2Pg)/(c1+c2)

andvarianceDX=1.Nomatter(c1c2/(c1+c2))2(Pg Pi)2(1+

ω)/f(1)whatthevalueofPiis,iff(1)<c2(1+ω),then(Pg EX)2=(c1/(c1+c2))2(Pg Pi)2

<DX.HenceitisobviousthatProb(Xt=Pg)>0,whichdirectlyleadstoProb(limt→∞Pi(t)=Pg)=1duetotheupdateequationofPi.AndifPi(t)=Pg,itwillbestablethere.Thusitisevidentthatitera-tiveprocess{Pi(t)}willconvergetoPgwithprobabil-ity1.2

Itshouldbenoticedthattheconditionf(1)<

c2(1+ω)isonlyasuf cientconditiontoensurethecon-vergence,butnotanecessaryone.Asamatteroffact,

thisconditionistoberelaxedinfuture.

3.4.Convergenceanalysisofstandardparticleswarmsystem

Theaboveanalysisinthissectionareallbasedontheone-particleone-dimensionalsimpli edPSOsystem.Here,theoriginalstandardM-particleD-dimensionalstochasticPSOsystemisrecalled.

Whentheparticleswarmoperatesproblem,thevalueofP

iandP onanoptimization

gareconstantlyupdated,asthesystemevolvestowardanseefromaboveanalysis,whenP

optimum.Aswecan

tainconditions,P

gis xed,undercer-iwillevolvetowardP g.AndifP changes,P

giwillevolvetothenewP g.RegardingtheconvergencepropertyofthestandardPSOsystem,The-orem5canbeobtained.

Theorem5.Givenω,c1,c2 0,if0 ω<1,c1+c2>0,and0<f(1)<

c2(1+ω)areallsatis edto-

粒子群优化

14M.Jiangetal./InformationProcessingLetters102(2007)8–16

gether,thestandardparticleswarmsystemdeterminedbyparametertuple{ω,c1,c2}willsquaretoP

convergeinmean

g.Proof.Fromtheω,c1,c2 0,ifP

resultsofTheorems1and3,given

iandP gkeepconstantduringape-riodoftime,thenif0 ω<1,c1+c2>0,andf(1)>0areallsatis edtogether,foreachdimension

dofparticlei,theconclusionisthat{EXd(t)}con-vergesto(c1Pid+c2Pd)/(c+c),and{DXi

d(t)}con-vergesto1g12(c1c2/(c1+c2))2(Pgd Pid)2i

(1+ω)/f(1).

ItappearsfromEqs.(2)and(3)thateachdimensionofparticleiisupdatedindependentlyThus,itcanbeconcludedthat{E fromtheothers.

i(t)}convergesto(c1P

X

i+c2P g)/(c1+c2),and{DX 1i(t)}convergesto(c1c2/(c1+c2))2(P g P i)2

(1+ω)/f(1).Andfrom

theresultofTheorem4,iff(1)<c2

(1+ω),eachP

iconvergestoP

gwithprobabilitydiatelyP

obtained that{EX

1,thusitcanbeimme-i(t)}will nallyconvergetog,and{DXi(t)}will nallyconvergeto0.Thatmeans,eachP

sequence{X

i(t)}willstochasticallyevolvetowardguntilitconvergesinmeansquaretoP g.Thiscon-clusionappliestoeachparticle,thusthewholeparticle

swarmsystemwillconvergetoP

g.2ItshouldbenoticedthatTheorem5onlydeclaresthateachparticleinthestandardparticleswarmwouldconvergeinmeansquarefarbytheswarm,i.e.,P

tothebestpositionfoundso

g.Itdoesnotmeanthatthecon-vergentpositionisanoptimalone,orevenalocalopti-malone.Ifalocaloptimalpositionisdesired,theideafromGuaranteedLocallyConvergenceParticleSwarmOptimiser(GCPSO)proposedinvandenBergh[8]canbeadopted,whichwouldnotin uencetheanalysisre-sultsderivedinthisletter.4.Parameterselectionguidelines

Theconvergenceanalysisoftheexpectationandvarianceofparticle’sposition,andconvergenceanaly-sisofparticle’scognitioninSection3leadtosomelimitationontherelationshipamongtheparametertu-pleusedinstandardPSOalgorithm,thatis,0 ω<1,c1+c2>0,and0<f(1)<c2(1+ω)

beusedtoeffectivelyguide.Theseconditionscantheparameterselec-tionofPSOalgorithm.Althoughthisparameterareaisquiterestricted,thesuggestedandwidelyusedpa-rametersinliteraturesallfallintothisarea,suchasω=0.729,c=c1=2.8 ω,c2==01..6,3 cω[1],ω=0.729,c12=1.49[2],andω1=c2=1.7

[7].

Fig.1.Parameterrangetoguaranteetheconvergenceofiterative

process{EXt}.Thecyan(light)areacorrespondstocasewithcom-plexeigenvalues,theblue(dark)areacorrespondstocasewithrealeigenvalues.(Forinterpretationofthereferencestocolorinthis g-urelegend,thereaderisreferredtothewebversionofthis

article.)

Fig.2.Relationshipbetweenc1andc2toguaranteetheconvergenceofiterativeprocess{DXt}.

Maybetheanalysisresultpresentedinthisworkcanhelptoexplainwhythoseparametersworkwell.

Thecorrespondinggraphicalillustrationsofparame-terrangesaregivenasfollowsinthissection.

Theparameterrangetoguaranteetheconvergenceofiterativeprocess{EXt}isillustratedinFig.1.Thecyan(light)areainFig.1correspondstocase(1)discussedinTheorem1,andtheblue(dark)areainFig.1corre-spondstocase(2)discussedinTheorem1.

Theparameterrangestoguaranteetheconvergenceofiterativeprocess{DXt}areillustratedinFigs.2–4.InFig.2,therelationshipbetweenc1andc2,whichisdeterminedbyEq.(19),isillustrated.Therelationshipbetweenlowerandhigherrangeofωandc1,c2,whichisdeterminedbyEq.(20)andω 0,areillustratedinFigs.3and4,separately.

粒子群优化

M.Jiangetal./InformationProcessingLetters102(2007)8–16

15

Fig.3.Relationshipbetweenlowerrangeofωandc1,c2toguaranteetheconvergenceofiterativeprocess{DXt}

.

Fig.4.Relationshipbetweenhigherrangeofωandc}.

1,c2toguaranteetheconvergenceofiterativeprocess{DXtBecausetheconditionf(1)<c2(1+ω)

condition,therelationshipamongisonlyasuf -cientparametertuple{ω,c1,c2}determinedbythisconditionisnotillus-trated.

IfweusePSEtodenotetheparametersettoguaran-teetheconvergenceofiterativeprocess{EXt},usePSDtodenotetheparametersettoguaranteetheconvergenceofiterativeprocess{DXt},andusePSCtodenotetheparametersettosatisfy0<f(1)<c2(1+ω),thenitisobviousthattherelationshipshouldbePSE PSD PSC.IfweusePSStodenotetheparametersettoen-suretheconvergenceofiterativeprocess{Pi(t)},itisobviousthattherelationshipshouldbePSD PSSandPSS PSC.

TheparameterselectionofPSOalgorithminlitera-turesfavorsc1=c2=c,somoredetaileddiscussiononthisconditionisgiven.Atthistime,Eq.(10)becomes0 ω<1and0<c<2(1+ω).(21)

Andf(1)>0

becomes

Fig.5.Relationshipbetweenωandcwhenc1=c2=ctosimultane-ouslyguaranteetheconvergenceofiterativeprocesses{EXt},{DXt},and{Pi(t)}.Theblack(dark)areashowstheconvergenceconditionofprocess{EXt}.Thecyan(light)areashowstheconvergencecondi-tionofprocess{DXt}.Andtheblue(grey)areashowsaconvergenceconditionofprocess{Pi(t)}andthetotalparticleswarm.(Forinter-pretationofthereferencestocolorinthis gurelegend,thereaderisreferredtothewebversionofthisarticle.)

5c

√

24<ω<

5c+√

24

.(22)Thesyntheticconvergenceconditionsaresimultane-ouslyillustratedinFig.5.Therelationshipbetweenωandc,whichisdeterminedbyEq.(21),isillustratedintheblack(dark)areainFig.5.Therelationshipbe-tweenωandc,whichisdeterminedbyEq.(22)andω 0,isillustratedinthecyan(light)areainFig.5.Therelationshipbetweenωandc,whichisdeterminedby0<f(1)<c2(1+ω)

Fig.5.Obviously,,isillustratedintheblue(grey)areaintheconvergenceconditionofiterativeprocess{DXt}ismuchstrongerthantheconvergenceconditionofiterativeprocess{EXt},andtheconvergenceconditionofparticle’scognitionisthestrongest.5.Conclusions

Thestochasticprocesstheoryisappliedtoanalyzethestandardparticleswarmoptimizationalgorithmde-terminedbyparametertuple{ω,c1,c2},consideringtherandomnessthoroughly.Theanalysisresultsleadtoaconvergentconditionforthestandardparticleswarmsystem,andthecorrespondingparameterranges,bothinformularandgraphicalform,aregiven.ThisresultishelpfultounderstandthemechanismofstandardPSOalgorithmandselectappropriateparameterstomakePSOalgorithmmorepowerful.

粒子群优化

16M.Jiangetal./InformationProcessingLetters102(2007)8–16

Theresultderivedinthisletterdeclaresthatthestan-dardparticleswarmsystemcanconvergeinasenseofprobability,butonlyasuf cientconditionensuringtheconvergenceisgiven,andthedetailedconvergentpro-cedureisstillnotquiteclearnow.

Somemorefactorsin uencingtheconvergenceofparticleswarmsystemareneededtobeconsideredinfuture.FurtherresearchisalsoneededtoclarifytherelationshipbetweenPSOperformanceandparameterselectiontoguaranteeconvergence.References

[1]A.Carlisle,G.Dozier,Anoff-the-shelfPSO,in:Proceedings

oftheWorkshoponParticleSwarmOptimization,Indianapolis,USA,2001.

[2]M.Clerc,J.Kennedy,Theparticleswarm-explosion,stability,and

convergenceinamultidimensionalcomplexspace,IEEETransac-tionsonEvolutionaryComputation6(1)(2002)58–73.

[3]J.Kennedy,R.C.Eberhart,Particleswarmoptimization,in:Proc.

IEEEInternationalConferenceonNeuralNetworks,Piscataway,NJ,1995,pp.1942–1948.

[4]E.Ozcan,C.K.Mohan,Analysisofasimpleparticleswarmop-timizationsystem,in:IntelligentEngineeringSystemsthroughArti cialNeuralNetworks,1998,pp.253–258.

[5]E.Ozcan,C.K.Mohan,Particleswarmoptimization:sur ngthe

waves,in:Proc.IEEECongressonEvolutionaryComputation(CEC1999),Washington,DC,USA,1999,pp.1939–1944.

[6]Y.Shi,R.C.Eberhart,Amodi edparticleswarmoptimizer,in:

ProceedingsoftheIEEECongressonEvolutionaryComputation(CEC1998),Piscataway,NJ,1998,pp.69–73.

[7]I.C.Trelea,Theparticleswarmoptimizationalgorithm:Conver-genceanalysisandparameterselection,InformationProcessingLetters85(2003)317–325.

[8]F.vandenBergh,Ananalysisofparticleswarmoptimizers,PhD

Dissertation,UniversityofPretoria,Nov.2001.

[9]K.Yasuda,A.Ide,N.Iwasaki,Adaptiveparticleswarmoptimiza-tion,in:ProceedingsoftheIEEEInternationalConferenceonSystems,Man,andCybernetics,2003,pp.1554–1559.

本文来源：https://www.bwwdw.com/article/ees1.html