Complexity Drift in Evolutionary Computation with Tree Representations

One serious problem of standard Genetic Programming (GP) is that evolved expressions appear to drift towards large and slow forms on average. This report 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 representations. A tree-schema is a relation on the space of tree-shaped structures which provides a quantifiable partitioning of the search space. The present analysis answers questions such as: What role does variable complexity play in the selection and survival of evolved expressions? What is the influence of a parsimony penalty? How heavy should parsimony penalty be weighted or how should it be adapted in order to preserve the underlying optimization process? Are there alternative approaches to simulating a parsimony penalty that do not result in a change of the fitness landscape? The present report provides theoretical answers to these questions, interpretation of these results, and an experimental perspective