On The Effect of Populations in Evolutionary Multi

UNIVERSIT¨ATDORTMUNDREIHECOMPUTATIONALINTELLIGENCESONDERFORSCHUNGSBEREICH531DesignundManagementkomplexertechnischerProzesseundSystememitMethodenderComputationalIntelligenceOnTheEffectofPopulationsinEvolutionaryMulti-objectiveOptimizationOliverGielandPerKristianLehreNr.CI-202/06InternerBerichtISSN1433-3325Februar2006SekretariatdesSFB531·Universit¨atDortmund·FachbereichInformatik/XI44221Dortmund·GermanyDieseArbeitistimSonderforschungsbereich531,”ComputationalIntelligence“,derUniversit¨atDortmundentstandenundwurdeaufseineVeranlassungunterVerwendungderihmvonderDeutschenForschungsgemeinschaftzurVerf¨ugunggestelltenMittelgedruckt.OnTheEffectofPopulationsinEvolutionaryMulti-objectiveOptimizationOliverGiel1?andPerKristianLehre2??1FachbereichInformatik,Lehrstuhl2Universit¨atDortmund44221Dortmund,[e-mail]ScienceNorwegianUniversityofScienceandTechnology7491Trondheim,[e-mail]-objectiveevolutionaryalgorithms(MOEAs)havebe-comeincreasinglypopularasmulti-objectiveproblemsolvingtechniques.MoststudiesofMOEAsareempirical.Onlyrecently,afewtheoreticalresultshaveappeared.Itisacknowledgedthatmoretheoreticalresearchisneeded.Animportantopenproblemistounderstandtheroleofpopu-lationsinMOEAs.Wepresentasimplebi-objectiveproblemwhichem-phasizeswhenpopulationsareneeded.Rigorousruntimeanalysispointoutanexponentialruntimegapbetweenapopulation-basedalgorithm(SEMO)andseveralsingleindividual-basedalgorithmsonthisproblem.Thismeansthatamongthealgorithmsconsidered,onlythepopulation-basedMOEAissuccessfulandallotheralgorithmsfail.1IntroductionTheunderstandingoftheroleofpopulationsinsingle-objectiveEAshasbeensupportedbytheoreticalresults[11,12].Forexample,thereareproblemswherereducingtheparentpopulationsizebyoneleadstoanexponentialincreaseintheruntime[10].Inapopulationofasingle-objectiveEA,allindividualsarecomparable.ThisistypicallynotthecaseforMOEAs.Hence,itisnotobviousthatresultsforsingle-objectiveproblemscarryovertoMOEAswhenappliedtoatrulymulti-objectiveproblem.Theuseofpopulationsinmulti-objectiveEAsisoftenmotivatedbytheneedtofindasetofsolutions(theParetoset)ratherthanasingleoptimalsolution.However,itisunclearwhetheronecanachievethesamegoalbyrestartingasingleindividualalgorithm.Laumannsetal.[8]provethatsomesimplepopulationbasedMOEAscanslightlyoutperformasingle?SupportedbytheGermanResearchFoundation(DFG)asapartofthecollaborativeresearchcenter“ComputationalIntelligence”(SFB531).??ThisworkwasconductedwhilevisitingUniversit¨atDortmund.2individualbasedapproachcalledε-constrainedmethod.ThisresultaloneisnotsufficienttounderstandtheroleofpopulationsinMOEAssincetheruntimegapisrathersmall,anditgivesonlylittleinsightintowhythepopulationbasedapproachcanbesuperior.Inthispaper,wepresentaproblemwheremanysingleindividual-basedalgorithms,includingtheε-constrainedmethod,faildramatically.Furthermore,thepresentedproblemhasastructurethatcanbetterexplainwhytheindividualbasedalgorithmsfail.Thispaperisorganizedasfollows.WeintroducetheMOEAsconsideredandthenecessarynotationinthenextsection.Theobjectivefunctionwillbepre-sentedinSection3.InSections4–6,weshowthatallconsideredsingleindividualalgorithmsfailonthisobjectivefunction.Finally,inSection7,weprovethatSEMOefficientlydiscoversallParetooptimalpointsintheobjectivespace.2Preliminaries2.1NotationWeassumethatthereaderisfamiliarwiththeconceptsofmulti-objectiveopti-mization(see,e.g.,[2]).Weconsideramaximizationproblemf:{0,1}n→Rm.Forclarity,wesaythatavectorbfromtheobjectivespaceRmweaklydominatesanothervectora,denotedab,ifai≤bi,foralli.Wesaybdominatesa,denoteda≺b,ifabandaibiforatleastoneindexi.Thisnotationwillalsobeusedforsolutionsxandyinthesearchspace{0,1}n.Forexample,xyifandonlyiff(x)f(y).2.2TheMulti-objectiveEAsAllthesingleindividualmulti-objectiveevolutionaryalgorithmsconsideredinthispaperareinstantiationsofthefollowingscheme.Choosexuniformlyfrom{0,1}n.RepeatApplymutationtoxtoobtainx0.Ifselectionfavorsx0overxthenx:=x0.Thealgorithmsdifferinthechoiceofthemutationoperatorandinthechoiceoftheselectionoperator.Twodifferentmutationoperatorsareconsidered.Thelocalmutationoperatorflipsarandomlychosenbitofx.Theglobalmutationoperatorflipseachbitofxindependentlywithprobability1/n.Inthesingle-objectivecase,theobjectivefunctionfestablishesatotalorderinthesearchspaceandselectionfavorsx0overxiff(x0)≥f(x).Then,weobtainrandomizedlocalsearch(RLS)andthe(1+1)EAwiththelocalandglobalsearchoperator,respectively.Formulti-objectiveproblems,thereareseveraloptionswhentofavortheoffspringx0overtheparentx.Inthiswork,weconsiderfourdifferentselection3operators.Theweakestselectionoperatorfavorsx0overxifx0weaklydomi-natesx,orx0andxareincomparable.Theweakselectionoperatorfavorsx0overxifx0weaklydominatesx.Thestrongselectionoperatorfavorsx0overxifx0dominatesx.Finally,wedefinetheε-constraintselectionoperatorfortwocriteriaproblemsasfollows.(See[8]forthegeneraldefinitionwithmcriteria.)Iff1(x)ε,thentheoperatorfavorsx0overxiff1(x0)≥f1(x).Iff1(x)≥ε,thentheoperatorfavorsx0overxiff1(x0)≥εandf