资源描述:
《time complexity of evolutionary algorithms for combinatorial optimization: a decade of results》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、TimeComplexityofEvolutionaryAlgorithmsforCombinatorialOptimization:ADecadeofResultsInternationalJournalofAutomationandComputingTimeComplexity一一ofEvolutionary04(3),July2007,281-293DOI:10.1007/s11633-007-0281-3AlgorithmsforOptimization:ADecadeofResultsPietroS.OlivetoJunHeXi
2、nYaoTheCenterofExcellenceforResearchinComputationalIntelligenceandApplications(CERCIA),SchoolofComputerScienceUniversityofBirmingham,Edgbaston,BirminghamBI52TT,UKAbstract:Computationaltimecornplexityanalyzesofevolutionaryalgorithms(EAs)havebeenperformedsincethemid-ninetie
3、s.Thefirstresultswererelatedtoverysimplealgorithms,suchasthe(1+1)-EA,ontoyproblems.TheseeffortsproducedadeeperunderstandingofhowEAsperformondifierentkindsoffitrIesslandscapesandgeneralmathematicaltoolsthatmaybeextendedtotheanalysisofmorecomplicatedEAsonmorerealisticproble
4、ms.Infact,inrecentyears,ithasbeenpossibletoanalyzethe(1+1)-EAoncombinatorialoptimizationproblemswithpracticalapplicationsandmorerealisticpopulation-basedEAsonstructuredtoyproblems.Thispaperpresentsasurveyoftheresultsobtainedinthelastdecadealongthesetworesearchlines.Themos
5、tcommonmathematicaltechniquesareintroduced,thebasicideasbehindthemarediscussedandtheirelectiveapplicationsarehighlighted.Solvedproblemsthatwerestillopenareenumeratedasarethosestillawaitingforasolution.Newquestionsandproblemsariseninthemeantimearealsoconsidered.Keywords:Ev
6、olutionaryalgorithms,computationalcomplexity,combinatorialoptimization,evolutionarycomputationtheory1IntroductionEvolutionaryalgorithms(EAs)areawideclassofran.domizedproblemsolversbasedonprinciplesofbiologicalevolution.Theyhavebeenused.oftensuccessfully.inmanycomputationa
7、lareassuchasOptimization,Learning,Adap-tationandotherst.Hence.therearelotsofavailableex.perimentalresultsconcerningthisclassofalgorithms,butcomparedtothatamount,thetheoreticalknowledgeofhowtheyperformlagswaybehind.Indeed,thelargestpartoftheavailableresearchstudiesareofemp
8、iricalnature.How.ever,sincetheeightieswhenEAsstartedtobecomepopu-lar,therehavealwaysbeentheoreti