An Arithmetic Test Suite for Genetic Programming

In this paper we explore a number of ideas for enhancing the techniques of genetic programming in the context of a very simple test environment that nevertheless possesses some degree of algorithmic subtlety. We term this genetic programming environment plus-one-recall-store (PORS). This genetic programming environment is quite simple having only a pair of terminals and a pair of operations. The terminals are the number one and recall from an external memory. The operations are a unary store operation and binary addition, +, on natural numbers. In this paper we present the PORS environment, present a mathematical description of its properties, and then focus on testing the use of Markov chains in generating, crossing over, and mutating evolving programs. We obtain a surprising indication of the correct situations in which to use Markov chains during evolutionary program induction