Exact Schema Theorems for GP with One-Point and
Standard Crossover Operating on Linear Structures and
their Application to the Study of the Evolution of
Size
Genetic Programming, Proceedings of EuroGP'2001, volume 2038 of LNCS, page 126--142. Lake Como, Italy, Springer-Verlag, (18-20 April 2001)Abstract
In this paper, firstly we specialise the exact GP
schema theorem for one-point crossover to the case of
linear structures of variable length, for example
binary strings or programs with arity-1 primitives
only. Secondly, we extend this to an exact schema
theorem for GP with standard crossover applicable to
the case of linear structures. Then we study, both
mathematically and numerically, the schema equations
and their fixed points for infinite populations for
both a constant and a length-related fitness function.
This allows us to characterise the bias induced by
standard crossover. This is very peculiar. In the case
of a constant fitness function, at the fixed-point,
structures of any length are present with non-zero
probability. However, shorter structures are sampled
exponentially much more frequently than longer ones.
Links and resources
Tags
community
@brazovayeye's tags highlighted