GED

From Makers Local 256
Jump to: navigation, search

Creator:
Jmcarthur
Status:
Retired
Born On:
12 March 2007
Last Updated:
28 July 2009

This project has been replaced by Grammatical evolution engine.

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.
  • Add a pool evolver for keeping track of fitnesses and breeding the most fit genomes.
  • Try it out with a whole bunch of situations.
  • Look into generating more complex programs/algorithms with object-oriented design, an area not well-tread in evolutionary programming.

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)

References