Drift analysis and average time complexity of evol

DriftAnalysisandAverageTimeComplexityofEvolutionaryAlgorithmsJunHeDepartmentofComputerSieneNorthernJiaotongUniversityBeijing100044,P.R.ChinaXinYaoyShoolofComputerSieneTheUniversityofBirminghamBirminghamB152TT,U.K.Email:x.yaos.bham.a.ukDeember21,2000AbstratTheomputationaltimeomplexityisanimportanttopiinthetheoryofevolutionaryalgorithms(EAs).ThispaperreportssomenewresultsontheaveragetimeomplexityofEAs.Basedondriftanalysis,someusefuldriftonditionsforderivingthetimeomplexityofEAsarestudied,inludingonditionsunderwhihanEAwilltakenomorethanpolynomialtime(inproblemsize)tosolveaproblemandonditionsunderwhihanEAwilltakeatleastexponentialtime(inproblemsize)tosolveaproblem.Thepaperrstpresentsthegeneralresults,andthenusesseveralproblemsasexamplestoillustratehowthesegeneralresultsanbeappliedtoonreteproblemsinanalyzingtheaveragetimeomplexityofEAs.Whilepreviousworkonlyonsidered(1+1)EAswithoutanyrossover,theEAsonsideredinthispaperarefairlygeneral,whihuseanitepopulation,rossover,mutation,andseletion.KeywordsEvolutionaryalgorithms,timeomplexity,randomsequenes,driftanalysis,stohastiinequalities.1IntrodutionEvolutionaryalgorithms(EAs)areapowerfullassofadaptivesearhalgorithms[1,4,5℄.Theyhavebeenusedtosolvemanyombinatorialproblemswithsuessinreentyears.However,theoriesonexplainingwhyandhowEAsworkarestillrelativelyfewinspiteofreenteorts[6℄.TheomputationaltimeomplexityofEAsislargelyunknown,exeptforafewsimpleases[7,8,9,10,11℄.Ambatietal.[8℄andFogel[9℄estimatedtheomputationaltimeomplexityoftheirEAsonthetravelingsalesmanproblem.Notheoretialresultsweregiven.Rudolph[10℄provedthat(1+1)EAswithmutationprobabilitypm=1=n,wherenisthenumberofbitsinabinarystring(i.e.,individual)andpmisthemutationprobability,onvergeinaveragetimeO(nlogn)fortheONE-MAXproblem.Drosteetal.[11℄arriedoutarigorousomplexityanalysisof(1+1)EAsforlinearfuntionswithBooleaninputs.However,alloftheseresultswerebasedonEAswithapopulationsizeof1andwithoutanyrossoveroperators.Nimwegenetal.[12,13℄developedatheorywhihpreditsthetotalnumberoftnessfuntionevaluationsneededtoreahaglobalAeptedbyArtiialIntelligenejournalin2000.Toappearin2001.yCorrespondingauthor.1optimumbyepohaldynamisasafuntionofmutationrateandpopulationsize.However,norelationshiptotheproblemsizewasstudied.Heetal.[14,15℄showedthatgenetialgorithms(GAs)maytakeexponentialaveragetimetosolvesomedeeptiveproblems.ThispaperpresentsamoregeneraltheoryabouttheaveragetimeomplexityofEAs.ThemotivationofthisstudyistoestablishageneraltheoryforalassofEAs,ratherthanapartiularEA.ThetheoryanthenbeusedtoderivespeiomplexityresultsfordierentEAsondierentproblems.Thetheoryhasbeendevelopedusingdriftanalysis[16,17℄|averyusefultehniqueinanalyzingrandomsequenes.Itanbeusedtoestimatethersthittingtimebyestimatingthedriftofarandomsequene.Toourbestknowledge,thisistherstattemptthatdriftanalysisisintroduedintothetheoretialstudyofevolutionaryomputation.Oneofthemajoradvantagesofusingdriftanalysisisthatitisofteneasiertoestimatethedriftthantoestimatethersthittingtimediretly.ThetehniquesofdriftanalysisanalsobeappliedtorandomsequeneswhiharenotMarkovian[16℄.Thebasiideaofthispaperisasfollows.WerstmodeltheevolutionofanEApopulationasarandomsequene,e.g.,aMarkovhain.Apopulationofmultipleindividualswillbeonsidered.BothrossoverandmutationareinludedintheEA.Thenweanalyzedthedriftofthissequenetoandfromtheoptimalsolution(assumingwearesolvinganoptimizationproblem).Variousboundsonthersthittingtimewillbederivedunderdierentdriftonditions.Somedriftonditionsausetherandomsequenetodriftawayfromtheoptimalsolution,whileotherdriftonditionsenablethesequenetodrifttowardstheoptimalsolution.WewillstudytheonditionswhihareusedtodeterminethetimeomplexityofanEAtosolveaproblem,whetherinpolynomialtime(inproblemsize)orinexponentialtime.Toillustratetheappliationoftheabovegeneraltheory,wewillapplythetheoretialresultstoseveralwell-knownproblems,inludingalassialombinatorialoptimizationproblem|thesubsetsumproblem.ItisshowninthispaperthataertainfamilyofsubsetsumproblemsanbesolvedbyanEAwithinpolynomialtime,whileotherfamiliesofsubsetsumproblemswillneedatleastexponentialtimetosolve.AlthoughtheEAsusedinourstudydonotinludeallpossiblevariationsofEAs,theydorepresentafairlylargelassofEAswhihhavemultipleindividualsandusebothrossoverandmutation.Therestofthispaperisorganizedasfollows:Setion2introduesbrieyEAsanddriftanalysis.Setion3studiestheonditionsunderwhihEAsansolveaproblemwithinpolynomialtimeonaverage.Ageneraltheoremisrstpresented.Thenexamples,inludingthesubsetsumproblem,arestudiedtoshowtheappliationofthetheorem.Setion4studiestheonditionsunderwhihEAsneedatleastexponentialomputationtimetosolveaproblem.Bothageneraltheoremandanappliationofthetheoremaregiven.Setion5disussessomeweakerdriftonditionsforthesubsetsumproblem.Finally,Setion6onludeswithabriefsummaryofthepaperandsomefuturework.2EvolutionaryAlgorithmsandDriftAnalysis2.1EvolutionaryAlgorithmsTheombinatorialoptimizationproblemonsideredinthispaperanbedesribedasfollows:GivenanitestatespaeSandafuntionf(x);x2S,ndmaxff(x);x2Sg:(1)Assumexisonest