On the Limiting Distribution of Program Sizes in Tree-based Genetic Programming

We provide strong theoretical and experimental evidence that standard sub-tree crossover with uniform selection of crossover points pushes a population of a-ary GP trees towards a distribution of tree sizes of the form: Prn = (1 - ap)C_n^an + 1(1-p)^(a-1)n+1 p^n where n is the number of internal nodes in a tree and p is a constant. This result generalises the result previously reported in \citepoli:2001:EuroGP_exact, \citemcphee:2001:astamsbgplr, \citeRowe01, \citepoli03:ECJ_gener_schem_part_I, \citepoli03:ECJ_gener_schem_part_II for the case a = 1