Recursion in tree-based genetic programming

Created by W.Langdon from gp-bibliography.bib Revision:1.4524

  author =       "Alexandros Agapitos and Michael O'Neill and 
                 Ahmed Kattan and Simon M. Lucas",
  title =        "Recursion in tree-based genetic programming",
  journal =      "Genetic Programming and Evolvable Machines",
  year =         "2017",
  volume =       "18",
  number =       "2",
  pages =        "149--183",
  month =        jun,
  keywords =     "genetic algorithms, genetic programming, Evolutionary
                 program synthesis Recursive programs, Variation
                 operators, Fitness landscape analysis",
  ISSN =         "1389-2576",
  DOI =          "doi:10.1007/s10710-016-9277-5",
  size =         "35 pages",
  abstract =     "Recursion is a powerful concept that enables a
                 solution to a problem to be expressed as a relatively
                 simple decomposition of the original problem into
                 sub-problems of the same type. We survey previous
                 research about the evolution of recursive programs in
                 tree-based Genetic Programming. We then present an
                 analysis of the fitness landscape of recursive
                 programs, and report results on evolving solutions to a
                 range of problems. We conclude with guidelines
                 concerning the choice of fitness function and variation
                 operators, as well as the handling of the halting
                 problem. The main findings are as follows. The
                 distribution of fitness changes initially as we look at
                 programs of increasing size but once some threshold has
                 been exceeded, it shows very little variation with
                 size. Furthermore, the proportion of halting programs
                 decreases as size increases. Recursive programs exhibit
                 the property of weak causality; small changes in
                 program structure may cause big changes in semantics.
                 Nevertheless, the evolution of recursive programs is
                 not a needle-in-a-haystack problem; the neighbourhoods
                 of optimal programs are populated by halting
                 individuals of intermediate fitness. Finally,
                 mutation-based variation operators performed the best
                 in finding recursive solutions. Evolution was also
                 shown to outperform random search.",
  notes =        "Factorial, Fibonacci, Exponentiation, Even-n-parity,

                 Random walks and error-distance correlation. Canberra
                 distance. (hard) limit of 10000 recursive calls. '..the
                 distribution of error is roughly independent of size'
                 BUT '..Even-n-parity and Nth in Fig. 4d,e do not show a
                 convergence..' 'Overall, our findings are in accordance
                 with simulation results published in
                 \cite{langdon:2006:eurogp}'. 'Fig. 4 Proportion of
                 halting programs (out of 2,000,000 programs) as a
                 function of program size' '..once programs containing
                 recursive nodes wither away from the population, it is
                 impossible to be introduced again.'",

Genetic Programming entries for Alexandros Agapitos Michael O'Neill Ahmed Kattan Simon M Lucas