FOUNDATIONS OF GENETIC PROGRAMMING

by

W. B. Langdon and R. Poli

Published by Springer. ISBN 3-540-42451-2
Amazon USA UK.

More information, table of contents and code.

BibTeX citation

Cute movie of a GP population evolving

Not so cute picture of bill presenting the book at GECCO'2001.
Complete tutorial slides for GECCO 2003 and (chapters 7 and 8) for CEC-2005 (PDF).
Picture of Ricardo Landa Becerra being awarded a prize copy at GECCO 2005 by Micheal O'Neill.

Foundations of Genetic Programming cover

Table of Contents

Preface
Acknowledgements
Chapter 1. Introduction1
1.1Problem Solving as Search2
1.2What is Genetic Programming?9
1.3Outline of the Book15
Chapter 2. Fitness Landscapes17
2.1Exhaustive Search17
2.2Hill Climbing17
2.3Fitness Landscapes as Models of Problem Difficulty19
2.4An Example GP Fitness Landscape20
2.5Other Search Strategies21
2.6Difficulties with the Fitness Landscape Metaphor23
2.7Effect of Representation Changes25
2.8Summary26
Chapter 3.Program Component Schema Theories27
3.1Price's Selection and Covariance Theorem28
3.2Genetic Algorithm Schemata33
3.3From GA Schemata\ to GP Schemata35
3.4Koza's Genetic Programming Schemata38
3.5Altenberg's GP Schema Theory39
3.6O'Reilly's Genetic Programming Schemata42
3.7Whigham's Genetic Programming Schemata44
3.8Summary46
Chapter 4.Pessimistic GP Schema Theories47
4.1Rosca's Rooted Tree Schemata47
4.2Fixed-Size-and-Shape Schemata\ in GP49
4.3Point Mutation and One-Point Crossover in GP54
4.4Disruption-Survival GP Schema Theorem58
4.5Summary66
Chapter 5.Exact GP Schema Theorems67
5.1Criticisms of Schema Theorems67
5.2The Role of Schema Creation69
5.3Stephens and Waelbroeck's GA Schema Theory71
5.4GP Hyperschema Theory72
5.5Examples81
5.6Exact Schema Theorem for GP with Standard Crossover87
5.7Summary93
Chapter 6.Lessons from the GP Schema Theory95
6.1Effective Fitness95
6.2Operator Biases and Linkage Disequilibrium for Shapes103
6.3Building Blocks in GAs and GP105
6.4Practical Ideas Inspired by Schema Theories107
6.5Convergence, Population Sizing, GP Hardness and Deception108
6.6Summary109
Chapter 7.The Genetic Programming Search Space111
7.1Experimental Exploration of GP Search Spaces111
7.2Boolean Program Spaces112
7.3Symbolic Regression121
7.4Side Effects, Iteration, Mixed Arity: Artificial Ant122
7.5Less Formal Extensions125
7.6Tree Depth127
7.7Discussion128
7.8Summary 130
Chapter 8.The GP Search Space: Theoretical Analysis131
8.1Long Random Linear Programs131
8.2Big Random Tree Programs137
8.3XOR Program Spaces143
8.4Summary148
Chapter 9.Example I: The Artificial Ant149
9.1The Artificial Ant Problem149
9.2Size of Program and Solution Space152
9.3Solution of the Ant Problem155
9.4Fitness Landscape156
9.5Fixed Schema Analysis157
9.6The Solutions165
9.7Discussion166
9.8Reducing Deception168
9.9Summary169
Chapter 10.Example II: The Max Problem173
10.1The MAX Problem174
10.2GP Parameters174
10.3Results174
10.4Variety181
10.5Selection Pressure184
10.6Applying Price's Covariance and Selection Theorem187
10.7Summary190
Chapter 11.GP Convergence and Bloat191
11.1Convergence191
11.2Bloat195
11.3Subquadratic Bloat200
11.4Depth and Size Limits209
11.5Discussion210
11.6AntiBloat Techniques212
11.7Summary214
Chapter 12.Conclusions217
Appendix Genetic Programming Resources221
Bibliography 223
List of Special Symbols239
Glossary 245
Index 253

code Park & Miller pseudo random numbers, Santa Fe Ant trail (code and soloutions), ntrees.cc ntreeshapes.cc


W. B. Langdon (2001, last update 4 Oct 2012).