Multiobjective-Differential-Evolution-with-Externa

1MultiobjectiveDifferentialEvolutionwithExternalArchiveandHarmonicDistance-BasedDiversityMeasureV.L.Huang,P.N.Suganthan,A.K.QinandS.BaskarSchoolofElectricalandElectronicEngineeringNanyangTechnologicalUniversitySingapore639798{huangling,qinkai}@pmail.ntu.edu.sg,[e-mail],[e-mail]:ThispaperpresentsanapproachtoincorporateParetodominanceintothedifferentialevolution(DE)algorithminordertosolveoptimizationproblemswithmorethanoneobjectivebyusingtheDEalgorithm.UnliketheexistingproposalstoextendtheDEtosolvemultiobjectiveoptimizationproblems,ouralgorithmusesanexternalarchivetostorenondominatedsolutions.Inordertogeneratetrialvectors,thecurrentpopulationandthenondominatedsolutionsstoredintheexternalarchiveareused.Wealsoproposeanewharmonicaveragedistancetomeasurethecrowdingdegreeofthesolutionsmoreaccurately.SimulationresultsonninetestproblemsshowthattheproposedMODE,inmostproblems,isabletofindmuchbetterspreadofsolutionswithbetterapproximatingthetruePareto-optimalfrontcomparedtothreeothermultiobjectiveoptimizationevolutionaryalgorithms.FurtherthenewcrowdingdegreeestimationmethodimprovesthediversityofthenondominatedsolutionsalongtheParetofront.Keywords:differentialevolution,multiobjectivedifferentialevolution,multiobjectiveevolutionaryalgorithm,externalarchive.21.IntroductionThedevelopmentofevolutionaryalgorithmstosolvemultiobjectiveoptimizationproblemshasattractedmuchinterestrecentlyandanumberofmultiobjectiveevolutionaryalgorithms(MOEAs)havebeensuggested(ZitzlerandThiele,1999;KnowlesandCorne,2000;Zitzler,LaumannsandThiele,2001;Debetal.,2002;Coelloetal.,2004).Whilemostofthethesealgorithmsweredevelopedtakingintoconsiderationtwocommongoals,namelyfastconvergencetothePareto-optimalfrontandgooddistributionofsolutionsalongthefront,eachalgorithmemploysauniquecombinationofspecifictechniquestoachievethesegoals.SPEA(ZitzlerandThiele,1999)usesasecondarypopulationtostorethenondominatedsolutionsandclustermechanismtoensurediversity.PAES(KnowlesandCorne,2000)usesahistogram-likedensitymeasureoverahyper-griddivisionoftheobjectivespace.NSGA-II(Debetal.,2002)incorporateselitistandcrowdingapproaches.Themainadvantageofevolutionaryalgorithms(EAs)insolvingmulti-objectiveoptimizationproblemsistheirabilitytofindmultiplePareto-optimalsolutionsinonesinglerun.Thedifferentialevolution(DE)algorithmhasbeenfoundtobesuccessfulinsingleobjectiveoptimizationproblems.RecentlythereareseveralattemptstoextendtheDEtosolvemultiobjectiveproblems.Oneapproachispresentedtooptimisetrainmovementbytuningfuzzymembershipfunctionsinmasstransitsystems(Changetal.,1999).Abbassetal.,(2001)introduceaPareto-frontierDifferentialEvolutionalgorithm(PDE)tosolvemultiobjectiveproblembyincorporatingParetodominance.ThisPDEisalsoextendedwithself-adaptivecrossoverandmutation(Abbass,2002).Madavan(2002)extendedDEtosolvemultiobjectiveoptimizationproblemsbyincorporatinganondominatedsortingandrankingselectionschemeofNSGA-II.AnotherapproachinvolvesPareto-basedevaluationtoDEforsolvingmultiobjectivedecisionproblemsandhasbeenappliedtoanenterpriseplanningproblemwithtwoobjectivesnamely,cycletimeandcost(Xue,2003;Xueetal.,2003).Recentlyresearchersalsohavedevelopedparallelmulti-populationDEalgorithm(Parsopoulosetal.,2004)andKukkonenandLampinen(2004)proposeGeneralizedDifferentialEvolution(GDE)forconstrainedmultiobjectivealgorithmandextendGDE2.However,noneoftheexistingapproachesextendDEtodealwithmultiobjectiveoptimizationproblemswithanexternalarchive,whichisaneffectivenotionofelitismandhasbeensuccessfullyusedinotherMOEAs(ZitzlerandThiele,1999;KnowlesandCorne,2000;3Zitzler,LaumannsandThiele,2001;Coelloetal.,2004).Further,existingmultiobjectiveDEimplementationshavenotbeencomprehensivelyevaluatedandcomparedwiththeothermultiobjectiveevolutionaryalgorithms.Inthispaper,wepresentanapproachtoextendDEalgorithmtosolvemultiobjectiveoptimizationproblemswithanexternalarchive,whichwecall“multiobjectivedifferentialevolution”(MODE).Fromthesimulationresultsonseveralstandardtestfunctions,wefindthattheMODEoveralloutperformsthreehighlycompetitiveMOEAs:thenondominatedsortinggeneticalgorithm-II(NSGA-II)(Debetal.,2002),themultiobjectiveparticleswarmoptimization(MOPSO)(Coelloetal.,2004)andParetoarchiveevolutionstrategy(PAES)(KnowlesandCorne,2000).Togenerateabetterdistributionofsolutionsalongthefront,weproposeanewharmonicaveragedistancemeasuretoestimatecrowdingandincorporateitintotheMODEtoobtainMODE-II.Theremainderofthepaperisorganizedasfollows.Section2summarizesthedifferentialevolutionalgorithm.InSection3,wedescribeMODEwithastandardcrowdingdistancemeasureandMODE-IIwithharmonicaveragedistancemeasure.Section4presentssimulationandcomparativeresultsofMODEandthreeothercompetitiveMOEAs,andalsoevaluateseffectivenessoftheharmonicaveragedistancemeasure.ThepaperisconcludedinSection5.2.TheDifferentialEvolutionAlgorithmDifferentialevolution(DE)isasimplepopulation-based,direct-searchalgorithmforglobaloptimization(StornandPrice,1997).Ithasdemonstrateditsrobustnessandeffectivenessinavarietyofapplications,suchasneu