Boosting Search for Recursive Functions Using Partial Call-Trees

Brad Alexander and Brad Zacher

Abstract. Recursive functions are a compact and expressive way to solve challenging problems in terms of local processing. These properties have made recursive functions a popular target for genetic programming. Unfortunately, the evolution of substantial recursive programs has proven difficult. One cause of this problem is the difficulty in evolving both correct base and recursive cases using just information derived from running test cases. In this work we describe a framework that exploits additional information in the form of partial call-trees. Such trees - a by-product of deriving input-output cases by hand - guides the search process by allowing the separate evolution of the recursive case. We show that the speed of evolution of recursive functions is significantly enhanced by the use of partial call-trees and demonstrate application of the technique in the derivation of functions for a suite of numerical functions.

Keywords: Recursion, Genetic Programming, Call-Tree, Adaptive Grammar

LNCS 8672, p. 384 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer International Publishing Switzerland 2014