Grammatical evolution
Encyclopedia
Grammatical evolution is a relatively new evolutionary computation
technique pioneered by Conor Ryan, JJ Collins and Michael O'Neill in 1998 at the BDS Group in the University of Limerick
.
It is related to the idea of genetic programming
in that the objective is to find an executable program or program fragment, that will achieve a good fitness value for the given objective function. In most published work on Genetic Programming, a LISP
-style tree-structured expression is directly manipulated, whereas Grammatical Evolution applies genetic operator
s to an integer string, subsequently mapped to a program (or similar) through the use of a grammar. One of the benefits of GE is that this mapping simplifies the application of search to different programming languages and other structures.
/Cramer-style GP, the function set must meet the requirement of closure: all functions must be capable of accepting as their arguments the output of all other functions in the function set. Usually, this is implemented by dealing with a single data-type such as double-precision floating point. Whilst modern Genetic Programming frameworks supporting typing, such type-systems have limitations that Grammatical Evolution does not suffer from.
GE has a modular approach to it. In particular, the search portion of the GE paradigm needn't be carried out by any one particular algorithm or method. Observe that the objects GE performs search on are the same as that used in genetic algorithms. This means, in principle, that any existing genetic algorithm package, such as the popular GAlib, can be used to carry out the search, and a developer implementing a GE system need only worry about carrying out the mapping from list of integers to program tree. It is also in principle possible to perform the search using some other method, such as particle swarm optimization
(see the remark below); the modular nature of GE creates many opportunities for hybrids as the problem of interest to be solved dictates.
Brabazon and O'Neill have successfully applied GE to predicting corporate bankruptcy, forecasting stock indices, bond credit rating
s, and other financial applications.
It is possible to structure a GE grammar that for a given function/terminal set is equivalent to genetic programming.
to carry out the searching instead of genetic algorithms with results comparable to that of normal GE; this is referred to as a "grammatical swarm"; using only the basic PSO model it has been found that PSO is probably equally capable of carrying out the search process in GE as simple genetic algorithms are. (Although PSO is normally a floating-point search paradigm, it can be discretized, e.g., by simply rounding each vector to the nearest integer, for use with GE.)
Yet another possible variation that has been experimented with in the literature is attempting to encode semantic information in the grammar in order to further bias the search process.
Evolutionary computation
In computer science, evolutionary computation is a subfield of artificial intelligence that involves combinatorial optimization problems....
technique pioneered by Conor Ryan, JJ Collins and Michael O'Neill in 1998 at the BDS Group in the University of Limerick
University of Limerick
The University of Limerick is a university in Ireland near the city of Limerick on the island's west coast. It was established in 1972 as the National Institute for Higher Education, Limerick and became a university by statute in 1989 in accordance with the University of Limerick Act 1989...
.
It is related to the idea of genetic programming
Genetic programming
In artificial intelligence, genetic programming is an evolutionary algorithm-based methodology inspired by biological evolution to find computer programs that perform a user-defined task. It is a specialization of genetic algorithms where each individual is a computer program...
in that the objective is to find an executable program or program fragment, that will achieve a good fitness value for the given objective function. In most published work on Genetic Programming, a LISP
Lisp
A lisp is a speech impediment, historically also known as sigmatism. Stereotypically, people with a lisp are unable to pronounce sibilants , and replace them with interdentals , though there are actually several kinds of lisp...
-style tree-structured expression is directly manipulated, whereas Grammatical Evolution applies genetic operator
Genetic operator
A genetic operator is an operator used in genetic algorithms to maintain genetic diversity, known as Mutation and to combine existing solutions into others, Crossover...
s to an integer string, subsequently mapped to a program (or similar) through the use of a grammar. One of the benefits of GE is that this mapping simplifies the application of search to different programming languages and other structures.
Problem addressed
In type-free conventional, KozaJohn Koza
John R. Koza is a computer scientist and a former consulting professor at Stanford University, most notable for his work in pioneering the use of genetic programming for the optimization of complex problems. He was a cofounder of Scientific Games Corporation, a company which built computer systems...
/Cramer-style GP, the function set must meet the requirement of closure: all functions must be capable of accepting as their arguments the output of all other functions in the function set. Usually, this is implemented by dealing with a single data-type such as double-precision floating point. Whilst modern Genetic Programming frameworks supporting typing, such type-systems have limitations that Grammatical Evolution does not suffer from.
GE's solution
GE offers a solution to this issue by evolving solutions according to a user-specified grammar (usually a grammar in Backus-Naur form). Therefore the search space can be restricted, and domain knowledge of the problem can be incorporated. The inspiration for this approach comes from a desire to separate the "genotype" from the "phenotype": in GP, the objects the search algorithm operates on and what the fitness evaluation function interprets are one and the same. In contrast, GE's "genotypes" are ordered lists of integers which code for selecting rules from the provided context-free grammar. The phenotype, however, is the same as in Koza/Cramer-style GP: a tree-like structure that is evaluated recursively. This is more in line with how genetics work in nature, where there is a separation between an organism's genotype and that expression in proteins and the like.GE has a modular approach to it. In particular, the search portion of the GE paradigm needn't be carried out by any one particular algorithm or method. Observe that the objects GE performs search on are the same as that used in genetic algorithms. This means, in principle, that any existing genetic algorithm package, such as the popular GAlib, can be used to carry out the search, and a developer implementing a GE system need only worry about carrying out the mapping from list of integers to program tree. It is also in principle possible to perform the search using some other method, such as particle swarm optimization
Particle swarm optimization
In computer science, particle swarm optimization is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality...
(see the remark below); the modular nature of GE creates many opportunities for hybrids as the problem of interest to be solved dictates.
Brabazon and O'Neill have successfully applied GE to predicting corporate bankruptcy, forecasting stock indices, bond credit rating
Bond credit rating
In investment, the bond credit rating assesses the credit worthiness of a corporation's or government debt issues. It is analogous to credit ratings for individuals.-Table:...
s, and other financial applications.
It is possible to structure a GE grammar that for a given function/terminal set is equivalent to genetic programming.
Criticism
Despite its successes, GE has been the subject of some criticism. One issue is that as a result of its mapping operation, GE's genetic operators do not achieve high locality which is a highly regarded property of genetic operators in evolutionary algorithms.Variants
Although GE is fairly new, there are already enhanced versions and variants that have been worked out. GE researchers have experimented with using particle swarm optimizationParticle swarm optimization
In computer science, particle swarm optimization is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality...
to carry out the searching instead of genetic algorithms with results comparable to that of normal GE; this is referred to as a "grammatical swarm"; using only the basic PSO model it has been found that PSO is probably equally capable of carrying out the search process in GE as simple genetic algorithms are. (Although PSO is normally a floating-point search paradigm, it can be discretized, e.g., by simply rounding each vector to the nearest integer, for use with GE.)
Yet another possible variation that has been experimented with in the literature is attempting to encode semantic information in the grammar in order to further bias the search process.
Resources
- An Open Source C++ implementation of GE was funded by the Science Foundation of Ireland.
- Grammatical Evolution Tutorial.
- Grammatical Evolution in Java.
- jGE - Java Grammatical Evolution.
- The Biocomputing and Developmental Systems (BDS) Group at the University of Limerick.
- Michael O'Neill's Grammatical Evolution Page, including a bibliography.
- DRP, Directed Ruby Programming, is an experimental system designed to let users create hybrid GE/GP systems. It is implemented in pure Ruby.
- GERET, Grammatical Evolution Ruby Exploratory Toolkit.