Journal Home Online First Current Issue Archive For Authors Journal Information 中文版

Strategic Study of CAE >> 2002, Volume 4, Issue 2

Evolutionary Algorithms for Multi-objective Optimization and Decision-Making Problems

Institute of Computer Science , National University of Defense Technology, Changsha 410073, China

Funding project:国家自然科学基金资助项目(NSF69903010, NSF 60133010, NSF69933030) Received: 2001-04-10 Revised: 2001-11-10 Available online: 2002-02-20

Next Previous

Abstract

Multi-objective optimization (MOO) and decision-making (DM) has become an important research area of evolutionary computations in recent years. The researches on multi-objective evolutionary algorithms (MOEA) focus mainly on the Pareto-based comparison and ordering of individuals, fitness assignment and Riching techniques, etc., so that the population can converge and uniformly distribute in the Pareto front. This paper presents an introduction to the history and classification of multi-objective optimization and decision-making techniques, analyzes both the Pareto-based and non-Pareto-based evolutionary algorithms, and,particularly,the five well-known MOEAs. Some problems related to the researches on MOEAs are addressed in details, such as the characteristics of Pareto front, the test suite and performance evaluation of MOEAs, the MOEA convergence analysis, the MOEA parallelization, and the disposal of real world MOO problems.

Figures

图1

图2

References

[ 1 ] ParetoV .Coursd’economiespolitique, volumeIandII[M ].FRouge, Lausanne, 1896

[ 2 ] RosenbergRS .Simulationofgeneticpopulationswithbiochemicalproperties[D ].UniversityofMichigan, AnnHarbor, Michigan, 1967

[ 3 ] SchafferJD .Multipleobjectiveoptimizationwithvectorevaluatedgeneticalgorithms[A].GeneticAlgorithmsandtheirApplications:ProceedingoftheFirstInterna tionalConferenceonGeneticAlgorithms[C], LawrenceErlbaum, 1985.93~100

[ 4 ] VeldhuizenDAV , LamontGB .Multiobjectiveevolu tionaryalgorithmresearch:ahistoryandanalysis[R].TR 9803, DepartmentofElectricalandComputerEn gineering, GraduateSchoolofEngineering, AirForceInstituteofTechnology, WrightPattersonAFB , OH , USA , 1998

[ 5 ] FonsecaCM , FlemingPJ.Geneticalgorithmsformul tiobjectiveoptimization:formulation, discussionandgeneration[A].ForrestS .ProceedingsoftheFifthIn ternationalConferenceonGeneticAlgorithms[C], SanMateo, California, UniversityofIllinoisatUrbanaChampaign, MorganKaufmanPublishers, 1993.416~423

[ 6 ] SrinivasN , KalyanmoyD .Multiobjectiveoptimizationusingnondominatedsortingingeneticalgorithms[J].EvolutionaryComputation, 1994, 2 (3) :221~248

[ 7 ] HornJ, NafpliotisN .MultiobjectiveoptimizationusingtheRichedParetogeneticalgorithm[R].TechnicalRe portIlliGALReport93005, UniversityofIllinoisatUr banaChampaign, Urbana, Illinois, USA , 1993

[ 8 ] LisJ, EibenAE .Amulti sexualgeneticalgorithmformulti objectiveoptimization[A].FukudaT , FuruhashiT .Proceedingsofthe1996InternationalConferenceonEvolutionaryComputation, IEEE [C], Nagoya, Japan, 1996.59~64

[ 9 ] DarrellW .Evaluatingevolutionaryalgorithms[J].Ar tificialIntelligence, 1996, 85:245~276

[10] WienkePB , LucasiusC , KatemanG .Multicriteriatargetvectoroptimizationofanalyticalproceduresusinga geneticalgorithm[J].AnalyticaChimicaActa, 1992, 265 (2) :211~225

[11] TsengCH , LuTW .Minimaxmultiobjectiveoptimiza tioninstructuraldesign[J].InternationalJournalforNumericalMethodsinEngineering, 1990, 30:1213~1228

