TY - GEN
T1 - 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
AU - Poli, Riccardo
AU - McPhee, Nicholas Freitag
PY - 2001
Y1 - 2001
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84937428414&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84937428414&partnerID=8YFLogxK
U2 - 10.1007/3-540-45355-5_11
DO - 10.1007/3-540-45355-5_11
M3 - Conference contribution
AN - SCOPUS:84937428414
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 126
EP - 142
BT - Genetic Programming - 4th European Conference, EuroGP 2001, Proceedings
A2 - Miller, Julian
A2 - Tomassini, Marco
A2 - Lanzi, Pier Luca
A2 - Ryan, Conor
A2 - Tettamanzi, Andrea G.B.
A2 - Langdon, William B.
PB - Springer Verlag
T2 - 4th European Conference on Genetic Programming, EuroGP 2001
Y2 - 18 April 2001 through 20 April 2001
ER -