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.

Preface | ||

Acknowledgements | ||

Chapter 1. | Introduction | 1 |

1.1 | Problem Solving as Search | 2 |

1.2 | What is Genetic Programming? | 9 |

1.3 | Outline of the Book | 15 |

Chapter 2. | Fitness Landscapes | 17 |

2.1 | Exhaustive Search | 17 |

2.2 | Hill Climbing | 17 |

2.3 | Fitness Landscapes as Models of Problem Difficulty | 19 |

2.4 | An Example GP Fitness Landscape | 20 |

2.5 | Other Search Strategies | 21 |

2.6 | Difficulties with the Fitness Landscape Metaphor | 23 |

2.7 | Effect of Representation Changes | 25 |

2.8 | Summary | 26 |

Chapter 3. | Program Component Schema Theories | 27 |

3.1 | Price's Selection and Covariance Theorem | 28 |

3.2 | Genetic Algorithm Schemata | 33 |

3.3 | From GA Schemata\ to GP Schemata | 35 |

3.4 | Koza's Genetic Programming Schemata | 38 |

3.5 | Altenberg's GP Schema Theory | 39 |

3.6 | O'Reilly's Genetic Programming Schemata | 42 |

3.7 | Whigham's Genetic Programming Schemata | 44 |

3.8 | Summary | 46 |

Chapter 4. | Pessimistic GP Schema Theories | 47 |

4.1 | Rosca's Rooted Tree Schemata | 47 |

4.2 | Fixed-Size-and-Shape Schemata\ in GP | 49 |

4.3 | Point Mutation and One-Point Crossover in GP | 54 |

4.4 | Disruption-Survival GP Schema Theorem | 58 |

4.5 | Summary | 66 |

Chapter 5. | Exact GP Schema Theorems | 67 |

5.1 | Criticisms of Schema Theorems | 67 |

5.2 | The Role of Schema Creation | 69 |

5.3 | Stephens and Waelbroeck's GA Schema Theory | 71 |

5.4 | GP Hyperschema Theory | 72 |

5.5 | Examples | 81 |

5.6 | Exact Schema Theorem for GP with Standard Crossover | 87 |

5.7 | Summary | 93 |

Chapter 6. | Lessons from the GP Schema Theory | 95 |

6.1 | Effective Fitness | 95 |

6.2 | Operator Biases and Linkage Disequilibrium for Shapes | 103 |

6.3 | Building Blocks in GAs and GP | 105 |

6.4 | Practical Ideas Inspired by Schema Theories | 107 |

6.5 | Convergence, Population Sizing, GP Hardness and Deception | 108 |

6.6 | Summary | 109 |

Chapter 7. | The Genetic Programming Search Space | 111 |

7.1 | Experimental Exploration of GP Search Spaces | 111 |

7.2 | Boolean Program Spaces | 112 |

7.3 | Symbolic Regression | 121 |

7.4 | Side Effects, Iteration, Mixed Arity: Artificial Ant | 122 |

7.5 | Less Formal Extensions | 125 |

7.6 | Tree Depth | 127 |

7.7 | Discussion | 128 |

7.8 | Summary | 130 |

Chapter 8. | The GP Search Space: Theoretical Analysis | 131 |

8.1 | Long Random Linear Programs | 131 |

8.2 | Big Random Tree Programs | 137 |

8.3 | XOR Program Spaces | 143 |

8.4 | Summary | 148 |

Chapter 9. | Example I: The Artificial Ant | 149 |

9.1 | The Artificial Ant Problem | 149 |

9.2 | Size of Program and Solution Space | 152 |

9.3 | Solution of the Ant Problem | 155 |

9.4 | Fitness Landscape | 156 |

9.5 | Fixed Schema Analysis | 157 |

9.6 | The Solutions | 165 |

9.7 | Discussion | 166 |

9.8 | Reducing Deception | 168 |

9.9 | Summary | 169 |

Chapter 10. | Example II: The Max Problem | 173 |

10.1 | The MAX Problem | 174 |

10.2 | GP Parameters | 174 |

10.3 | Results | 174 |

10.4 | Variety | 181 |

10.5 | Selection Pressure | 184 |

10.6 | Applying Price's Covariance and Selection Theorem | 187 |

10.7 | Summary | 190 |

Chapter 11. | GP Convergence and Bloat | 191 |

11.1 | Convergence | 191 |

11.2 | Bloat | 195 |

11.3 | Subquadratic Bloat | 200 |

11.4 | Depth and Size Limits | 209 |

11.5 | Discussion | 210 |

11.6 | AntiBloat Techniques | 212 |

11.7 | Summary | 214 |

Chapter 12. | Conclusions | 217 |

Appendix | Genetic Programming Resources | 221 |

Bibliography | 223 | |

List of Special Symbols | 239 | |

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).