An Experimental Analysis of Schema Creation, Propagation and Disruption in Genetic Programming
Riccardo Poli, William B. Langdon · 1997
In this paper we first review the main results in the theory of schemata in Genetic Programming (GP) and summarise a new GP schema theory which is based on a new definition of schema. Then we study the creation, propagation and disruption of this new form of schemata in real runs, for standard crossover, one-point crossover and selection only. Finally, we discuss these results in the light our GP schema theorem. 1 Introduction Genetic Programming (GP) has been applied successfully to a large number of difficult problems [Koza, 1992, K. E. Kinnear, Jr., 1994, Angeline and Kinnear, Jr., 1996]. However a relatively small number of theoretical results are available to try and explain why and how it works. Since John Holland's seminal work in the mid seventies and his well known schema theorem (see [Holland, 1992] and [Goldberg, 1989]), schemata are often used to explain why GAs work (although their usefulness has been recently criticised, e.g. in [Altenberg, 1995]). In particular it is be...