Functional Genetic Programming and Exhaustive Program Search with Combinator Expressions

Using a strongly typed functional programming language for genetic programming has many advantages, but evolving functional programs with variables requires complex ge-netic operators with special cases to avoid creating ill-formed programs. We introduce combinator expressions as an alternative program representation for genetic program-ming, providing the same expressive power as strongly typed functional programs, but in a simpler format that avoids variables and other syntactic clutter. We outline a complete genetic-programming system based on combinator expressions, including a novel generalized genetic operator, and also show how it is possible to exhaustively enumerate all well-typed combinator expressions up to a given size. Our experimental evidence shows that combinator expressions compare favorably with prior representa-tions for functional genetic programming and also offers insight into situations where exhaustive enumeration outperforms genetic programming and vice versa.