Genetic Programming with Primitive Recursion

When Genetic Programming is used to evolve arithmetic functions it often operates by composing them from a fixed collection of elementary operators and applying them to parameters or certain primitive constants. This limits the expressiveness of the programs that can be evolved. It is possible to extend the expressiveness of such an approach significantly without leaving the comfort of terminating programs by including primitive recursion as a control operation.The technique used here was gene expression programming [2], a variation of grammatical evolution [8]. Grammatical evolution avoids the problem of program bloat; its separation of genotype (string of symbols) and phenotype (expression tree) permits to optimise the generated programs without interfering with the evolutionary process.