We have described a system, Grammatical Evolution (GE) that can map a binary genotype onto a phenotype which is a high level program. Because our mapping technique employs a BNF definition, the system is language independant, and, theoretically can generate arbitrarily complex functions.
We believe GE to have closer biological analogies to nature than GP, particularly with its use of linear genomes and the manner in which it uses proteins to affect traits. Other schemes tend to use either the direct evolution of physical traits or the use of simple one to one mappings from genotype to phenotypic traits.
This paper serves an introduction to GE. We believe there is great promise to the system, and that the ability to evolve any high level language would surely be a huge boost for Evolutionary Algorithms, both in terms of increased usage and acceptance, and in terms of the complexity of the problems it can tackle.
Using BNF definitions, it is possible to evolve multi line functions; these functions can even declare local variables and use other high level constructs such as loops. The next step is to apply GE to a problem that requires such constructs.
Although GE is quite different from the functional nature GP, in both its structure and its aims, there is still quite a lot of similarity. We hope that GE will be able to benefit from the huge amount of work already carried out on GP, particularly in the fundamentals, i.e. ADFS, indexed memory, etc. many of which can be coded in BNF with relative ease.