- 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,
Nth
ftp://ftp.cs.ucl.ac.uk/genetic/gp-code/rand_tree.cc 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.'",
