Grammatical evolution

From Wikipedia, the free encyclopedia

Grammatical evolution is a relatively new evolutionary computation technique pioneered by Conor Ryan, JJ Collins and Michael O'Neill in 1998^[1] at the BDS Group in the University of Limerick, Ireland. It is related to the idea of genetic programming in that the objective is to find an executable program or program fragment, normally a Lisp-style tree-structured expression, that will achieve a good fitness value for the given objective function to be minimized. However, in normal, Koza-style GP, any function in the function set can "call" any others; that is, essentially any function can be a child of any other function. This means that the functions have to be made so that all functions in the function set can accept any value which could possibly be passed to them. Often this is done by simply making everything take double-precision floating point numbers as parameters and return doubles as well. This produces a "combinatorial explosion" situation. While assuming essentially nothing about the form of the solution to a problem may be desirable, it is not uncommon to have a general view of how the structure should look. It is desirable to be able to incorporate this knowledge into the search process as necessary.

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-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 (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 ratings, and other financial applications.

It is possible to structure a GE grammar that for a given function/terminal set is equivalent to genetic programming.

1 Variants
2 Notes
- 2.1 Resources
3 See also

[edit] 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 optimization 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.)

It is also possible to use the GE process itself to evolve an optimal grammar, in a kind of "meta-grammatical evolution."

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.