Recent approaches to global optimization problems

NaturalComputing1:235–306,2002.©2002KluwerAcademicPublishers.PrintedintheNetherlands.RecentapproachestoglobaloptimizationproblemsthroughParticleSwarmOptimizationK.E.PARSOPOULOS1andM.N.VRAHATIS2DepartmentofMathematics,UniversityofPatrasArtificialIntelligenceResearchCenter(UPAIRC),UniversityofPatras,GR-26110Patras,Greece(1E-mail:[e-mail];2E-mail:[e-mail])Abstract.ThispaperpresentsanoverviewofourmostrecentresultsconcerningtheParticleSwarmOptimization(PSO)method.Techniquesforthealleviationoflocalminima,andfordetectingmultipleminimizersaredescribed.Moreover,resultsontheabilityofthePSOintacklingMultiobjective,Minimax,IntegerProgrammingand
1errors-in-variablesproblems,aswellasproblemsinnoisyandcontinuouslychangingenvironments,arereported.Finally,aCompositePSO,inwhichtheheuristicparametersofPSOarecontrolledbyaDifferentialEvolutionalgorithmduringtheoptimization,isdescribed,andresultsformanywell-knownandwidelyusedtestfunctionsaregiven.Keywords:DifferentialEvolution,EvolutionaryComputation,GlobalOptimization,IntegerProgramming,MatlabCodeImplementation,MinimaxProblems,MultiobjectiveOptimi-zation,NoisyProblems,ParticleSwarmOptimization,SwarmIntelligenceAbbreviations:ANN–ArtificialNeuralNetwork;BWA–Bang-BangWeightedAggre-gation;CWA–ConventionalWeightedAggregation;DE–DifferentialEvolution;DLS–DynamicLightScattering;DWA–DynamicWeightedAggregation;EA–EvolutionaryAlgorithms;EC–EvolutionaryComputation;ES–EvolutionStrategies;GA–GeneticAlgorithms;GO–GlobalOptimization;MO–MultiobjectiveOptimization;PSO–ParticleSwarmOptimization;SLS–StaticLightScattering;SPSO–“Stretched”PSO;VEGA–VectorEvaluatedGeneticAlgorithms;VEPSO–VectorEvaluatedPSOACMComputingClassification(1998):G.1.6,F.1.2,G.3–4,I.2.81.IntroductionInnumerousoptimizationproblemsencounteredindifferentareasofscientificinquiry,thesearchforasolutionisidentifiedwiththediscoveryoftheglobalminimizerofarealvaluedobjectivefunctionf:S→R,i.e.,findingapointx∗∈Ssuchthatf(x∗)
f(x),∀x∈S,(1)whereS⊂RDisanonemptycompactset.236K.E.PARSOPOULOSANDM.N.VRAHATISGlobalOptimization(GO)methodscanbeclassifiedintotwomaincategories:deterministicandprobabilisticmethods.Mostofthedeterministicmethodsinvolvetheapplicationofheuristics,suchasmodifyingthetrajectory(trajectorymethods)oraddingpenalties(penalty-basedmethods),toescapefromlocalminima.Ontheotherhand,probabilisticmethodsrelyonproba-bilisticjudgementstodeterminewhetherornotsearchshoulddepartfromtheneighborhoodofalocalminimum(Forgó,1988;Hansen,1992;HorstandPardalos,1995;HorstandTuy,1996;Pintér,1996;Rao,1996;Schwefel,1995;TörnandŽilinskas,1989).Incontrastwithdifferentadaptivestochasticsearchalgorithms,Evolu-tionaryComputation(EC)techniques(Bäcketal.,1997)exploitasetofpotentialsolutions,namedpopulation,anddetecttheoptimalproblemsolutionthroughcooperationandcompetitionamongtheindividualsofthepopulation.Thesetechniquesoftenfindoptimaincomplicatedoptimi-zationproblemsfasterthantraditionaloptimizationmethods.Themostcommonlymetpopulation-basedECtechniques,suchasEvolutionStrategies(ES)(Bäck,1996;Beyer,2001;BeyerandSchwefel,2002;Rechenberg,1994;Rudolph,1997;Schwefel1975;Schwefel,1981;Schwefel,1995;SchwefelandRudolph,1995),GeneticAlgorithms(GA)(Goldberg,1989;Michalewicz,1994),GeneticProgramming(Banzhafetal.,1998;Koza,1992),EvolutionaryProgramming(Fogel,1996)andArtificialLifemethods,areinspiredfromtheevolutionofnature.TheParticleSwarmOptimization(PSO)methodisamemberofthewidecategoryofSwarmIntelligencemethods(KennedyandEberhart,2001),forsolvingGOproblems.ItwasoriginallyproposedbyJ.Kennedyasasimu-lationofsocialbehavior,anditwasinitiallyintroducedasanoptimizationmethodin1995(EberhartandKennedy,1995;KennedyandEberhart,1995).PSOisrelatedwithArtificialLife,andspecificallytoswarmingtheories,andalsowithEC,especiallyESandGA.PSOcanbeeasilyimplementedanditiscomputationallyinexpensive,sinceitsmemoryandCPUspeedrequirementsarelow(Eberhartetal.,1996).Moreover,itdoesnotrequiregradientinformationoftheobjectivefunctionunderconsideration,butonlyitsvalues,anditusesonlyprimitivemathematicaloperators.PSOhasbeenprovedtobeanefficientmethodformanyGOproblemsandinsomecasesitdoesnotsufferthedifficultiesencounteredbyotherECtechniques(EberhartandKennedy,1995).Inthispaper,somerecentapproachesforsolvingGOproblemsthroughPSOarepresented.AfterananalyticdescriptionoftheconceptsbehindPSOanditshistoricalbackgroundinSection2,arecentlyproposedtechnique,calledFunction“Stretching”,isdescribedinSection3.IncorporatingFunc-tion“Stretching”inPSO,themethodbecomescapableofalleviatinglocalRECENTAPPROACHESTOGLOBALOPTIMIZATIONPROBLEMS237minimaoftheobjectivefunction,thusincreasingsignificantlyitssuccessrates.InSection4,PSOistestedinnoisyandcontinuouslychangingenvir-onments,wherethefunctionvaluesareimpreciseandtheglobalminimizermoveswithinthesearchspace.Inthiscontext,anapplicationofPSOforsolvingLightScatteringproblems,ispresented.ThePSO’sabilitytocopeefficientlywithMultiobjectiveOptimizationproblemsisinvestigatedinSection5.InSection6,PSOisusedtosolve
1normerrors-in-variablesprob-lems,determiningthebe