[12] ChipperfieldAJ , FlemingPJ .Gasturbineenginecon trollerdesignusingmultiobjective geneticalgorithms[A ].ZalzalaAMS .ProceedingsoftheFirstIEE/IEEEInternationalConferenceonGeneticAlgorithmsinEngineeringSystems:InnovationsandApplications[C ], HalifaxHall, UniversityofSheffield, UK , September1995.214~219

[13] ViciniA , QuagliarellaD .Inverseanddirectairfoilde signusingamultiobjectivegeneticalgorithm[J].AIAAJournal, September1997, 35 (9) :1499~1505

[14] JonesBR , CrossleyWA , LyrintzisAS .Aerodynamicandaeroacousticoptimizationofairfoilsviaaparallelge neticalgorithm[A].Proceedingsofthe7thAIAA/US AF/NASA/ISSMOSymposiumonMultidisciplinaryAnalysisandOptimization[C], AIAA , 1998

[15] FujitaK , HirokawaN , AkagiS , etal.Multi objectiveoptimaldesignofautomotiveengineusinggeneticalgo rithm[A].ProceedingsofDETC’98ASMEDesignEngineeringTechnicalConferences[C], 1998

[16] CohonJL , MarksDH .Reviewandevaluationofmul tiobjective programmingtechniques[J].WaterRe sourcesResearch, 1975, 11 (2) :208~220

[17] HwangCL , MasudASM .Multiobjectivedecisionmaking:methodsandapplications[M ].SpringerVer lag, 1979

[18] CoelloCAC .Handlingpreferencesinevolutionarymul tiobjectiveoptimization:Asurvey[A].2000CongressonEvolutionaryComputation[C], Piscataway, NewJersey, IEEEServiceCenter, July2000, 1:30~37

[19] AharonBT .CharacterizationofParetoandlexico graphicoptimalsolutions[A].FandelG , GalT .MultiCriteriaDecisionMakingTheoryandApplication, 177ofLectureNotesinEconomicsandMathematicalSys tems[M], Berlin:SpringerVerlag, 1980.1~11

[20] FourmanMP .Compactionofsymboliclayoutusingge neticalgorithms[A].ProceedingsoftheFirstInterna tionalConferenceonGeneticAlgorithms[C], LawrenceErlbaum, 1985.141~153

[21] HajelaP , LinCY .Geneticsearchstrategiesinmulti criterionoptimaldesign[J].StructuralOptimization, 1992, 4:99~107 link1

[22] ViennetR , FontiexC , MarcI.Multicriteriaoptimiza tionusingageneticalgorithmfordeterminingaParetoset[J].InternationalJournalofSystemsScience, 1996, 27 (2) :255~260

[23] LiuTK , IshiharaT , InookaH .Multiobjectivecontrolsystemsdesignbygeneticalgorithms[A].Proceedingsofthe34thSocietyofInternationalandControlEngi neeringAnnualConference[C], 1995.1521~1526

[24] BaitaF , MasonF , PoloniC , etal.Geneticalgorithmwithredundanciesforthevehiclescheduling problem[A].BiethahnJ , NissenV .EvolutionaryAlgorithmsinManagementApplications[M ].Berlin:SpringerVerlag.1995.341~353

[25] TakadaY , YamamuraM , KobayashiS .AnapproachtoPortfolioselectionproblemsusingmulti objectivege neticalgorithms[A].Proceedingsofthe23rdSympo siumonIntelligentSystems[C], 1996.103~108

[26] KursaweF .Avariantofevolutionstrategiesforvectoroptimization[A].SchwefelHP , MannerR .ParallelProblemSolvingfromNature, 1stWorkshop, Proceed ings, volume496ofLecturenotesinComputerScience[C], Berlin:SpringerVerlag, 1991.193~197

[27] GoldbergDE .Geneticalgorithmsinsearch, optimiza tionandmachinelearning[M ].Massachusetts:Addi sonWesley, Reading, 1989

[28] AllensonR .Geneticalgorithmswithgenderformulti functionoptimization[R ].TechnicalReportEPCC SS9201, EdinburghParallelComputingCenter, Edin burgh, Scotland, 1992

