An introduction to genetic algorithms

An Introduction to Genetic Algorithms............................................................................................................1 Mitchell Melanie.....................................................................................................................................1 Chapter 1: Genetic Algorithms: An Overview.................................................................................................2 Overview.................................................................................................................................................2 1.1 A BRIEF HISTORY OF EVOLUTIONARY COMPUTATION.....................................................2 1.2 THE APPEAL OF EVOLUTION.....................................................................................................4 1.3 BIOLOGICAL TERMINOLOGY.....................................................................................................5 1.4 SEARCH SPACES AND FITNESS LANDSCAPES.......................................................................6 1.5 ELEMENTS OF GENETIC ALGORITHMS...................................................................................7 Examples of Fitness Functions...................................................................................................7 GA Operators.............................................................................................................................8 1.6 A SIMPLE GENETIC ALGORITHM..............................................................................................8 1.7 GENETIC ALGORITHMS AND TRADITIONAL SEARCH METHODS..................................10 1.9 TWO BRIEF EXAMPLES..............................................................................................................12 Using GAs to Evolve Strategies for the Prisoner's Dilemma...................................................13 Hosts and Parasites: Using GAs to Evolve Sorting Networks..................................................16 1.10 HOW DO GENETIC ALGORITHMS WORK?...........................................................................21 THOUGHT EXERCISES......................................................................................................................23 COMPUTER EXERCISES...................................................................................................................24 Chapter 2: Genetic Algorithms in Problem Solving......................................................................................27 Overview...............................................................................................................................................27 2.1 EVOLVING COMPUTER PROGRAMS.......................................................................................27 Evolving Lisp Programs...........................................................................................................27 Evolving Cellular Automata.....................................................................................................34 2.2 DATA ANALYSIS AND PREDICTION.......................................................................................42 Predicting Dynamical Systems.................................................................................................42 Predicting Protein Structure......................................................................................................47 2.3 EVOLVING NEURAL NETWORKS............................................................................................49 Evolving Weights in a Fixed Network.....................................................................................50 Evolving Network Architectures..............................................................................................53 Direct Encoding.......................................................................................................................54 Grammatical Encoding.............................................................................................................55 Evolving a Learning Rule.........................................................................................................58 THOUGHT EXERCISES......................................................................................................................60 COMPUTER EXERCISES...................................................................................................................62 Chapter 3: Genetic Algorithms in Scientific Models.....................................................................................65 Overview...............................................................................................................................................65 3.1 MODELING INTERACTIONS BETWEEN LEARNING AND EVOLUTION...........................66 The Baldwin Effect...................................................................................................................66 A Simple Model of the Baldwin Effect....................................................................................68 Evolutionary Reinforcement Learning.....................................................................................72 3.2 MODELING SEXUAL SELECTION.............................................................................................75 Simulation and Elaboration of a Mathematical Model for Sexual Selection...........................76 3.3 MODELING ECOSYSTEMS.........................................................................................................78 3.4 MEASURING EVOLUTIONARY ACTIVITY.............................................................................81 Thought Exercises.................................................................................................................................84 Computer Exercises..............................................................................................................................85 Chapter 4: Theoretical Foundations of Genetic Algorithms........................................................................87 Overview...............................................................................................................................................87 4.1 SCHEMAS AND THE TWO−ARMED BANDIT PROBLEM.....................................................87 The Two−Armed Bandit Problem............................................................................................88 Sketch of a Solution..................................................................................................................89 Interpretation of the Solution....................................................................................................91 Implications for GA Performance.............................................................................................92 Deceiving a Genetic Algorithm................................................................................................93 Limitations of "Static" Schema Analysis..................................................................................93 4.2 ROYAL ROADS............................................................................................................................94 Royal Road Functions...............................................................................................................94 Experimental Results................................................................................................................95 Steepest−ascent hill climbing (SAHC).....................................................................................96 Next−ascent hill climbing (NAHC)..........................................................................................96 Random−mutation hill climbing (RMHC)...............................................................................96 Analysis of Random−Mutation Hill Climbing.........................................................................97 Hitchhiking in the Genetic Algorithm......................................................................................98 An Idealized Genetic Algorithm...............................................................................................99 4.3 EXACT MATHEMATICAL MODELS OF SIMPLE GENETIC ALGORITHMS.....................103 Formalization of GAs.............................................................................................................103 Results of the Formalization...................................................................................................108 A Finite−Population Model....................................................................................................108 4.4 STATISTICAL−MECHANICS APPROACHES.........................................................................112 THOUGHT EXERCISES....................................................................................................................114 COMPUTER EXERCISES.................................................................................................................116 5.1 WHEN SHOULD A GENETIC ALGORITHM BE USED?........................................................116 5.2 ENCODING A PROBLEM FOR A GENETIC ALGORITHM...................................................117 Binary Encodings....................................................................................................................117 Many−Character and Real−Valued Encodings......................................................................118 Tree Encodings......................................................................................................................118 5.3 ADAPTING THE ENCODING....................................................................................................118 Inversion................................................................................................................................119 Evolving Crossover "Hot Spots"............................................................................................120 Messy Gas..............................................................................................................................121 5.4 SELECTION METHODS.............................................................................................................124 Fitness−Proportionate Selection with "Roulette Wheel" and "Stochastic Universal" Sampling...............................................................................................................................124 Sigma Scaling........................................................................................................................125 Elitism....................................................................................................................................126 Boltzmann Selection...............................................................................................................126 Rank Selection.......................................................................................................................127 Tournament Selection.............................................................................................................127 Steady−State Selection...........................................................................................................128 5.5 GENETIC OPERATORS..............................................................................................................128 Crossover...............................................................................................................................128 Mutation.................................................................................................................................129 Other Operators and Mating Strategies..................................................................................130 5.6 PARAMETERS FOR GENETIC ALGORITHMS.......................................................................130 THOUGHT EXERCISES....................................................................................................................132 COMPUTER EXERCISES.................................................................................................................133 Chapter 6: Conclusions and Future Directions............................................................................................135 Overview.............................................................................................................................................135 Incorporating Ecological Interactions..................................................................................................136 Incorporating New Ideas from Genetics..............................................................................................136 Incorporating Development and Learning...........................................................................................137 Adapting Encodings and Using Encodings That Permit Hierarchy and Open−Endedness.................137 Adapting Parameters...........................................................................................................................137 Connections with the Mathematical Genetics Literature.....................................................................138 Extension of Statistical Mechanics Approaches..................................................................................138 Identifying and Overcoming Impediments to the Success of GAs......................................................138 Understanding the Role of Schemas in GAs........................................................................................138 Understanding the Role of Crossover..................................................................................................139 Theory of GAs With Endogenous Fitness...........................................................................................139 Appendix A: Selected General References...................................................................................................140 Appendix B: Other Resources......................................................................................................................141 SELECTED JOURNALS PUBLISHING WORK ON GENETIC ALGORITHMS..........................141 SELECTED ANNUAL OR BIANNUAL CONFERENCES INCLUDING WORK ON GENETIC ALGORITHMS................................................................................................................141 INTERNET MAILING LISTS, WORLD WIDE WEB SITES, AND NEWS GROUPS WITH INFORMATION AND DISCUSSIONS ON GENETIC ALGORITHMS........................................142 Bibliography.......................................................................................................................................143