Exact schema theorem and effective fitness for GP with one-point crossover
Riccardo Poli · 2000
This paper extends recent results in the GP schema theory by formulating a proper exact schema theorem for GP with one-point crossover. This gives an exact expression for the expected number of instances of a schema at the next generation in terms of macroscopic quantities. This result allows the exact formulation of the notion of effective fitness in GP. 1 INTRODUCTION Schemata are traditionally used to explain why GAs and more recently GP work [1, 2, 3, 4, 5]. Schemata are similarity templates representing sets of points in the search space. Schema theorems are descriptions of how the number of members of the population belonging to a schema vary over time [6]. The usefulness of schema theorems has been often criticised on the basis that they give only a lower bound for the expected value of the number of instances of a schema H at the next generation E[m(H; t + 1)]. The presence of the expectation operator means that it is not easy to use the theorems to predict the behavi...