[29] CoelloCAC .Anupdatedsurveyofevolutionarymultiobjectiveoptimizationtechniques:stateoftheartandfuturetrends[R].TechnicalReportLaniaRD 9808, LaboratorioNationaldeInformaticsAvanzada (LANI A) , Xalapa, VeraCruz, Mexico, December1998

[30] FonsecaCM , FlemingPJ .Anoverviewofevolution aryalgorithmsinmultiobjectiveoptimization[J].Evo lutionaryComputation, 1995, 3 (1) :1~16

[31] GoldbergDE , RichardsonJ.Geneticalgorithmswithsharingformultimodalfunctionoptimization[A].Procofthe2ndInternationalConferenceontheGeneticAl gorithms[C], 1987.41~49

[32] BakerJE .Reducingbiasandinefficiencyintheselectionalgorithm[A].Proceedingsofthe2ndInternation alConferenceontheGeneticAlgorithms[C], 1987.14~21

[33] ZitzlerE , ThieleL .MultiobjectiveoptimizationusingevolutionaryalgorithmsAcomparativecasestudy[A].EibenAE , etal.ParallelProblemSolvingfromNaturePPSNV [M], BerlinSpringer, 1998

[34] WolpertDH , MacreadyWG .Nofreelunchtheoremsforoptimization[J].IEEETransactionsonEvolution aryComputation, 1997, 1 (1) :67~82

[35] FonsecaCM , FlemingPJ .Multiobjectiveoptimizationandmultipleconstrainshandlingwithevolutionaryalgo rithmsPartI:Aunifiedformulation, andPartII:Ap plicationexample[J].IEEETransactionsonSystems, Man&CyberneticsPartA :SystemsandHumans, 1998, 28 (1) :26~47

[36] VeldhuizenDAV , LamontGB .Evolutionarycompu tationandconvergencetoaParetofront[A].KozaJR .LateBreakingPapersattheGeneticProgramming1998Conference[C], Stanford, CA :StanfordUniver sityBookstore, July1998.221~228

[37] DeJongKA .Ananalysisofthebehaviorofaclassofgeneticadaptivesystems[D].TheUniversityofMichi gan, AnnArborMI , 1975

[38] MichalewiczZ .Geneticalgorithms+datastructures=evolutionprograms[M ].2ndEdition, NewYork:SpringerVerlag, 1994

[39] GoldbergDE .Messygeneticalgorithms:motivation, analysis, andfirstresults[J].ComplexSystems, 1989, 3:493~530

[40] RudolphG .OnaMulti objectiveevolutionaryalgorithmanditsconvergencetotheParetoset[A].Proceedingofthe1998IEEEConferenceonEvolutionaryComputa tion[C], 1998

[41] FonsecaCM , FlemingPJ.Multiobjectivegeneticalgo rithmsmadeeasy:selection, sharingandmatingrestric tion[A].Proceedingofthe1stinternationalConferenceonGeneticAlgorithmsinEngineeringSystems:Innova tionsandApplications, IEE [C], September1995, 414:45~52

[42] ZitzlerE , ThieleL .Anevolutionaryalgorithmformul tiobjectiveoptimization:thestrengthParetoapproach[R].TechnicalReportTIK43, ComputerEngineeringandCommunicationNetworksLab, SwissFederalInsti tuteofTechnology, Gloriastrasse35, CH8092, Zurich, Switzerland, May1998

[43] CvetkovicD , ParmeeIC .Geneticalgorithm basedmulti objectiveoptimizationandconceptualengineeringdesign[A].1999CongressonEvolutionaryComputa tion[C], WashingtonDC , USA , July1999.6~9

[44] XieTao, ChenHuowang.Problemdecomposition basedscalablemacro evolutionaryalgorithms[A ].2001CongressonEvolutionaryComputation[C], Seoul, Ko rea, April2001.200~210

[45] 谢 涛, 陈火旺.基于函数分解的可伸缩宏进化算法[J].自然科学进展, 2001, 11 (6) :661~667 link1

Related Research