Difference between revisions of "GED"
From Makers Local 256
m (minor edit) |
m (fixed username) |
||
| (9 intermediate revisions by one user not shown) | |||
| Line 1: | Line 1: | ||
| + | {{Project|Creator=Jmcarthur | ||
| + | |Status=<onlyinclude>Retired</onlyinclude><!--LEAVE ONLYINCLUDES FOR STATUS HACK--> | ||
| + | |Born On=12 March 2007<!--DO NOT EDIT --> | ||
| + | |Last Updated={{#time: d F Y| {{REVISIONTIMESTAMP}} }}<!--DO NOT EDIT --> | ||
| + | }} | ||
| + | |||
| + | This project has been replaced by [[Grammatical evolution engine]]. | ||
| + | |||
== Overview == | == 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. | + | 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 [http://en.wikipedia.org/wiki/Backus–Naur_form BNF] for the language the final program is to be written and tested in. |
== Progress == | == 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. | ||
| + | |||
| + | <pre>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") ; | ||
| + | </pre> | ||
| + | |||
| + | And here are a few examples of expressions generated using the above BNF in this early version of GED: | ||
| + | |||
| + | <pre>cos(cos(x))*x/x</pre> | ||
| + | <pre>sin(tan(x))</pre> | ||
| + | <pre>x+((x+x-(((x-x)*sin(sin(x/x)))+cos(x)/x))/(((x+x/x)+x)*sin(x/(x*x))))/sin(sin(x))</pre> | ||
| + | <pre>((cos(x)*cos(x))+x)</pre> | ||
| + | |||
| + | == References == | ||
| + | |||
| + | * [http://en.wikipedia.org/wiki/Grammatical_evolution Wikipedia article on grammatical evolution] | ||
| + | * [http://www.grammaticalevolution.org/tutorial.pdf Slides on some grammatical evolution research] | ||
| + | |||
| − | + | [[Category:Software]] | |
| + | [[Category:Research]] | ||
Latest revision as of 17:30, 28 July 2009
|
Creator: |
This project has been replaced by Grammatical evolution engine.
Contents
[hide]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)
