Evolving encapsulated programs as shared grammars
Facilitating the discovery and reuse of modular building blocks is generally regarded as the key to achieving better scalability in genetic programming (GP). A precedent for this exists in biology, where complex designs are the product of developmental processes that can also be abstractly modeled as generative grammars. We introduce shared grammar evolution (SGE), which aligns grammatical development with the common application of grammars in GP as a means of establishing declarative bias. Programs are derived from and represented by a global context-free grammar that is transformed and extended according to another, user-defined grammar. Grammatical productions and the subroutines they encapsulate are shared between programs, which enables their reuse without reevaluation and can significantly reduce total evaluation time for large programs and populations. Several variants of SGE employing different strategies for controlling solution size and diversity are tested on classic GP problems. Results compare favorably against GP and newer techniques, with the best results obtained by promoting diversity between derived programs.
encapsulation shared grammars modularity genetic programming grammatical evolution developmental systems memoization