Foundations of Genetic Programming

by Langdon, William B.; Poli, Riccardo

• ISBN13: 9783540424512
• ISBN10: 3540424512
• Format: Hardcover
• Copyright: 2001-10-01
• Publisher: Springer-Nature New York Inc

Summary

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.

Table of Contents

Introduction	1	(16)
Problem Solving as Search	2	(7)
Microscopic Dynamical System Models	4	(1)
Fitness Landscapes	4	(2)
Component Analysis	6	(1)
Schema Theories	7	(1)
No Free Lunch Theorems	8	(1)
What is Genetic Programming?	9	(6)
Tree-based Genetic Programming	10	(1)
Modular and Multiple Tree Genetic Programming	11	(2)
Linear Genetic Programming	13	(1)
Graphical Genetic Programming	14	(1)
Outline of the Book	15	(2)
Fitness Landscapes	17	(10)
Exhaustive Search	17	(1)
Hill Climbing	17	(2)
Fitness Landscapes as Models of Problem Difficulty	19	(1)
An Example GP Fitness Landscape	20	(1)
Other Search Strategies	21	(2)
Difficulties with the Fitness Landscape Metaphor	23	(2)
Effect of Representation Changes	25	(1)
Summary	26	(1)
Program Component Schema Theories	27	(22)
Price's Selection and Covariance Theorem	28	(5)
Proof of Price's Theorem	29	(2)
Price's Theorem for Genetic Algorithms	31	(1)
Price's Theorem with Tournament Selection	31	(1)
Applicability of Price's Theorem to GAs and GPs	32	(1)
Genetic Algorithm Schemata	33	(2)
From GA Schemata to GP Schemata	35	(3)
Koza's Genetic Programming Schemata	38	(1)
Altenberg's GP Schema Theory	39	(4)
O'Reilly's Genetic Programming Schemata	43	(2)
Whigham's Genetic Programming Schemata	45	(1)
Summary	46	(3)
Pessimistic GP Schema Theories	49	(20)
Rosca's Rooted Tree Schemata	49	(2)
Fixed-Size-and-Shape Schemata in GP	51	(5)
Point Mutation and One-Point Crossover in GP	56	(4)
Disruption-Survival GP Schema Theorem	60	(8)
Effect of Fitness Proportionate Selection	60	(1)
Effect of One-Point Crossover	61	(4)
Effect of Point Mutation	65	(1)
GP Fixed-size-and-shape Schema Theorem	65	(1)
Discussion	66	(1)
Early Stages of a GP Run	66	(1)
Late Stages of a GP Run	67	(1)
Interpretation	68	(1)
Summary	68	(1)
Exact GP Schema Theorems	69	(28)
Criticisms of Schema Theorems	69	(2)
The Role of Schema Creation	71	(2)
Stephens and Waelbroeck's GA Schema Theory	73	(1)
GP Hyperschema Theory	74	(9)
Theory for Programs of Fixed Size and Shape	74	(3)
Hyperschemata	77	(1)
Microscopic Exact GP Schema Theorem	77	(3)
Macroscopic Schema Theorem with Schema Creation	80	(2)
Macroscopic Exact GP Schema Theorem	82	(1)
Examples	83	(6)
Linear Trees	83	(4)
Comparison of Bounds by Different Schema Theorems	87	(2)
Example of Schema Equation for Binary Trees	89	(1)
Exact Macroscopic Schema Theorem for GP with Standard Crossover	89	(6)
Cartesian Node Reference Systems	90	(1)
Variable Arity Hyperschema	91	(1)
Macroscopic Exact Schema Theorem for GP with Standard Crossover	92	(3)
Summary	95	(2)
Lessons from the GP Schema Theory	97	(16)
Effective Fitness	97	(8)
Goldberg's Operator-Adjusted Fitness in GAs	97	(1)
Nordin and Banzhaf's Effective Fitness in GP	98	(1)
Stevens and Waelbroeck's Effective Fitness in GAs	99	(1)
Exact Effective Fitness for GP	100	(1)
Understanding GP Phenomena with Effective Fitness	100	(5)
Operator Biases and Linkage Disequilibrium for Shapes	105	(2)
Building Blocks in GAs and GP	107	(2)
Practical Ideas Inspired by Schema Theories	109	(1)
Convergence, Population Sizing, GP Hardness and Deception	110	(1)
Summary	111	(2)
The Genetic Programming Search Space	113	(20)
Experimental Exploration of GP Search Spaces	113	(1)
Boolean Program Spaces	114	(9)
NAND Program Spaces	114	(5)
Three-Input Boolean Program Spaces	119	(1)
Six-Input Boolean Program Spaces	119	(4)
Full Trees	123	(1)
Symbolic Regression	123	(1)
Sextic Polynomial Fitness Function	124	(1)
Sextic Polynomial Fitness Distribution	124	(1)
Side Effects, Iteration, Mixed Arity: Artificial Ant	124	(3)
Less Formal Extensions	127	(2)
Automatically Defined Function	127	(1)
Memory	128	(1)
Turing-Complete Programs	128	(1)
Tree Depth	129	(1)
Discussion	130	(2)
Random Trees	130	(1)
Genetic Programming and Random Search	131	(1)
Searching Large Programs	131	(1)
Implications for GP	131	(1)
Conclusions	132	(1)
The GP Search Space: Theoretical Analysis	133	(18)
Long Random Linear Programs	133	(6)
An Illustrative Example	135	(1)
Rate of Convergence and the Threshold	136	(2)
Random Functions	138	(1)
The Chance of Finding a Solution	139	(1)
Big Random Tree Programs	139	(6)
Setting up the Proof for Trees	139	(3)
Large Binary Trees	142	(1)
An Illustrative Example	143	(1)
The Chance of Finding a Solution	144	(1)
A Second Illustrative Example	144	(1)
XOR Program Spaces	145	(5)
Parity Program Spaces	145	(1)
The Number of Parity Solutions	146	(2)
Parity Problems Landscapes and Building Blocks	148	(2)
Conclusions	150	(1)
The Artificial Ant	151	(24)
The Artificial Ant Problem	151	(3)
Size of Program and Solution Space	154	(3)
Solution of the Ant Problem	157	(1)
Uniform Random Search	157	(1)
Ramped Half-and-Half Random Search	157	(1)
Comparison with Other Methods	158	(1)
Fitness Landscape	158	(1)
Fixed Schema Analysis	159	(8)
Competition Between Programs of Different Sizes	160	(2)
Competition Between Programs of Size 11	162	(1)
Competition Between Programs of Size 12	163	(1)
Competition Between Programs of Size 13	164	(3)
The Solutions	167	(1)
Discussion	168	(2)
Reducing Deception	170	(1)
Conclusions	171	(4)
The Max Problem	175	(18)
The MAX Problem	176	(1)
GP Parameters	176	(1)
Results	176	(7)
Impact of Depth Restriction on Crossover	178	(1)
Trapping by Suboptimal Solutions	178	(1)
Modelling the Rate of Improvement	179	(3)
Number of Steps to Climb the Hill	182	(1)
Variety	183	(3)
Variety in the Initial Population	183	(1)
Evolution of Variety	184	(1)
Modelling Variety	185	(1)
Selection Pressure	186	(3)
Applying Price's Covariance and Selection Theorem	189	(3)
Conclusions	192	(1)
GP Convergence and Bloat	193	(26)
Convergence	193	(4)
Bloat	197	(5)
Examples of Bloat	198	(1)
Convergence of Phenotype	198	(1)
Theories of Bloat	199	(2)
Fitness Variation is Needed for Bloat	201	(1)
Subquadratic Bloat	202	(9)
Evolution of Program Shapes	203	(3)
Experiments	206	(1)
Results	207	(4)
Convergence	211	(1)
Depth and Size Limits	211	(1)
Discussion	212	(2)
AntiBloat Techniques	214	(2)
Conclusions	216	(3)
Conclusions	219	(4)
Genetic Programming Resources	223	(2)
Bibliography	225	(16)
List of Special Symbols	241	(6)
Glossary	247	(8)
Index	255