Research Repository

Recursion in tree-based genetic programming

Agapitos, Alexandros and O’Neill, Michael and Kattan, Ahmed and Lucas, Simon M (2017) 'Recursion in tree-based genetic programming.' Genetic Programming and Evolvable Machines, 18 (2). pp. 149-183. ISSN 1389-2576

Full text not available from this repository.


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.

Item Type: Article
Uncontrolled Keywords: Evolutionary program synthesis; Genetic programming; Recursive programs; Variation operators; Fitness landscape analysis
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Faculty of Science and Health
Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 13 Dec 2016 21:12
Last Modified: 18 Aug 2022 11:42

Actions (login required)

View Item View Item