Functional genetic programming and exhaustive program search with combinator expressions

Issue title: Genetic Programming An Emerging Engineering Tool

Article type: Research Article

Authors: Briggs, Forrest | O'Neill, Melissa

Affiliations: E-mail: [email protected]; [email protected]

Abstract: Using a strongly typed functional programming language for genetic programming has many advantages, but evolving functional programs with variables requires complex genetic operators with special cases to avoid creating ill-formed programs. We introduce combinator expressions as an alternative program representation for genetic programming, 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 representations for functional genetic programming and also offers insight into situations where exhaustive enumeration outperforms genetic programming and vice versa.

DOI: 10.3233/KES-2008-12105

Journal: International Journal of Knowledge-based and Intelligent Engineering Systems, vol. 12, no. 1, pp. 47-68, 2008