Analysis of Complexity Drift in Genetic Programming

One serious problem of standard Genetic Programming (GP) is that evolved structures appear to drift towards large and slow forms on average. This paper presents a novel analysis of the role played by variable complexity in the selection and survival of GP expressions. It defines a particular property of GP representations, called rooted tree-schema, that sheds light on the role of variable complexity of evolved structures. A rooted tree-schema is a relation on the space of tree-shaped structures which provides a quantifiable partitioning of the search space. The paper analyzes the influence of parsimony pressure on selection and growth of structures. Experimental evidence confirms theoretical predictions. 1 Introduction Genetic programming (GP) uses open-ended complexity representations of flexible semantics (Koza1992). GP evolves a population of expressions in some problem dependent language that encode problem solutions. Evolved expressions are tree structured and can be interpret..