Introduction to Evolutionary Algorithms，进化算法电子书Series editorProfessor Rajkumar RoyDepartment of Enterprise IntegrationSchool of Industrial and Manufacturing ScienceCranfield UniversityCranfieldBedfordMK43 OALUKOther titles published in this seriesCost Engineering in PracticeJohn mcilwraithIPA- Concepts and Applications in EngineeringJerzy pokojskiStrategic Decision MakingNavneet bhushan and Kanwal raiProduct Lifecycle ManagementJohn starkFrom Product Description to Cost: A Practical ApproachVolume 1 The Parametric ApproachPierre fussierFrom Product Description to Cost: A Practical approachVolume 2: Building a Specific ModelPierre fussierDecision-Making in Engineering designYotaro hatamuraComposite Systems DecisionsMark sh. levinIntelligent Decision-making Support SystemsJatinder N D. Gupta, Guisseppi A Forgione and Manuel Mora tKnowledge acquisition in PracticeN.R. MiltonGlobal Product: Strategy, Product Lifecycle Management and the billion Customer QuestionJohn StarkEnabling a Simulation Capability in the organisationAndrew GreasleyNetwork Models and optimizationMitsuo gen runewei Cheng and Lin linManagement of UncertaintyGudela groteXinjie yu· Mitsuo genIntroductionto Evolutionary algorithmsSpringerXinjie Yu, PhDMitsuo gen phDDepartment of Electrical EngineeringFuzzy Logic Systems Institute(FLSI)Tsinghua University680-41 Kawazu100084 Beijing820-0067 lizukaChinaJapanyuxj@@tsinghua.edu.cngen@flsi or jpISSN16195736ISBN978-1-84996-128-8e-ISBN978-1-84996-1295DOⅠ10.10071978-1-84996-129-5Springer London Dordrecht Heidelberg New YorkBritish library Cataloguing in Publication DataA catalogue record for this book is available from the British LibraryLibrary of Congress Control Number: 2010929767o Springer-Verlag London limited 2010Discipulus is a trademark of RML Technologies, 7606 S Newland St, Littleton, CO 80128, USA,stered trademark of wolfh. Inc. 100 Trade Center dri,ChampaignIl61820-7237,usa,www.wolfram.comMATLAB is a registered trademark of The Math Works, Inc., 3 Apple Hill Drive, Natick, MA,01760-2098Usa.www.mathworks.comApart from any fair dealing for the purposes of research or private study, or criticism or review,aspermitted under the Copyright, Designs and Patents Act 1988, this publication may only bereproduced, stored or transmitted, in any form or by any means, with the prior permission in writing ofthe publishers, or in the case of reprographic reproduction in accordance with the terms of licencesissued by the Copyright Licensing Agency. Enquiries concerning reproduction outside those termsshould be sent to the publishersThe use of registered names, trademarks, etc in this publication does not imply, even in the absence ofa specific statement, that such names are exempt from the relevant laws and regulations and thereforealee for general useThe publisher makes no representation, express or implied, with regard to the accuracy of theinformation contained in this book and cannot accept any legal responsibility or liability for any errorsor omissions that may be madeCover design: eStudio calamar, Figueres/BerlinPrinted on acid-free paperSpringerispartofSpringerScience+businessMedia(www.springer.com)To our families, friends, and studentsPrefaceThis is a textbook on evolutionary algorithms (EAs). In preparing the proposal andthe manuscript, the following questions were always kept in our mindsIs this book convenient for teaching, studying, and self-study, i.e., have the contents been arranged in a pedagogically sound way?Does this book introduce the state of the art of eas?Does this book cover the contents as comprehensively as possible?Does this book contain specific programming codes so that the reader can usethem directly?For the first two questions, we would like to say yes. We want this textbook to beintuitive because intuitive ideas, and not strict proofs lead to the kind of innovationwe seek. We also want to build a bridge connecting the basics and the cutting edgeso that our students can reach the peak quickly yet with a solid grasp of the mate-rial. Our answer to the remaining two questions is no This textbook is neither anencyclopedia nor a cookbook. We selected only interesting and important topics andleft the reader to implement the codes for the algorithms after we have deliberatelyremoved all understanding obstacles. The reason for the latter consideration lies inthe belief contained in the following saying: Tell me and I'lI forget; show me and Imay remember; let me try, and I can understandEAs have attracted considerable interest in recent years To understand how " hotthe topic is, consider the number of papers indexed by the Science Citation Index(SCI) every year. If the reader has the access to the sCl, he/she is encouraged to doa search to verify the hotness of this topicThe reason the topic is so hot is mainly because of its effects on various problems,i. e, it really works. We will introduce various application examples to show howsimple ideas can be expanded to solve complex problemsThe procedure of designing or analyzing an algorithm for solving optimizationor learning problems is full of challenges, 1. e, problems are difficult. This is irrelevant. We will accompany and assist the reader when necessary we will demonstratethe basic ideas behind the scary equations and try our best to make things easy tounderstand. Incidentally, this cumbersome procedure is also interesting. Before andduring the procedure of climbing Mount Fuji, we thought it would be torture whileat the summit, we felt that all the sufferings were interestingThe prerequisites of this book lie in two aspects. In the mathematics part, a basicunderstanding of linear algebra, multivariable calculus, probability, and statistics inecessary. The other demand is derived from a proficiency in programming. Weassume a firm grasp of at least one programming language, i.e., you can implementan algorithm Since these requirements are in the common curriculum of juniorundergraduate programs, senior undergraduate or graduate students should be ableto read this textbook without knowledge obstaclesThe pedagogical approaches used in this text can be summarized as followsBuilding the mansion from the bricks. We will always focus on the key elementsof an algorithm because later they might become your toolsFrom specific to general. We will always discuss specific simple examples beforeformal expressions.From idea to implementation. We will always introduce the initial notions beforediscussing the concrete contentsExplaining the critical part but leaving questions unanswered deliberately. Wewill leave some obstacles deliberately in the context to activate your thoughtsR W. Hamming gave his motto as the following statement: The purpose ofcomputing is insight, not numbers"in his famous book Numerical Methods for Scientists and engineers. here we would like to use it again to represent our own atti-tude toward EAs. As algorithm designers, we care more about the solution landscapeof the problem and the corresponding search ability of the algorithms, although wedo seek the optimal solution to the problem. From this perspective, there will beless"how-to"in this textbook for specific instructions. On the contrary, there willbe plenty of why-tos to explain the insights and the rationale of a given algorithmso that one can generate ones own cookbook according to these "why-tos. Webelieve that's what the reader wantsOther teaching and self-study considerations include plenty of footnotes for men-tioning easily ignored yet important points, Suggestions for Further Reading" sections in most chapters for further study, exercises with various degrees of difficultto deepen one's understanding and even promote ones own"small-scale researchThe pedagogical relationship among the ten chapters of this textbook is illus-trated by Fig. 0. 1, where the dotted circles separate the ten chapters into three cat-egories: the basics, optimization problems, and other branches. The solid lines arethe suggested pedagogical path for teaching or self-study. Chapters 1 to 3 are allnecessary for subsequent chapters. After that, readers can skip around depending onpersonal interests. Dashed lines represent the improvements, e.g., an understandingI Knowledge of operations research, e.g., linear programming, nonlinear programming, and combinatorial optimization, might contribute to ones understanding but not be necessary2 Father of the Hamming distance, which will be used often in this textbook3 These terms will be explained explicitly and used throughout the book. here they can be takenas the procedure to find the optimal solutionPrefaceof Chap. 4 might contribute to, but not be a prerequisite of, understanding Chap 6and vice versa. We hope Fig 0.1 helps the reader form a mental map for differentbranches and applications of EAsPart I: EAsChI: IntroductionGenetic algorithmCh2: Simple EAsEvolutionary programminSimplex searchScatter searchCh3: Advanced easDifferential evolutionCh4: ConstrainedintelligenceAnt colony optimizationCh5: MultimodalParticle swarm optimizationCh: ArtificialCh6: MultiobiectiveImmune systemCh10: genetieCh7: CombinatorialprogrammIngPart 2: ProblemsPart 3: OthersFig. 0.1 The pedagogical relationship of the ten chapters in this textbookThis book is the result of the development of the course evolutionary computa-tion and Its Applications given by the first author at Tsinghua University since 2002and the numerous intensive courses taught by the second author around the worldToo many names require mention in the acknowledgments. But we wish to expressour appreciation for our students first, especially those in the seminar EvolutionaryAlgorithms 2010. Without your critical comments during the seminar, we wouldhave no appreciation of the readers position, which is perhaps the most distinctivefeature of this textbook. Many of old friends gave encourage and comments on thebook, including Runwei Cheng, Baoding Liu, Kap Hwan Kim, etc. The fast responseand the professional skill of Claire Protherough at Springer and Nadja Kroke at le-tex impressed us deeply. The final, but most important, acknowledgement belongsto Lin Wang and eiko gen because you are the backbones of our livesBeijing ChinaXinjie YuKitakyushu Japan,Mitsuo genMay 2010ContentsPart I Evolutionary Algorithms1 Introduction1.1 What Are Evolutionary algorithms Used For?1. 2 What Are Evolutionary Algorithms?Suggestions for Further ReadingReferences2 Simple Evolutionary algorithms2.1 Introductory Remarks112.2 Simple genetic algorithm....142.2.1 An Optimization problem....142.2.2 Representation and evaluation2.2.3 Initialization2.2.4 Selection182.2.5 Variation Operators2.2.6 Simple genetic Algorithm Infrastructure2.3 Evolution Strategy and Evolutionary Programming2.3.1 Evolution Strategy2.3.2 Evolutionary Programming2.4 Direction-based Search282. 4.1 Deterministic Direction-based search2.4.2 Random Direction-based SearchummaryStions for further readingExercises and Potential Research ProjectsReferences3 Advanced Evolutionary algorithms393.1 Problems We Face..393.2 Encoding and operato