Multiobjective optimization using the niched paret

MultiobjectiveOptimizationUsingTheNichedParetoGeneticAlgorithmJereyHornandNicholasNafpliotisDepartmentofComputerScienceDepartmentofGeneralEngineeringUniversityofIllinoisatUrbana-ChampaignUrbana,IL61801-2996IlliGALReportNo.93005July1993IllinoisGeneticAlgorithmsLaboratory(IlliGAL)DepartmentofGeneralEngineeringUniversityofIllinoisatUrbana-Champaign117TransportationBuilding104SouthMathewsAvenueUrbana,IL61801-2996MultiobjectiveOptimizationUsingtheNichedParetoGeneticAlgorithmJereyHorn,NicholasNafpliotis,andDavidE.GoldbergIllinoisGeneticAlgorithmsLaboratoryUniversityofIllinoisatUrbana-Champaign117TransportationBuilding104SouthMathewsAvenueUrbana,IL61801-2996Internet:[e-mail],[e-mail]:217/333-2346,Fax:[phone]AbstractMany,ifnotmost,optimizationproblemshavemultipleobjectives.Historically,multipleobjectives(i.e.,attributesorcriteria)havebeencombinedadhoctoformascalarobjectivefunction,usuallythroughalinearcombination(weightedsum)ofthemultipleattributes,orbyturningobjectivesintoconstraints.Themostrecentdevelopmentintheeldofdecisionanalysishasyieldedarigoroustechniqueforcombiningattributesmultiplicatively(therebyincorporatingnonlinearity),andforhandlinguncer-taintyintheattributevalues.ButMultiAttributeUtilityAnalysis(MAUA)providesonlyamappingfromavector-valuedobjectivefunctiontoascalar-valuedfunction,anddoesnotaddressthedicultyofsearchinglargeproblemspaces.Geneticalgorithms(GAs),ontheotherhand,arewellsuitedtosearchingintractablylarge,poorlyunderstoodproblemspaces,buthavemostlybeenusedtooptimizeasingleobjective.ThedirectcombinationofMAUAandGAsisalogicalnextstepformultiobjectiveGAoptimization.However,thereisanalternativeapproach.ItturnsoutthattheGAisreadilymodiedtodealwithmultipleobjectivesbyincorporatingtheconceptofParetodominationinitsselectionoperator,andapplyinganichingpressuretospreaditspopulationoutalongtheParetooptimaltradeosurface.Inthisreport,wediscussthegeneralissuesinvolvedinsearchinglargeproblemspaceswhiletryingtooptimizeseveralobjectivessimultaneously.Weexplorevariouscombinationsofdecisionanalysistech-niques,specicallyMAUA,andGAs.Finally,weintroducetheNichedParetoGAasanalgorithmforndingtheParetooptimalset.WecompareandcontrasttheNichedParetoGAwithMAUA.AndwedemonstratetheabilityoftheNichedParetoGAtondandmaintainadiverse\Paretooptimalpopulationontwoarticialproblems,andanopenprobleminhydrosystems.1IntroductionGeneticalgorithms(GAs)havebeenappliedalmostexclusivelytosingle-attribute1problems.Butacarefullookatmany,ifnotmost,ofthereal-worldGAapplicationsrevealsthattheobjectivefunctionsarereallymultiattribute.Typically,theGAuserndssomead-hocfunctionofthemultipleattributestoyieldascalartnessfunction.Often-seentoolsforcombiningmultipleattributesareconstraints,withassociatedthresholdsandpenaltyfunctions,andweightsforlinearcombinationsofattributevalues.Butpenaltiesandweightshaveproventobeproblematic.ThenalGAsolutionisusuallyverysensitivetosmallchangesinthepenaltyfunctioncoecientsandweightingfactors.OneapproachtoimprovetheGA’shandlingofmultipleattributesistouseamoresystematicandrobustmethodforcombiningthemultipleattributesintoasinglescalartnessfunction.Atthevery1Throughoutthisreportweusetheterms\attribute,\objective,and\criteriainterchangeably.Theyalldescribeascalarvaluetobemaximizedorminimized.\Decisionvariablereferstotheparametersoftheproblemencodedinthegenomeofthegeneticalgorithm.1least,suchamethodshouldaccountfornonlinearitiesinattributeinteractions.ThetechniqueknownasMultiAttributeUtilityAnalysis(MAUA)isarecentdevelopmentintheeldofdecisionanalysis.MAUAprescribesamultiplicativecombinationofindividualutilityvalues,whicharefunctionsofattributevaluesandtheuncertaintiesinthosevalues.ThusMAUAaddressesmultiplecriteriaanduncertainty,butdoesnotaddresstheissueofsearch.GAsandMAUAarethereforecomplementarytechniquesforoptimizationanddesign.MAUAhasnospecicmethodforhandlingintractablesearchspaceswhiletraditionalGAsassumeasingleattribute.Afterconductingalimitedsearchoftheliteratureongeneticalgorithms,weconcludedthatGAsandMAUAhaveneverbeforebeencombinedinanymannertosolveaparticularproblem.TheMAUAapproachhassomelimitations,however.First,itonlyincorporatespairwise,multiplicativenonlinearitiesandnothigher-ordernonlineardependencies.Second,toestimatethecoecientsofthesingularandpairwiseterms,MAUArequiresalengthyinterviewwithadecisionmakerinwhichthedecisionanalystposesaseriesoflotteryquestions.Thisprocesscanbetimeconsumingand,ifnotcarefullyperformed,canintroduceerrorsduetobiasonthepartofthedecisionanalyst,etc.Finally,theestimatedscalarutilityfunctionU[~x]pertainsonlytoasingledecisionmaker(orasinglegroupofdecisionmakers,iftheycanallagreeontheiranswerstothelotteryquestions!).ThustheoptimalsolutionfoundbyaGAforaparticularU[~x]isoflittleusetoadierentdecisionmaker.AlloftheseproblemsareavoidedintheParetoapproachdescribednext.AfewstudieshavetriedadierentapproachtomulticriteriaoptimizationwithGAs:usingtheGAtondallpossibletradeosamongthemultiple,conictingobjectives.Thesesolutions(tradeos)arenon-dominat