Genetic Programming

An Introduction


  • Wolfgang Banzhaf
  • Peter Nordin
  • Robert Keller
  • Frank Francone

Since the early 1990s, genetic programming (GP)—a discipline whose goal is to enable the automatic generation of computer programs—has emerged as one of the most promising paradigms for fast, productive software development. GP combines biological metaphors gleaned from Darwin's theory of evolution with computer-science approaches drawn from the field of machine learning to create programs that are capable of adapting or recreating themselves for open-ended tasks.This unique introduction to GP provides a detailed overview of the subject and its antecedents, with extensive references to the published and online literature. In addition to explaining the fundamental theory and important algorithms, the text includes practical discussions covering a wealth of potential applications and real-world implementation techniques. Software professionals needing to understand and apply GP concepts will find this book an invaluable practical and theoretical guide.
View full description


Book information

  • Published: December 1997
  • ISBN: 978-1-55860-510-7


"[The authors] have performed a remarkable double service with this excellent book on genetic programming. First, they give an up-to-date view of the rapidly growing field of automatic creation of computer programs by means of evolution and, second, they bring together their own innovative and formidable work on evolution of assembly language machine code and linear genomes." --John R. Koza

Table of Contents

I Prerequisites of Genetic Programming1 Genetic Programming as Machine Learning1.1 Motivation1.2 A Brief History of Machine Learning1.3 Machine Learning as a Process1.4 Major Issues in Machine Learning1.5 Representing the Problem1.6 Transforming Solutions with Search Operators1.7 The Strategy of Search1.8 Learning1.9 Conclusion2 Genetic Programming and Biology2.1 Minimal Requirements for Evolution to Occur2.2 Test Tube Evolution—A Study in Minimalist Evolution2.3 The Genetic Code—DNA as a Computer Program2.4 Genomes, Phenomes, and Ontogeny2.5 Stability and Variability of Genetic Transmission2.6 Species and Sex3 Computer Science and Mathematical Basics3.1 The Importance of Randomness in Evolutionary Learning3.2 Mathmatical Basics3.3 Computer Science Background and Terminology3.4 Computer Hardware3.5 Computer Software4 Genetic Programming as Evolutionary Computation4.1 The Dawn of Genetic Programming—Setting the Stage4.2 Evolutionary Algorithms: The General View4.3 Flavors of Evolutionary Algorithms4.4 Summary of Evolutionary AlgorithmsII Genetic Programming Fundamentals5 Basic Concepts—The Foundation5.1 Terminals and Functions—The Primitives of Genetic Programs5.2 Executable Program Structures5.3 Initializing a GP Population5.4 Genetic Operators5.5 Fitness and Selection5.6 Basic GP Algorithm5.7 An Example Run6 Crossover—The Center of the Storm6.1 The Theoretical Basis for the Building Block Hypothesis in GP6.2 A Gedanken Experiment About Preservation and Disruption of Building Blocks6.3 Empirical Evidence of Crossover Effects6.4 Improving Crossover—The Argument from Biology6.5 Improving Crossover—New Directions6.6 Improving Crossover—A Proposal6.7 Improving Crossover—The Trade-offs6.8 Conclusion7 Genetic Programming and Emergent Order7.1 Introduction7.2 Evolution of Structure and Variable Length Genomes7.3 Iteration, Selection, and Variable Length Program Structures7.4 Evolvable Representations7.5 The Emergence of Introns, Junk DNA, and Bloat7.6 Introns in GP Defined7.7 Why GP Introns Emerge7.8 Effective Fitness and Crossover7.9 Effective Fitness and Other Operators7.10 Why Introns Grow Exponentially7.11 The Effects of Introns7.12 What To Do About Introns8 Analysis—Improving Genetic Programming with Statistics8.1 Basic Statistics Concepts8.2 Basic Statistical Tools for GP8.3 Offline Data Analysis and Processing Before a GP Run—An Overview8.4 Analysis and Preprocessing to Meet Feature Representation Constraints8.5 Analysis and Preprocessing of Data for Feature Extraction8.6 Analysis of Input Data8.7 Postprocessing8.8 Online Data Analysis8.9 Measurement of Online Data8.10 Survey of Available Online Tools8.11 Generalization and Induction8.12 An Example of Overfitting and Poor Generalization8.13 Dealing with Generalization Issues8.14 ConclusionIII Advanced Topics in Genetic Programming9 Different Varieties of Genetic Programming9.1 GP with Tree Genomes9.2 GP with Linear Genomes9.3 GP with Graph Genomes9.4 Other Genomes10 Advanced Genetic Programming10.1 Introduction10.2 Improving the Speed of GP10.3 Improving the Evolvability of Programs10.4 Improving the Power of GP Search11 Implementation—Making Genetic Programming Work11.1 Why Is GP So Computationally Intensive?11.2 Computer Representation of Individuals11.3 Implementations Using LISP11.5 Implementations Using Arrays and Stacks11.6 Implementations Using Machine Code11.7 A Guide to Parameter Choices12 Applications of Genetic Programming12.1 General Overview12.2 Applications from A-Z12.3 Science Oriented Applications12.4 Computer Science Oriented Applications12.5 Engineering Oriented Applications12.6 Summary13 Summary and Perspectives13.1 Summary13.2 The Future of Genetic Programming13.3 ConclusionBibliographyA Printed and Recorded ResourcesA.1 Books On Genetic ProgrammingA.2 GP Video TapesA.3 Books on Evolutionary AlgorithmsA.4 Selected JournalsB Information Available on the InternetB.1 GP TutorialsB.2 GP Frequently Asked QuestionsB.3 GP BibliographiesB.4 GP ResearchersB.5 General Evolutionary ComputationB.6 Mailing ListsC GP SoftwareC.1 Public Domain GP SystemsC.2 Related Software PackagesC.3 C++ Implementation IssuesD EventsD.1 GP ConferencesD.2 Related Conferences and Workshops