Foundations of Genetic Programming

Genetic programming (GP), one of the most advanced forms of evolutionary computation, has been highly successful as a technique for getting computers to automatically solve problems without having to tell them explicitly how. Since its inceptions more than ten years ago, GP has been used to solve practical problems in a variety of application fields. Along with this ad-hoc engineering approaches interest increased in how and why GP works. This book provides a coherent consolidation of recent work on the theoretical foundations of GP. A concise introduction to GP and genetic algorithms (GA) is followed by a discussion of fitness landscapes and other theoretical approaches to natural and artificial evolution. Having surveyed early approaches to GP theory it presents new exact schema analysis, showing that it applies to GP as well as to the simpler GAs. New results on the potentially infinite number of possible programs are followed by two chapters applying these new techniques.

This is one of the only books to provide a complete and coherent review of the theory of genetic programming (GP). In doing so, it provides a coherent consolidation of recent work on the theoretical foundations of GP. A concise introduction to GP and genetic algorithms (GA) is followed by a discussion of fitness landscapes and other theoretical approaches to natural and artificial evolution. Having surveyed early approaches to GP theory it presents new exact schema analysis, showing that it applies to GP as well as to the simpler GAs. New results on the potentially infinite number of possible programs are followed by two chapters applying these new techniques.

Front Matter....Pages I-XV Introduction....Pages 1-16 Fitness Landscapes....Pages 17-26 Program Component Schema Theories....Pages 27-47 Pessimistic GP Schema Theories....Pages 49-68 Exact GP Schema Theorems....Pages 69-95 Lessons from the GP Schema Theory....Pages 97-111 The Genetic Programming Search Space....Pages 113-132 The GP Search Space: Theoretical Analysis....Pages 133-150 Example I: The Artificial Ant....Pages 151-174 Example II: The Max Problem....Pages 175-192 GP Convergence and Bloat....Pages 193-217 Conclusions....Pages 219-221 Back Matter....Pages 223-260