Grammatical Evolution in Java (GEVA)

Category Intelligent Software>Genetic Programming Systems/Tools

Abstract GEVA is an open source implementation of Grammatical Evolution (GE) in Java developed at UCD’s Natural Computing Research & Applications group.

As well as providing the characteristic genotype-phenotype Mapper of GE, a search algorithm engine and a simple GUI are also provided. A number of sample problems and tutorials on how to use and adapt GEVA have also been developed.

Grammatical Evolution --

Grammatical Evolution (GE) is a grammar-based form of Genetic Programming (GP). It marries principles from molecular biology to the representational power of formal grammars.

GE’s rich modularity gives a unique flexibility, making it possible to use alternative search strategies, whether evolutionary, deterministic or some other approach, and to radically change its behavior by merely changing the grammar supplied.

As a grammar is used to describe the structures that are generated by GE, it is trivial to modify the output structures by simply editing the plain text grammar. This is one of the main advantages that make the GE approach so attractive.

The genotype-phenotype mapping also means that instead of operating exclusively on solution trees, as in standard Genetic Programming (GP), GE allows search operators to be performed on the genotype (e.g., integer or binary chromosomes), in addition to partially derived phenotypes, and the fully formed phenotypic derivation trees themselves.

GEVA Design Overview --

GEVA takes advantage of GE’s modular structure. This allows the user to create a framework in which any search engine algorithm can be used to generate the genotypes (the GEChromosome class) that are used to direct the GE Mapper’s use of the Grammar during the development of the output solution.

In recent years this approach has included the adoption of a Particle Swarm algorithm and Differential Evolution as alternative search engines resulting in Grammatical Swarm and Grammatical Differential Evolution variants.

GEVA facilitates the adoption of alternative search engines through the provision of an Algorithm interface.

This will work correctly as long as a GE Mapper object is provided with a legal GEChromosome object, so any alternative algorithm must ensure to map its search engine’s individual representation to a GEChromosome to generate an output solution.

In this first release of GEVA, a standard Genetic Algorithm (GA) engine is provided with plans to add alternative engines in future releases.

The current version uses individuals with (32-bit) integer codon values and adopts a corresponding integer mutation operator.

Grammars are made available to GEVA through plain text files that adopt Backus Naur Form (BNF) notation (BNF is a notation for expressing the grammar of a language in the form of production rules).

A simple parser is provided which handles standard BNF and can also recognize special symbols including GECodonValue, which returns the current codon’s numerical value as a terminal symbol to the developing output phenotype sentence.

Simply by altering the contents of a BNF text file you can radically change the output generated by GEVA.

A number of studies have illustrated this flexibility: for example, grammars have been used to represent a diverse array of structures including binary strings, code in various programming languages (e.g., C, Scheme, Slang, Postscript, etc.), music, financial trading rules, 3D surfaces, and even grammars themselves.

A number of demonstration grammars are provided in the example problems and are available through the graphical user interface (GUI) and from the command line.

GEVA additional information/documentation --

GEVA comes out-of-the-box with a number of demonstration problems (as stated above...) that can be easily switched between the GUI and command line.

Sample problems include simple String Pattern Matching, an LSystem generator, the Paint problem, and a number of classic Genetic Programming (GP) problems such as an example of Symbolic Regression, the Santa Fe ant trail and Even Five Parity.

When opened for the first time GEVA adopts the parameter settings for a pattern matching example problem where the goal is to rediscover the string “geva”.

Simple graphing support is also provided, which allows the user to observe various attributes of the population live, during the course of a run. The resulting graphs can then be saved for later use.

Attributes that can be plotted include the best fitness, the average fitness (with error bars), the number of invalid (incompletely mapped individuals), the average number of codons in each individual, and the average number of expressed codons in the population.

A number of tutorials have been developed to help the novice user get up to speed: from running the software out-of-the-box, to using the command-line parameters, writing your own grammars and fitness functions, to developing your own search engine.

These include a tutorial describing a bonus demo problem, Battleship, which the interested user can add to a GEVA installation.

System Requirements

Contact manufacturer.

Manufacturer

Manufacturer Web Site GEVA

Price Contact manufacturer.

G6G Abstract Number 20683

G6G Manufacturer Number 104261