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
R. Poli, und N. McPhee. Genetic Programming, Proceedings of EuroGP'2001, Volume 2038 von LNCS, Seite 126--142. Lake Como, Italy, Springer-Verlag, (18-20 April 2001)
Zusammenfassung
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.
%0 Conference Paper
%1 poli:2001:EuroGP_exact
%A Poli, Riccardo
%A McPhee, Nicholas Freitag
%B Genetic Programming, Proceedings of EuroGP'2001
%C Lake Como, Italy
%D 2001
%E Miller, Julian F.
%E Tomassini, Marco
%E Lanzi, Pier Luca
%E Ryan, Conor
%E Tettamanzi, Andrea G. B.
%E Langdon, William B.
%I Springer-Verlag
%K Algorithms, Crossover Crossover, Fixed Genetic Schema Standard Variable-length algorithms, bias, genetic points, programming, theory,
%P 126--142
%T 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
%U http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2038&spage=126
%V 2038
%X 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.
%@ 3-540-41899-7
@inproceedings{poli:2001:EuroGP_exact,
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.},
added-at = {2008-06-19T17:46:40.000+0200},
address = {Lake Como, Italy},
author = {Poli, Riccardo and McPhee, Nicholas Freitag},
biburl = {https://www.bibsonomy.org/bibtex/25c6b51613928b782c6da0283cdb256c4/brazovayeye},
booktitle = {Genetic Programming, Proceedings of EuroGP'2001},
editor = {Miller, Julian F. and Tomassini, Marco and Lanzi, Pier Luca and Ryan, Conor and Tettamanzi, Andrea G. B. and Langdon, William B.},
interhash = {be95b45f70af1e177b1a59088b77043c},
intrahash = {5c6b51613928b782c6da0283cdb256c4},
isbn = {3-540-41899-7},
keywords = {Algorithms, Crossover Crossover, Fixed Genetic Schema Standard Variable-length algorithms, bias, genetic points, programming, theory,},
month = {18-20 April},
notes = {EuroGP'2001, part of \cite{miller:2001:gp}},
organisation = {EvoNET},
pages = {126--142},
publisher = {Springer-Verlag},
publisher_address = {Berlin},
series = {LNCS},
size = {17 pages},
timestamp = {2008-06-19T17:49:44.000+0200},
title = {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},
url = {http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2038&spage=126},
volume = 2038,
year = 2001
}