Multiobjective-optimization-using-non-dominated-so

MultiobjectiveOptimizationUsingNondominatedSortinginGeneticAlgorithmsN.SrinivasandKalyanmoyDebDepartmentofMechanicalEngineeringIndianInstituteofTechnologyKanpur,UP208016,INDIAe-mail:[e-mail]emultiobjectiveoptimizationproblems,manytraditionalmethodsscalar-izetheobjectivevectorintoasingleobjective.Inthosecases,theobtainedsolutionishighlysensitivetotheweightvectorusedinthescalarizationprocessanddemandstheusertohaveknowledgeabouttheunderlyingproblem.Moreover,insolvingmultiobjectiveproblems,design-ersmaybeinterestedinasetofPareto-optimalpoints,insteadofasinglepoint.Sincegeneticalgorithms(GAs)workwithapopulationofpoints,itseemsnaturaltouseGAsinmultiobjec-tiveoptimizationproblemstocaptureanumberofsolutionssimultaneously.AlthoughavectorevaluatedGA(VEGA)hasbeenimplementedbySchaerandhasbeentriedtosolveanumberofmultiobjectiveproblems,thealgorithmseemstohavebiastowardssomeregions.Inthispaper,weinvestigateGoldberg’snotionofnondominatedsortinginGAsalongwithanicheandspeciationmethodtondmultiplePareto-optimalpointssimultaneously.Theproof-of-principleresultsobtainedonthreeproblemsusedbySchaerandotherssuggestthattheproposedmethodcanbeextendedtohigherdimensionalandmoredicultmultiobjectiveproblems.Anumberofsuggestionsforextensionandapplicationofthealgorithmisalsodiscussed.1IntroductionManyreal-worlddesignordecisionmakingproblemsinvolvesimultaneousoptimizationofmultipleobjectives.Inprinciple,multiobjectiveoptimizationisverydierentthanthesingle-objectiveoptimization.Insingleobjectiveoptimization,oneattemptstoobtainthebestdesignordecision,whichisusuallytheglobalminimumortheglobalmaximumdependingontheoptimizationproblemisthatofminimizationormaximization.Inthecaseofmultipleobjectives,theremaynotexistonesolutionwhichisbest(globalminimumormaximum)withrespecttoallobjectives.Inatypicalmultiobjectiveoptimizationproblem,thereexistsasetofsolutionswhicharesuperiortotherestofsolutionsinthesearchspacewhenallobjectivesareconsideredbutareinferiortoothersolutionsinthespaceinoneormoreobjectives.ThesesolutionsareknownasPareto-optimalsolutionsornondominatedsolutions(ChankongandHaimes1983;Hans1988).TherestofthesolutionsareThispaperhasappearedintheJournalofEvolutionaryComputation,Vol.2,No.3,pages221{248.1knownasdominatedsolutions.Sincenoneofthesolutionsinthenondominatedsetisabsolutelybetterthananyother,anyoneofthemisanacceptablesolution.Thechoiceofonesolutionovertheotherrequiresproblemknowledgeandanumberofproblem-relatedfactors.Thus,onesolutionchosenbyadesignermaynotbeacceptabletoanotherdesignerorinachangedenvironment.Therefore,inmultiobjectiveoptimizationproblems,itmaybeusefultohaveaknowledgeaboutalternativePareto-optimalsolutions.Onewaytosolvemultiobjectiveproblemsistoscalarizethevectorofobjectivesintooneobjec-tivebyaveragingtheobjectiveswithaweightvector.Thisprocessallowsasimpleroptimizationalgorithmtobeused,buttheobtainedsolutionlargelydependsontheweightvectorusedinthescalarizationprocess.Moreover,ifavailable,adecisionmakermaybeinterestedinknowingal-ternatesolutions.Sincegeneticalgorithms(GAs)workwithapopulationofpoints,anumberofPareto-optimalsolutionsmaybecapturedusingGAs.AnearlyGAapplicationonmultiobjectiveoptimizationbySchaer(1984)openedanewavenueofresearchinthiseld.Thoughhisalgorithm,VEGA,gaveencouragingresults,itsueredfrombiasnesstowardssomePareto-optimalsolutions.Anewalgorithm,NondominatedSortingGeneticAlgorithm(NSGA),ispresentedinthispaperbasedonGoldberg’ssuggestion(Goldberg1989).ThisalgorithmeliminatesthebiasinVEGAandtherebydistributesthepopulationovertheentirePareto-optimalregions.Althoughthereexisttwootherimplementations(FonescaandFleming1993;Horn,Nafpliotis,andGoldberg1994)basedonthisidea,NSGAisdierentfromtheirworkingprinciples,asexplainedbelow.Intheremainderofthepaper,webrieydescribedicultiesofusingthreecommonclassicalmethodstosolvemultiobjectiveoptimizationproblems.AbriefintroductiontoSchaer’sVEGAanditsproblemsareoutlined.Thereafter,thenondominatedsortingGAisdescribedandappliedtothreetwo-objectivetestproblems.SimulationresultsshowthatNSGAperformsbetterthanVEGAontheseproblems.Anumberofextensionstothisworkisalsosuggested.2MultiobjectiveOptimizationProblemAgeneralmultiobjectiveoptimizationproblemconsistsofanumberofobjectivesandisassociatedwithanumberofinequalityandequalityconstraints.Mathematically,theproblemcanbewrittenasfollows(Rao1991):Minimize/Maximizefi(x)i=1;2;:::;NSubjecttogj(x)0j=1;2;:::;Jhk(x)=0k=1;2;:::;K(1)2Theparameterxisapdimensionalvectorhavingpdesignordecisionvariables.Solutionstoamultiobjectiveoptimizationproblemaremathematicallyexpressedintermsofnondominatedorsuperiorpoints.Inaminimizationproblem,avectorx(1)ispartiallylessthananothervectorx(2);(x(1)x(2)),whennovalueofx(2)islessthanx(1)andatleastonevalueofx(2)isstrictlygreaterthanx(1).Ifx(1)ispartiallylessthanx(2),wesaythatthesolutionx(1)dominatesx(2)orthesolutionx(2)isinferiortox(1)(TamuraandMiura1979).Anymemberofsuchvectorswhichisnotdominatedbyanyothermemberissaidtobenondominatedornon-inferior.Similarlyiftheobjectiveistom