Natural Computing Series SeriesEditors:G.Rozenberg Th.Ba¨ck A.E.Eiben J.N.Kok H.P.Spaink LeidenCenterforNaturalComputing AdvisoryBoard:S.Amari G.Brassard K.A.DeJong C.C.A.M.Gielen T.Head L.Kari L.Landweber T.Martinetz Z.Michalewicz M.C.Mozer E.Oja G.Pa˘un J.Reif H.Rubin A.Salomaa M.Schoenauer H.-P.Schwefel C.Torras D.Whitley E.Winfree J.M.Zurada Forfurthervolumes: http://www.springer.com/series/4190 Thomas Jansen Analyzing Evolutionary Algorithms The Computer Science Perspective 123 ThomasJansen DepartmentofComputerScience UniversityCollegeCork Cork Ireland SeriesEditors G.Rozenberg(ManagingEditor) Th.Ba¨ck,J.N.Kok,H.P.Spaink LeidenCenterforNaturalComputing LeidenUniversity Leiden,TheNetherlands A.E.Eiben VrijeUniversiteitAmsterdam TheNetherlands ISSN1619-7127 NaturalComputingSeries ISBN978-3-642-17338-7 ISBN978-3-642-17339-4(eBook) DOI10.1007/978-3-642-17339-4 SpringerHeidelbergNewYorkDordrechtLondon LibraryofCongressControlNumber:2012954385 ACMComputingClassification:F.2,F.1,G.1,I.2 (cid:2)c Springer-VerlagBerlinHeidelberg2013 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerptsinconnection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’slocation,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer. PermissionsforusemaybeobtainedthroughRightsLinkattheCopyrightClearanceCenter.Violations areliabletoprosecutionundertherespectiveCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. While the advice and information in this book are believed to be true and accurate at the date of publication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityfor anyerrorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,with respecttothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) IdedicatethisbooktoIngo Wegener,my Doktorvater. Preface Evolutionaryalgorithmsare generalrandomizedsearch heuristics, inspired by the conceptofnaturalevolution.Theyareeasytoimplementandeasytoapply,thought to be robust problem solvers, popular in circumstances where there is no good problem-specificalgorithmknownandwherethereisnotenoughtimeorexpertise todevelopone.Theirdevelopmentandapplicationismotivatedbypracticalneeds. Therefore,thetheoryofevolutionaryalgorithmsseemstobeacontradiction.Infact, many people are very skeptical toward evolutionary algorithm theory and reject it as impractical, useless, or even just plain wrong. Admittedly, there were times when evolutionary algorithm theory was dominated by unfounded claims, risky hypotheses, and overgeneralizations. But evolutionary algorithm theory has seen a changein thelast two decades,a changethatitself was morerevolutionarythan evolutionary and that has lead to a rigorous, sound, and arguably useful theory. At the heart of this novel theory for evolutionary algorithms is the insight that evolutionary algorithms are in fact randomized algorithms and that consequently they should be analyzed as randomized algorithms. This establishes the study of evolutionary algorithms as an important topic in the area of computer science. Analyzing evolutionary algorithms as randomized algorithms is by far the most importantandfruitfulformoftheoryintheareaofevolutionarycomputationtoday. The analysis of evolutionary algorithms is a lively and very active field of research.Manydifferentandtremendouslyusefultoolsandmethodsforanalyzing evolutionary algorithms have been and continue to be developed. In this book, an introduction to this field of research is presented that makes it accessible by introducing the most important and fundamental analytical methods, presenting theminarigorousmanner,includingcompleteproofs,anddemonstratinghowthey are applied by means of a number of instructive examples. This should enable anyone to enter this fascinating and fruitful field of research: people interested in further developing the theory of randomized search heuristics, practitioners in evolutionary computation who appreciate the importance of a solid theoretical foundation, and people who teach evolutionary computation and prefer solid and provenfactsoverrulesofthumb.Sincethereisnothingmorepracticalthanagood theory, it is hoped that this book on analyzing evolutionary algorithms is seen as vii viii Preface not merely a theoretical exercise but as a useful guide into practical evolutionary computation. Many people have contributed to this book in different forms. I avoid missing any of them by extendingmy sincere thanksto all of them withoutnamingthem: the research groups at the TU Dortmund, George Mason University, the Max- Planck-Institut fu¨r Informatik, and the University of Birmingham and everybody whoparticipatedindiscussionsatDagstuhlseminarsaboutevolutionaryalgorithm theory,atFOGAworkshops,ThRaSHworkshops,workshopsatGECCOandPPSN, or conferences—they all deserve to be acknowledged for contributing insights, expertise, and motivation. Moreover, I gladly acknowledge the generous support bytheDeutscheForschungsgemeinschaft(DFG),theGermanAcademicExchange Service(DAAD),andScienceFoundationIreland(SFI). Cork,Ireland ThomasJansen Contents 1 Introduction .................................................................. 1 1.1 Overview................................................................ 4 1.2 Remarks................................................................. 5 2 Evolutionary Algorithms and Other Randomized SearchHeuristics............................................................. 7 2.1 ModulesofEvolutionaryAlgorithms ................................. 9 2.1.1 Initialization.................................................... 9 2.1.2 Selection........................................................ 10 2.1.3 Mutation........................................................ 12 2.1.4 Crossover....................................................... 14 2.1.5 TerminationCriterion.......................................... 16 2.2 ParametersofEvolutionaryAlgorithms............................... 17 2.3 TypicalEvolutionaryAlgorithms...................................... 19 2.4 OtherSimpleRandomizedSearchHeuristics......................... 22 2.5 DesignofEvolutionaryAlgorithms ................................... 24 2.6 Remarks................................................................. 29 3 TheoreticalPerspectivesonEvolutionaryAlgorithms................... 31 3.1 ApproachesBasedonMarkovChains................................. 32 3.2 SchemaTheory......................................................... 37 3.3 RunTimeAnalysis..................................................... 41 3.4 Remarks................................................................. 43 4 GeneralLimitsinBlack-BoxOptimization............................... 45 4.1 NoFreeLunch.......................................................... 50 4.2 Black-BoxComplexity................................................. 62 4.3 Remarks................................................................. 83 5 MethodsfortheAnalysisofEvolutionaryAlgorithms................... 85 5.1 Fitness-BasedPartitions................................................ 86 5.2 AGeneralLowerBoundforMutation-BasedAlgorithms ........... 100 5.3 TypicalEvents.......................................................... 108 ix x Contents 5.4 DriftAnalysisforLowerBounds...................................... 112 5.5 DriftAnalysisforUpperBounds...................................... 123 5.6 TypicalRuns............................................................ 129 5.7 DelaySequences........................................................ 135 5.8 RandomFamilyTrees.................................................. 142 5.9 Remarks................................................................. 153 6 SelectTopicsintheAnalysisofEvolutionaryAlgorithms............... 157 6.1 Crossover ............................................................... 157 6.2 Mutation ................................................................ 177 6.3 CooperativeCoevolution............................................... 201 6.4 CombinatorialOptimizationProblems................................ 216 6.5 Remarks................................................................. 235 A Fundamentals ................................................................ 237 A.1 LandauNotation........................................................ 237 A.2 TailEstimations ........................................................ 238 A.3 MartingalesandApplications.......................................... 240 A.4 Remarks................................................................. 243 References......................................................................... 245 Index............................................................................... 253