Grammatical Evolution

This chapter describes Grammatical Evolution (GE) in detail (Ryan et al., 1998; O’Neill and Ryan, 2001; O’Neill, 2001). We show that it is an evolutionary algorithm (EA) that can evolve complete programs in an arbitrary language using a variable-length binary string. The binary genome determines which production rules in a Backus Naur Form (BNF) grammar definition are used in a genotype-to-phenotype mapping process to a program. GE is set up such that the evolutionary algorithm is independent of the output programs by virtue of the genotype-phenotype mapping, allowing GE to take advantage of advances in EA research. The BNF grammar, like the EA, is a plug-in component of the system that determines the syntax and language of the output code, hence, it is possible to evolve programs in an arbitrary language.