Multi-Objective particle swarm optimizers A survey

Multi-ObjectiveParticleSwarmOptimizers:ASurveyoftheState-of-the-ArtMargaritaReyes-SierraandCarlosA.CoelloCoelloCINVESTAV-IPN(EvolutionaryComputationGroup)ElectricalEngineeringDepartment,ComputerScienceSectionAv.IPNNo.2508,Col.SanPedroZacatencoM´exicoD.F.07300,M´[e-mail]@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)where23*5476isthevectorofdecisionvariables,98:4;8:,#=%?@?BAaretheobjectivefunctionsand+DC58:4;8:,#EF%@@?*),GH%?@@10aretheconstraintfunctionsoftheproblem.Todescribetheconceptofoptimalityinwhichweareinterested,wewillintroducenextafewdefinitions.Definition1.GiventwovectorsIJLK8:,wesaythatMJifJfor#NO%@@?BA,andthatdominatesJ(denotedbyQPJ)ifRJandTSJ.Figure1showsaparticularcaseofthedominancerelationinthepresenceoftwoobjectivefunctions.Definition2.Wesaythatavectorofdecisionvari-ablesTKTUWVX8:4isnondominatedwithrespecttoU,iftheredoesnotexistanother5YZKQUsuchthat/5Y7[P.Definition3.Wesaythatavectorofdecisionvariables\]K_^HV‘8:4(^isthefeasibleregion)isPareto-optimalifitisnondominatedwithrespectto^.Definition4.TheParetoOptimalSeta\isdefinedby:a\LbQKc^QdisPareto-optimale2Withoutlossofgenerality,wewillassumeonlyminimizationprob-lems.dominatedsolutionsff21Figure1:Dominancerelationinabi-objectivespace.dominatedsolutionsParetofrontsolutionsff21Figure2:TheParetofrontofasetofsolutionsinatwoobjectivespace.Definition5.TheParetoFronta^f\isdefinedby:a^\gb[Kc8:dQKa\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