搜索
Multi-ObjectiveParticleSwarmOptimizers:ASurveyoftheState-of-the-ArtMargaritaReyes-SierraandCarlosA.CoelloCoelloCINVESTAV-IPN(EvolutionaryComputationGroup)ElectricalEngineeringDepartment,ComputerScienceSectionAv.IPNNo.2508,Col.SanPedroZacatencoM´exicoD.F.07300,M´EXICOmreyes@computacion.cs.cinvestav.mxccoello@cs.cinvestav.mxAbstract-ThesuccessoftheParticleSwarmOptimiza-tion(PSO)algorithmasasingle-objectiveoptimizer(mainlywhendealingwithcontinuoussearchspaces)hasmotivatedresearcherstoextendtheuseofthisbio-inspiredtechniquetootherareas.Oneofthemismulti-objectiveoptimization.DespitethefactthatthefirstproposalofaMulti-ObjectiveParticleSwarmOptimizer(MOPSO)isoversixyearsold,aconsiderablenum-berofotheralgorithmshavebeenproposedsincethen.Thispaperpresentsacomprehensivereviewofthevar-iousMOPSOsreportedinthespecializedliterature.Aspartofthisreview,weincludeaclassificationoftheap-proaches,andweidentifythemainfeaturesofeachpro-posal.Inthelastpartofthepaper,welistsomeofthetopicswithinthisfieldthatweconsideraspromisingar-easoffutureresearch.1IntroductionOptimizationproblemsthathavemorethatoneobjectivefunctionarerathercommonineveryfieldorareaofknowl-edge.Insuchproblems,theobjectivestobeoptimizedarenormallyinconflictwithrespecttoeachother,whichmeansthatthereisnosinglesolutionfortheseproblems.Instead,weaimtofindgood“trade-off”solutionsthatrepresentthebestpossiblecompromisesamongtheobjectives.ParticleSwarmOptimization(PSO)isaheuristicsearchtechnique(whichisconsideredasanevolutionaryalgorithmbyitsauthors[18])thatsimulatesthemovementsofaflockofbirdswhichaimtofindfood.TherelativesimplicityofPSOandthefactthatisapopulation-basedtechniquehavemadeitanaturalcandidatetobeextendedformulti-objectiveoptimization.MooreandChapmanproposedthefirstextensionofthePSOstrategyforsolvingmulti-objectiveproblemsinanunpublishedmanuscriptfrom19991[41].Afterthisearlyattempt,agreatinteresttoextendPSOaroseamongre-searchers,butinterestingly,thenextproposalwasnotpub-lisheduntil2002.Nevertheless,therearecurrentlyovertwentyfivedifferentproposalsofMOPSOsreportedinthespecializedliterature.Thispaperprovidesthefirstsurveyofthiswork,attemptingtoclassifytheseproposalsandtodelineatesomeofthepotentialresearchpathsthatcouldbefollowedinthefuturebyresearchersinthisarea.Theremainderofthispaperisorganizedasfollows.InSection2,weprovidesomebasicconceptsfrommulti-1ThispapermaybefoundintheEMOOrepositorylocatedat:˜ccoello/EMOO/objectiveoptimizationrequiredtomakethepaperself-contained.Section3presentsanintroductiontothePSOstrategyandSection4presentsabriefdiscussionaboutex-tendingthePSOstrategyforsolvingmulti-objectiveprob-lems.AcompletereviewoftheMOPSOapproachesispro-videdinSection5.WeprovideabriefdiscussionabouttheconvergencepropertiesofPSOandMOPSOinSection6.InSection7,possiblepathsoffutureresearcharediscussedand,finally,wepresentourconclusionsinSection8.2BasicConceptsWeareinterestedinsolvingproblemsofthetype2:minimize (1)subjectto: !$# % ’&( *)(2)+ , -!.#/ % ’&( 10(3)where 2 3 * 54 76isthevectorofdecisionvariables, 98:4;8:,#= % ? @ ? BAaretheobjectivefunctionsand +DC 58:4;8:,#E F% @ @ ? *),G H% ? @ @ 10aretheconstraintfunctionsoftheproblem.Todescribetheconceptofoptimalityinwhichweareinterested,wewillintroducenextafewdefinitions.Definition1.Giventwovectors I JLK 8: ,wesaythat M Jif J for#N O% @ @ ? BA,andthat dominates J(denotedby QP J)if R Jand TS J.Figure1showsaparticularcaseofthedominancerelationinthepresenceoftwoobjectivefunctions.Definition2.Wesaythatavectorofdecisionvari-ables TKTUWVX8:4isnondominatedwithrespecttoU,iftheredoesnotexistanother 5YZKQUsuchthat / 5Y7 [P .Definition3.Wesaythatavectorofdecisionvariables \]K_^HV‘8:4(^isthefeasibleregion)isPareto-optimalifitisnondominatedwithrespectto^.Definition4.TheParetoOptimalSeta\isdefinedby:a\ Lb QKc^Qd isPareto-optimale2Withoutlossofgenerality,wewillassumeonlyminimizationprob-lems.dominatedsolutionsff21Figure1:Dominancerelationinabi-objectivespace.dominatedsolutionsParetofrontsolutionsff21Figure2:TheParetofrontofasetofsolutionsinatwoobjectivespace.Definition5.TheParetoFronta^f\isdefinedby:a^\ gb [Kc8: d QKa\eFigure2showsaparticularcaseoftheParetofrontinthepresenceoftwoobjectivefunctions.WethuswishtodeterminetheParetooptimalsetfromtheset^ofallthedecisionvariablevectorsthatsatisfy(2)and(3).Notehoweverthatinpractice,notalltheParetooptimalsetisnormallydesirable(e.g.,itmaynotbedesir-abletohavedifferentsolutionsthatmaptothesamevaluesinobjectivefunctionspace)orachievable.3ParticleSwarmOptimizationJamesKennedyandRussellC.Eberhart[30]originallyproposedthePSOalgorithmforoptimization.PSOisapopulation-basedsearchalgorithmbasedonthesimulationofthesocialbehaviorofbirdswithinaflock.Althoughoriginallyadoptedforbalancingweightsinneuralnetworks[17],PSOsoonbecameaverypopularglobaloptimizer,mainlyinproblemsinwhichthedecisionvariablesarerealnumbers3[32,19].AccordingtoAngeline[3],we