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

Riccardo Poli, Nicholas Freitag McPhee

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    20 Scopus citations

    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.

    Original languageEnglish (US)
    Title of host publicationGenetic Programming - 4th European Conference, EuroGP 2001, Proceedings
    EditorsJulian Miller, Marco Tomassini, Pier Luca Lanzi, Conor Ryan, Andrea G.B. Tettamanzi, William B. Langdon
    PublisherSpringer Verlag
    Pages126-142
    Number of pages17
    ISBN (Electronic)3540418997, 9783540418993
    DOIs
    StatePublished - 2001
    Event4th European Conference on Genetic Programming, EuroGP 2001 - Lake Como, Italy
    Duration: Apr 18 2001Apr 20 2001

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume2038
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference4th European Conference on Genetic Programming, EuroGP 2001
    CountryItaly
    CityLake Como
    Period4/18/014/20/01

    Fingerprint Dive into the research topics of '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'. Together they form a unique fingerprint.

    Cite this