Genetic programming (GP) has been highly successful as a technique for getting computers to automatically solve problems without having to tell them explicitly how to do it. Since its inception more than ten years ago genetic programming has been used to solve practical problems but along with this engineering approach there has been interest in how and why it works. This book consolidates this theoretical work.

One of the goals of any theoretical work is to better understand the subject. This is useful in its own right and as an aid to designing improvements. We will describe several new genetic operators that arose naturally from theoretical work and suggest modest changes to the way existing GP systems could be used on specific problems to yield improved performance. No doubt these operators and suggestions will be of direct practical interest, even to those who are not interested in ``theory'' for its own sake.

1. Artificial Intelligence can be seen as a cluster of islands in the sea. ai_map_top_view

Genetic programming is one of a wide range of evolutionary computation techniques, such as evolutionary strategies and evolutionary programming, being itself a descendent of one of the oldest, Genetic Algorithms (GAs). It is nice to be able to report in this book that theoretical results from the ``new boy'', GP, can be directly applied to GAs. Since GP is more expressive than GAs, it can be viewed as a generalisation of GAs. In the same way, GP theory is a generalisation of GA theory, although, in fact, some recent advances in GP theory came first and the corresponding GA theory was derived by specialising the more general GP theory. In effect we are getting GA theory for free, from the GP theory. In this way the various strands of evolutionary computation theory are themselves coming together (although convergence is some way off).

The title of our book has, itself, a genetic pedigree. Its direct ancestor is a workshop of the same name held at the first Genetic and Evolutionary Computation Conference, which we organised (together with Una-May O'Reilly, Justinian Rosca and Thomas Haynes) in July 1999, in Orlando. Prior to this (starting in 1990) there has been a long-running series of workshops called Foundations of Genetic Algorithms (FOGA). More generally, the inspiration for ``Foundations of Genetic Programming'' came from a panel called ``The next frontiers of AI: the role of foundations'', held at EPIA 1995. On that occasion Riccardo put forward the view that the foundations of Artificial Intelligence (AI) are fundamental principles which are common to all disciplines within AI, be they artificial neural networks, evolutionary computation, theorem proving, etc. (see Figures 1 and 2). The common feature of these techniques is search (although the representation being used to express solutions and the search used may be radically different). In our opinion search (be it deterministic or stochastic, complete or incomplete, blind, partially sighted, heuristic, etc.), the related representation, operators and objective functions are the foundations of AI. So Foundations of Genetic Programming should not be viewed only as a collection of techniques that one needs to know in order to be able to do GP well but also as a first attempt to chart and explore the mechanisms and fundamental principles behind genetic programming as a search algorithm. In writing this book we hoped to cast a tiny bit of light onto the theoretical foundations of Artificial Intelligence as a whole.

2. Artificial Intelligence can be seen as a cluster of islands in the sea
sharing a set of common foundations (cross-sectional view). ai_map_side_view


October 2001 W.B. Langdon Riccardo Poli

Back to table of contents

(last updated 16 Apr 2006)