GED

Overview

GED is an attempt at grammatical evolution. Grammatical evolution is similar to genetic programming, but it is able to generate code in any arbitrary language. The actual genome representation for a generated program or algorithm is merely a sequence of 8-bit codons. Each codon represents a choice to make in a BNF for the language the final program is to be written and tested in.

Progress

• BNF specification pretty much works.
• Program generation from genome works.

Todo

• Add the ability to specify the probability for the different BNF forms.
• Add identifier scoping to BNF library.
• Add mutation functions for genomes.

More to be determined as I go.

Samples

GED is still early in its development, but here is the BNF for a simple expression generator as used in code. Yes, I know one of the expression forms is repeated. This is necessary to keep the the average recursion depth low until I make it possible to explicitly give probabilities.

auto preop = new Nonterminal();
auto op = new Nonterminal();
auto expr = new Nonterminal();
expr  (expr ) ( op  ) (expr )                 ;
expr  ( "(" ) (expr ) ( op  ) (expr ) ( ")" ) ;
expr  (preop) ( "(" ) (expr ) ( ")" )         ;
expr  ( "x" )                                 ;
expr  ( "x" )                                 ;
expr  ( "x" )                                 ;
op    ( "+" )                                 ;
op    ( "-" )                                 ;
op    ( "*" )                                 ;
op    ( "/" )                                 ;
preop ("sin")                                 ;
preop ("cos")                                 ;
preop ("tan")                                 ;

And here are a few examples of expressions generated using the above BNF in this early version of GED:

cos(cos(x))*x/x

sin(tan(x))

x+((x+x-(((x-x)*sin(sin(x/x)))+cos(x)/x))/(((x+x/x)+x)*sin(x/(x*x))))/sin(sin(x))

((cos(x)*cos(x))+x)