Particle swarm optimization

SwarmIntell(2007)1:33–57DOI10.1007/s11721-007-0002-0ParticleswarmoptimizationAnoverviewRiccardoPoli·JamesKennedy·TimBlackwellReceived:19December2006/Accepted:10May2007/Publishedonline:1August2007©SpringerScience+BusinessMedia,LLC2007AbstractParticleswarmoptimization(PSO)hasundergonemanychangessinceitsintro-ductionin1995.Asresearchershavelearnedaboutthetechnique,theyhavederivednewversions,developednewapplications,andpublishedtheoreticalstudiesoftheeffectsofthevariousparametersandaspectsofthealgorithm.Thispapercomprisesasnapshotofparticleswarmingfromtheauthors’perspective,includingvariationsinthealgorithm,currentandongoingresearch,applicationsandopenproblems.KeywordsParticleswarms·Particleswarmoptimization·PSO·Socialnetworks·Swarmtheory·Swarmdynamics·Realworldapplications1IntroductionTheparticleswarmparadigm,thatwasonlyafewyearsagoacuriosity,hasnowattractedtheinterestofresearchersaroundtheglobe.Thisarticleisintendedtogiveanoverviewofimportantworkthatgavedirectionandimpetustoresearchinparticleswarmsaswellassomeinterestingnewdirectionsandapplications.Thingschangefastinthisfieldasinves-tigatorsdiscovernewwaystodothings,andnewthingstodowithparticleswarms.Itisimpossibletocoverallaspectsofthisareawithinthestrictpagelimitsofthisjournalarticle.Thusthispapershouldbeseenasasnapshotoftheviewwe,theseparticularauthors,haveatthetimeofwriting.R.Poli()DepartmentofComputingandElectronicSystems,UniversityofEssex,Essex,UKe-mail:[e-mail],DC,USAe-mail:[e-mail]puting,GoldsmithsCollege,London,UKe-mail:[e-mail]34SwarmIntell(2007)1:33–57Thearticleisorganizedasfollows.InSect.2,weexplainwhatparticleswarmsareandwelookattherulesthatcontroltheirdynamics.InSect.3,weconsiderhowdifferenttypesofsocialnetworksinfluencethebehaviorofswarms.InSect.4,wereviewsomeinterestingvariantsofparticleswarmoptimization.InSect.5,wesummarizethemainresultsofthe-oreticalanalysesoftheparticleswarmoptimizers.Section6looksatareaswhereparticleswarmshavebeensuccessfullyapplied.OpenproblemsinparticleswarmoptimizationarelistedanddiscussedinSect.7.WedrawsomeconclusionsinSect.8.2Populationdynamics2.1TheoriginalversionTheinitialideasonparticleswarmsofKennedy(asocialpsychologist)andEberhart(anelectricalengineer)wereessentiallyaimedatproducingcomputationalintelligencebyexploitingsimpleanaloguesofsocialinteraction,ratherthanpurelyindividualcog-nitiveabilities.Thefirstsimulations(KennedyandEberhart1995)wereinfluencedbyHeppnerandGrenander’swork(HeppnerandGrenander1990)andinvolvedanaloguesofbirdflockssearchingforcorn.Thesesoondeveloped(KennedyandEberhart1995;EberhartandKennedy1995;Eberhartetal.1996)intoapowerfuloptimizationmethod—ParticleSwarmOptimization(PSO).1InPSOanumberofsimpleentities—theparticles—areplacedinthesearchspaceofsomeproblemorfunction,andeachevaluatestheobjectivefunctionatitscurrentlocation.2Eachparticlethendeterminesitsmovementthroughthesearchspacebycombiningsomeaspectofthehistoryofitsowncurrentandbest(best-fitness)locationswiththoseofoneormoremembersoftheswarm,withsomerandomperturbations.Thenextiterationtakesplaceafterallparticleshavebeenmoved.Eventuallytheswarmasawhole,likeaflockofbirdscollectivelyforagingforfood,islikelytomoveclosetoanoptimumofthefitnessfunction.EachindividualintheparticleswarmiscomposedofthreeD-dimensionalvectors,whereDisthedimensionalityofthesearchspace.Thesearethecurrentpositionxi,thepreviousbestpositionpi,andthevelocityvi.Thecurrentpositionxicanbeconsideredasasetofcoordinatesdescribingapointinspace.Oneachiterationofthealgorithm,thecurrentpositionisevaluatedasaproblemsolution.Ifthatpositionisbetterthananythathasbeenfoundsofar,thenthecoordinatesarestoredinthesecondvector,pi.Thevalueofthebestfunctionresultsofarisstoredinavariablethatcanbecalledpbesti(for“previousbest”),forcomparisononlateriterations.Theobjective,ofcourse,istokeepfindingbetterpositionsandupdatingpiandpbesti.Newpointsarechosenbyaddingvicoordinatestoxi,andthealgorithmoperatesbyadjustingvi,whichcaneffectivelybeseenasastepsize.Theparticleswarmismorethanjustacollectionofparticles.Aparticlebyitselfhasalmostnopowertosolveanyproblem;progressoccursonlywhentheparticlesinteract.1Followingstandardpractice,inthispaperweusetheacronym“PSO”alsoforParticleSwarmOptimizer.Thereisnoambiguitysinceinthissecondinterpretation“PSO”isalwaysprecededbyadeterminer(e.g.,“a”or“the”)orisusedinthepluralform“PSOs”.2InPSOtheobjectivefunctionisoftenminimizedandtheexplorationofthesearchspaceisnotthroughevolution.However,followingawidespreadpracticeofborrowingfromtheevolutionarycomputationfield,inthisarticleweusethetermsobjectivefunctionandfitnessfunctioninterchangeably.SwarmIntell(2007)1:33–5735Problemsolvingisapopulation-widephenomenon,emergingfromtheindividualbehaviorsoftheparticlesthroughtheirinteractions.Inanycase,populationsareorganizedaccordingtosomesortofcommunicationstructureortopology,oftenthoughtofasasocialnetwork.Thetopologytypicallyconsistsofbidirectionaledgesconnectingpairsofparticles,sothatifjisini’sneighborhood,iisals