Genetic programming with polymorphic types and higher-order functions

This article introduces our new approach to program representation for genetic programming (GP). We replace the usual s-expression representation scheme by a strongly-typed abstraction-based representation scheme. This allows us to represent many typical computational structures by abstractions rather than by functions defined in the GP system's terminal set. The result is a generic GP system that is able to express programming structures such as recursion and data types without explicit definitions. We demonstrate the expressive power of this approach by evolving simple boolean programs without defining a set of terminals. We also evolve programs that exhibit recursive behavior without explicitly defining recursion specific syntax in the terminal set. In this article, we present our approach and experimental results.