多目标进化算法综述

2012-05-04201215138(1973-)[e-mail]versityofScienceandTechnologyNaturalScienceEdition35320129Vol.35No.3Sep.2012130022ParetoTP31A1672-9870201203-0102-04SurveyofMulti-objectiveEvolutionaryAlgorithmsZHANGFuweiLIJunMENGPinchaoJIANGZhixiaLIYanzhongCollegeofScienceChangchunUniversityofScienceandTechnologyChangchun130022AbstractMulti-objectiveEvolutionaryAlgorithmhasbecomeoneofthemainmethodstosolvemulti-objectiveoptimi-zationproblems.Thispaperintroducesindetailtheclassicalmulti-objectiveevolutionaryalgorithmsanalyzesthestrate-giesadoptedbythevariousalgorithmsandgivestheanalysisoftheadvantagesanddisadvantagesofeachalgorithm.Moreovertheapplicationofmulti-objectiveevolutionaryalgorithmsisalsoexplored.Keywordsmulti-objectiveevolutionaryalgorithmsmulti-objectiveoptimizationevolutionaryalgorithmsPareto-domi-nanceMulti-objectiveOptimizationProblemMOPSingle-objectiveOptimizationProblemSOPMOPPare-toMOPSOPEvolutionaryAlgorithmEAEA1EAParetoEAPareto2MOP1Pareto231985Schaffervector-evaluatedgeneticalgorithmsVEGA3MOGANSGANPGASPEAPAESPESANSGA-IIMOEA/D45ParetoPareto234511.1nmìíîïïïïmin y=F(x)=()f1(x),f2(x),⋯,fm(x)s.t. gj(x)≤0, j=1,2,⋯,J  hk(x)=0, k=1,2,⋯,K1x=(x1,…,xn)∈X⊂RnnXny=(y1,…,yn)∈Y⊂RmmYmF(x)mgj(x)≤0,(j=1,2,…,J)Jhk(x)=0,(k=1,2,…,K)K1∀x∈Xx1x2XXfXf⊆X3Paretox,x'∈Xf1x′xPareto∀i=1,2,…,m, fi(x)≤fi(x')∧∃j=1,2,…,m, fi(x)fi(x')x≻x'xx′4Paretox*∈XfPareto¬∃x∈Xf:x≻x*5ParetoParetoPa-retoP*={}x*|¬∃x∈Xf:x≻x*6ParetoParetoP*ParetoParetoPF*PF*={}F(x*)=()f1(x*),f2(x*),…,fm(x*)T|x*∈P*22.12.1.1VEGA1985SchafferVEGAVectorEvaluatedGeneticAlgorithmMOP3VE-GASGAVEGAkVEGAkN/kNVE-GAPareto2.1.2MOGAFonsecaFlemingMOGAMulti-Ob-jectiveGeneticAlgorithm611MOGAGoldbergMOGA2.1.3NSGASrinivasDebNSGAGoldberg7NSGAPareto2.1.4NPGAHornNatpliotisGoldbergNPGA8NPGAPareto103EricksonParetoNPGA29ParetoPareto0kk2.22.2.1SPEAStrengthParetoEvolutionaryAlgorithmSPEA10SPEAParetoSPEAnichesSPEAStrengthParetoEvolutionaryAlgorithm2SPEA211SPEA1SPEA22SPEA23SPEA22.2.2PAES+PESAKnowlesCorneParetoArchivedEvolutionStrategyPAES12:MOEAPAES1+1CornePESA13SPEAPAESSPEAPEASPAESPESAPAESPESAPESA-IIPESA14hyperboxPESA-IIMOEAPareto2.2.3NSGA-IINondominatedSortingGeneticAlgorithmIINSGA-IIMOEANSGANondomi-natedSortingGeneticAlgorithmNSGA15NSGANSGA-IINSGA-IIcrowdingdistanceNS-GA-IIcrowded-comparisonoperatorNSGA-IIMOEAexternalarchiveelitistmechanismNS-GA-IIμ+λNSGA-IINSGA-II20121043MOEAMOEA1.M.2011.2.J..2009202:271-289.3SchafferJD.Multipleobjectiveoptimizationwithvec-torevaluatedgeneticalgorithmsJ.InProceedingoftheInternationalConferenceonGeneticAlgorithmsandTheirApplicationsHillsdale:L.ErlbaumAsso-ciatesInc198593−100.4CarlosA.CoelloCoello.Evolutionarymulti-objec-tiveoptimization:basicconceptsandsomeapplica-tionsinpatternrecognitionJ.LNCS6718201122-33.5VassilGuliashkiHristoToshevChavdarKorsemov.Surveyofevolutionaryalgorithmsusedinmultiob-jectiveoptimizationJ.ProblemsofEngineeringCy-berneticsandRoboticsBulgarianAcademyofSci-ences2009.6FonsecaCMFlemingPJ.Geneticalgorithmformul-tiobjectiveoptimization:formulationdiscussionandgenerationJ.InProceedingofthe5thInternationalConferenceonGeneticAlgorithms.SanMateo:MorganKauffmanPublishers1993416−423.7SrinivasNDebK.Multiobjectiveoptimizationusingnon-dominatedsortingingeneticalgorithms.Evolu-tionaryComputationvol.2no.3pp.221−2481994.8HornJNafpliotisNGoldbergDE.AnichedParetogeneticalgorithmformultiobjectiveoptimizationJ.InProceedingofthe1stIEEECongressonEvolu-tionaryComputation.Piscataway:IEEE82−871994.9EricksonMMayerAHornJ.ThenichedParetogeneticalgorithm2appliedtothedesignofground-waterremediationsystemJ.Inproceedingofthe1stInternationalConferenceonEvolutionaryMulti-CriterionOptimizationEMO2001.Berlin:Springer-Verlagpp.681−6952001.10ZitzlerELThiele.MultiobjectiveEvolutionaryAl-gorithms:AComparativeCaseStudyandtheStrengthParetoApproachJ.InIEEETransac-tionsonEvolutionaryComputation199934257-271.11ZitzlerELaumannsMThieleL.SPEA2:Improv-ingthestrengthParetoevolutionaryalgorithmM.InEvolutionaryMethodsforDesignOptimizationandControlwithApplicationstoIndustrialProb-lems.Berlin:Springer-Verlag200295-100.12KnowlesJDCorneDW.Approximatingthenon-dominatedfrontusingtheParetoarchivedevo-lutionstrategyJ.EvolutionaryComputation200082149−172.13CorneDWKnowlesJDOatesMJ.ThePare-to-envelopebasedselectionalgorithmformulti-ob-jectiveoptimizationM.InParallelProblemSolv-ingfromNaturePPSNVI.LNCSBerlin:Spring-er-Verlag2000869−878.14CorneDWJerramNRKnowlesJDOatesMJ.PE-SA-II:Region-Basedselectioninevolutionarymulti-objectiveoptimizationM.InProceedingoftheGeneticandEvolutionaryComputationConfer-enceGECCO2001SanFrancisco:MorganKaufmannPublishers2001283−290.15DebKPratapAAgarwalSetal.Afastandelit-istmultiobjectivegeneticalgorithm:NSGA-IIJ.IEEETransactionsofEvoluationaryComputation200262182-972.105