Foundations of genetic programming

Authors William B. Langdon, Riccardo Poli

Publication date 5 November 2001

automatic programming evolutionary search algorithms genetic programming

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) (68N19) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Review text

The content of that book is based on two assumptions: a) Development of computer programs is comparable to the growth of animals or plants based on its genes. b) Problem solving can be led back on search certain spaces. After an explanation of the idea of Genetic Programming (GP), fitness landscapes are discussed as notation's form in order to visualize the dynamics in evolutionary search algorithms. Chapter 3 describes ways of analyzing evolution by looking at the propagation of components within the programs rather than the individual programs themselves. This can be likened to `Selfish Gene' theory of evolution by Dawkins (1976). Early genetic programming schema theorems. Such as those to Koza Altenberg, O'Relly and Whigham, fall into this category, which makes them different from the traditional genetic algorithm schema theory. Schema theorems make predictions for the average behaviour of the population at the next generation. Chapter 4 looks at GP schema theorems (such as those due to Poli and Rosca) which provide lower bounds on schema proportions. Like Holland's schema theorem, these do not include the fact that genetic operators can create new instances of schemata as well as deleting them. Therefore in the book is referred to them as `pessimistic' schema theories. However, chapter 5 describes `exact' schema theories which do make allowance for schema creation. Chapter 6 concludes the presentation of the GP schema theorems by bringing together their implications. In chapter 7 is token a different point of view, by considering the GP search space and how it varies with the size and shape of programs. Some widely applicable results are presented. The formal proofs are presented in chapter 8. Chapters 9, 10 and 11 discuss a detailed analysis of two benchmark GP problems and consider bloat within GP. The analysis uses component analysis tools of chapter 3, the schema theorems of chapters 4-6 and the search space analysis of chapter 7. Finally, while each chapter finishes with a summary of the results contained within it, chapter 12 gives the overall conclusions and indications of how the theoretical foundations of genetic programming may continue to develop. Appendix A gives some pointers to other sources of information on genetic programming, especially those available via Internet.

Recommendations

Cited in

(70)

This page was built for publication: Foundations of genetic programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2754885)