多目标遗传算法、NSGA、经典文章NSGA-2算法、pareto最优解集的进展研究

22320085Computer&DigitalEngineeringVol.36No.5163(430070),;,,;,;ParetoTP301.6IntroductionofResearchonMulti-ObjectiveEvolutionaryAlgorithmsQiWeixiLiBin(DepartmentofComputerScience,WuhanUniversityofTechnology,Wuhan430070)AbstractFirst,thispaperreviewstheoriginsofMOEAs,andgivesitscorrespondingmathematicaldescription.Next,itanalyzestheoriginalclassicalMOEAsandtheirachievementsandshortage.Lateron,thenewlydeveloped2ndgenerationsMOE2Asarediscussedwithdetails.Finally,somepromisingprospectsarepredicted.KeywordsMOEAs,multi-objectiveoptimization,paretonon-dominanceClassNumberTP301.611.1,[1],(Multi-objectiveOptimizationProblem,MOP)[2]MOP,,[3]MOP,Pareto,,,Pareto2050,-(EvolutionaryAlgo2rithms,EA)EAs,Pareto,[4]1.2,MOP,,MOPPareto,:Maximizey=f(x)=(f1(x),f2(x),...,fk(x))Subjecttoe(x)=(e1(x),e2(x),...,em(x))F0x=(x1,x2,...xn)X,y=(y1,y2,...yn)Y,x,y,nk21967,R.S.Rosenberg3:20071221,:2008114:,,,:,,,:MOP,,MOP,GASchaffer.D.J1985VEGAMOP,MOPVEGA,ParetoEA[5],2.1(Multi-ObjectiveGeneticAlgorithm,MOGA)1993,CarlosFonsecaPeterFlemming[6]MOGA,GAMOGA,,Pareto1:1),;2);3),,Fon2secaFlemming2.2Pareto(NichedParetoGenet2icAlgorithm,NPGA)HornNafpliotisGoldberg1994Pareto[7]NPGAPareto,NPGA,,(10%),,,;,,,Pareto,,;,2.3(Non-dominatedSortingGeneticAlgorithm,NSGA)SrimivasDeb1994EvolutionaryComputationNSGA[8],,,,,Pareto,,,,NSGA;MOGA,,Pareto2.4,,,,,32090,MOEA,MOP,MOEA,,EchartZitzlerMOEA,MOEA3.1SPEA(StrengthParetoEvolutionaryAlgo2rithm)SPEA2SPEAZitzlerThiele1998[9]SPEAMOEAsPareto,,,,,SPEA,Pareto,,7136(2008)5,,ParetoSPEA,;,[10],2001Zitzler,SPEA2SPEA2,:1),,;2),,k;3),,3.2NSGA2(Non-dominatedSortingGeneticAl2gorithm2)NSGA,,Deb2000,NSGA2[1112],,,NSGA2,;Pareto,,,,;,,,NSGA2,O(MN2)(M,N),NSGA3.3PAES(ParetoArchivedEvolutionStrategy)ParetoPAES,(1+1)Corne,DWKnowlesJD,OatesMJ2000ProceedingsoftheParallelProblemSolvingfromNatureVIConference[13]PEAS,ParetoPEAS(1+1),1,,;,,PEAS,,,,,,,PAESO(MN)(,M,N),PEAS,,PAES,Knowles44.1,MOEA,[14],::;:;,4.2,MOEA,?,??,,[1]EhrgottM.Multi-criteriaoptimization[M].Ber2lin:Springer,2000:1921[2].1[M].:,2006:414(26)81:36,[1].()[M].:,2005[2].-C++[M].:,2006[3],,.0/1[J].2005,29(3):5861[4],,.0/1[J].2006,32(6):212214[5],.()[M].:,2003(18)[3]TanKC,KhorEF,LeeTH.Multi-objectiveEv2olutionaryAlgorithmsandApplications[M].London:SpringerVerlag,2005:2426[4]FonsecaCM,FlemingPJ.Anoverviewofevolution2aryalgorithmsinmultiobjectiveoptimization[C].EvolutionaryComputation,1995,3(1):116[5]GoldbergDE.GeneticAlgorithmsinSearch,Optimi2zationandMachineLearning[M].Massachusetts:Addison-WesleyPublishingCompany,1989:7986[6]FonsecaCM,FlemingPJ.GeneticalgorithmsforMulti-objectiveoptimization:Formulation,discussionandgeneralization[C].The5thInternationalConferenceonGeneticAlgorithms.SanMateo,California,1993:5456[7]SrinivasN,DebK.Multiobjectiveoptimizationusingnon-dominatedsortingingeneticalgorithms[J].Evolution2aryComputation,1994,(2):221248[8]HornJ,NafpliotisN,GoldbergDE,etal.AnichedParetogeneticalgorithmformulti-objectiveoptimization[C].TheFirstIEEEConferenceonEvolutionaryComputation,IEEEWorldCongressonComputationalIntelligence.Piscat2away,NewJersey,1994:8287[9]ZitzlerE,ThieleL.AnEvolutionaryAlgorithmforMulti-objectiveOptimization:TheStrengthParetoApproach[R].ComputerEngineeringandCommunicationNetworksLab(TIK),SwissFederalInstituteofTechnology(ETH),Zurich,Switzerland,TechnicalReport,1998:43[10]ZitzlerE,LaunannsM,ThieleL.SPEA:ImprovingtheStrengthParetoEvolutionaryAlgorithm[C].GiannakoglouK,etal.Des.EUROGEN2001.EvolutionaryMethodsforDe2sign,OptimizationandControlwithApplicationstoIndustrialProblems,Athens,Greece,2002:95100[11]DebK,AgrawalS,PratapA,etal.AFastElitistNon-DominatedSortingGeneticAlgorithmforMulti-Objec2tiveOptimization:NSGA-II[C].TheParallelProblemSol2vingfromNatureVIConference.Paris,France,2000:84985[12]DebK,PratapA,AgarwalS,etal.AFastandE2litistMulti-objectiveGeneticAlgorithm:NSGA-II[J].IEEETransactionsonEvolutionaryComputation,2002,6(2):182197[13]KnowlesJD,CorneDW.TheParetoarchivedevo2lutionstrategy:AnewbaselinealgorithmforParetomulti-ob2jectiveoptimization[C].TheParallelProblemSolvingfromNatureVIConference.Piscataway,NewJersy,2000:149172[14],.[J].,2007,34(7):18719162:0-136