Grammatical evolution: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 22:30, 22 October 2024

Grammatical evolution (GE) is an evolutionary computation and, more specifically, a genetic programming (GP) technique (or approach) pioneered by Conor Ryan, JJ Collins and Michael O'Neill in 1998^[1] at the BDS Group in the University of Limerick.

As in any other GP approach, the objective is to find an executable program, program fragment, or function, which will achieve a good fitness value for a given objective function. In most published work on GP, a LISP-style tree-structured expression is directly manipulated, whereas GE applies genetic operators to an integer string, subsequently mapped to a program (or similar) through the use of a grammar, which is typically expressed in Backus–Naur form. 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 Koza-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. While modern Genetic Programming frameworks support typing, such type-systems have limitations that Grammatical Evolution does not suffer from.

GE's solution

GE offers a solution to the single-type limitation 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 model is more in line with how genetics work in nature, where there is a separation between an organism's genotype and the final expression of phenotype in proteins, etc.

Separating genotype and phenotype allows a modular approach. 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 those 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.^{[citation needed]} GE has also been used with a classic predator-prey model to explore the impact of parameters such as predator efficiency, niche number, and random mutations on ecological stability.^[2]

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^[3]^[4] which is a highly regarded property of genetic operators in evolutionary algorithms.^[3]

Variants

Although GE was originally described in terms of using an Evolutionary Algorithm, specifically, a Genetic Algorithm, other variants exist. For example, 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.)

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. Other work showed that, with biased grammars that leverage domain knowledge, even random search can be used to drive GE.^[5]

Related Work

GE was originally a combination of the linear representation as used by the Genetic Algorithm for Developing Software (GADS)^{[citation needed]} and Backus Naur Form grammars, which were originally used in tree-based GP by Wong and Leung^[6] in 1995 and Whigham in 1996.^[7] Other related work noted in the original GE paper was that of Frederic Gruau,^[8] who used a conceptually similar "embryonic" approach, as well as that of Keller and Banzhaf,^[9] which similarly used linear genomes.

Implementations

There are several implementations of GE. These include the following.


Project name	Language	Year	Location
GRAPE	Python	2022	https://github.com/bdsul/grape
GELab	Matlab	2018	https://github.com/adilraja/GELAB
PonyGE2	Python	2017	https://arxiv.org/abs/1703.08535
gramEvol	R	2016	https://cran.r-project.org/web/packages/gramEvol/vignettes/ge-intro.pdf
PyNeurGen	Python	2012	http://pyneurgen.sourceforge.net/
Grammatical_ evolution	Ruby	2011	http://www.cleveralgorithms.com/nature-inspired/evolution/grammatical_evolution.rb
AGE	C, Lua	2011	http://nohejl.name/age/pdf/AGE-Documentation-1.0.2.pdf
PonyGE	Python	2010	https://code.google.com/archive/p/ponyge/downloads
GERET	Ruby	2010	https://github.com/bver/GERET/
GEVA	Java	2008	http://ncra.ucd.ie/Site/GEVA.html
ECJ	Java	2008	https://cs.gmu.edu/~eclab/projects/ecj/
GENN	C++	2007	https://ritchielab.org/research/past-research/52-grammatical-evolution-neural-networks
libGE	C++, S-Lang, tinycc	2004	http://bds.ul.ie/libGE/

Notes

^ "Grammatical Evolution: Evolving Programs for an Arbitrary Language".
^ Alfonseca, Manuel; Soler Gil, Francisco José (2 January 2015). "Evolving a predator-prey ecosystem of mathematical expressions with grammatical evolution". Complexity. 20 (3): 66–83. Bibcode:2015Cmplx..20c..66A. doi:10.1002/cplx.21507. hdl:10486/663611.
^ ^a ^b Rothlauf, Franz; Oetzel, Marie (2006). "On the Locality of Grammatical Evolution". Genetic Programming. Lecture Notes in Computer Science. Vol. 3905. pp. 320–330. doi:10.1007/11729976_29. ISBN 978-3-540-33143-8.
^ "Publication: Positional Effect of Crossover and Mutation in Grammatical Evolution - School of Computing - University of Kent".
^ O’Sullivan, John; Ryan, Conor (2002), Foster, James A.; Lutton, Evelyne; Miller, Julian; Ryan, Conor (eds.), "An Investigation into the Use of Different Search Strategies with Grammatical Evolution", Genetic Programming, vol. 2278, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 268–277, doi:10.1007/3-540-45984-7_26, ISBN 978-3-540-43378-1, retrieved 2022-08-08
^ Wong, Man Leung; Leung, Kwong Sak (November 1995). "Applying logic grammars to induce sub-functions in genetic programming". Proceedings of 1995 IEEE International Conference on Evolutionary Computation. Vol. 2. pp. 737–740 vol.2. doi:10.1109/ICEC.1995.487477. ISBN 0-7803-2759-4. S2CID 16071918.
^ Whigham, P. (1996). "Search Bias, Language Bias and Genetic ProgrammingP". S2CID 16631215. {{cite web}}: Missing or empty |url= (help)
^ Gruau, Frédéric (1994), Neural Network Synthesis Using Cellular Encoding And The Genetic Algorithm, CiteSeerX 10.1.1.29.5939
^ Kellere, Robert E. (1996). "Genetic Programming Using Mutation, Reproduction and Genotype-phenotype Mapping from Linear Binary Genomes into Linear Lalr(1) Phenotypes Paper Category: Genetic Programming (gp)". S2CID 18095204. {{cite web}}: Missing or empty |url= (help)

Resources

Grammatical Evolution Tutorial.
Grammatical Evolution in Java Archived 2010-03-11 at the Wayback Machine.
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.
gramEvol, Grammatical Evolution for R.

[1] "Grammatical Evolution: Evolving Programs for an Arbitrary Language".

[2] Alfonseca, Manuel; Soler Gil, Francisco José (2 January 2015). "Evolving a predator-prey ecosystem of mathematical expressions with grammatical evolution". Complexity. 20 (3): 66–83. Bibcode:2015Cmplx..20c..66A. doi:10.1002/cplx.21507. hdl:10486/663611.

[rothlauf:2006-3] Rothlauf, Franz; Oetzel, Marie (2006). "On the Locality of Grammatical Evolution". Genetic Programming. Lecture Notes in Computer Science. Vol. 3905. pp. 320–330. doi:10.1007/11729976_29. ISBN 978-3-540-33143-8.

[4] "Publication: Positional Effect of Crossover and Mutation in Grammatical Evolution - School of Computing - University of Kent".

[5] O’Sullivan, John; Ryan, Conor (2002), Foster, James A.; Lutton, Evelyne; Miller, Julian; Ryan, Conor (eds.), "An Investigation into the Use of Different Search Strategies with Grammatical Evolution", Genetic Programming, vol. 2278, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 268–277, doi:10.1007/3-540-45984-7_26, ISBN 978-3-540-43378-1, retrieved 2022-08-08

[6] Wong, Man Leung; Leung, Kwong Sak (November 1995). "Applying logic grammars to induce sub-functions in genetic programming". Proceedings of 1995 IEEE International Conference on Evolutionary Computation. Vol. 2. pp. 737–740 vol.2. doi:10.1109/ICEC.1995.487477. ISBN 0-7803-2759-4. S2CID 16071918.

[7] Whigham, P. (1996). "Search Bias, Language Bias and Genetic ProgrammingP". S2CID 16631215. {{cite web}}: Missing or empty |url= (help)

[8] Gruau, Frédéric (1994), Neural Network Synthesis Using Cellular Encoding And The Genetic Algorithm, CiteSeerX 10.1.1.29.5939

[9] Kellere, Robert E. (1996). "Genetic Programming Using Mutation, Reproduction and Genotype-phenotype Mapping from Linear Binary Genomes into Linear Lalr(1) Phenotypes Paper Category: Genetic Programming (gp)". S2CID 18095204. {{cite web}}: Missing or empty |url= (help)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

@@ Line 1: / Line 1: @@
 {{Evolutionary algorithms}}
-'''Grammatical evolution (GE)''' is an [[evolutionary computation]] and, more specifically, a [[genetic programming]] (GP) technique (or approach) pioneered by Conor Ryan, JJ Collins and Michael O'Neill in 1998<ref>{{Cite web|url=http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/ryan_1998_geepal.html|title=Grammatical Evolution: Evolving Programs for an Arbitrary Language}}</ref> at the [http://bds.ul.ie BDS Group] in the [[University of Limerick]], although there are other related works, which were published even before, such as.<ref>https://www.researchgate.net/profile/PA_Whigham/publication/2450222_Grammatically-based_Genetic_Programming/links/55c3c89908aebc967df1b765.pdf</ref>
+'''Grammatical evolution (GE)''' is an [[evolutionary computation]] and, more specifically, a [[genetic programming]] (GP) technique (or approach) pioneered by Conor Ryan, JJ Collins and Michael O'Neill in 1998<ref>{{Cite web|url=http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/ryan_1998_geepal.html|title=Grammatical Evolution: Evolving Programs for an Arbitrary Language}}</ref> at the [http://bds.ul.ie BDS Group] in the [[University of Limerick]].
 As in any other GP approach, the objective is to find an executable program, program fragment, or function, which will achieve a good fitness value for a given [[objective function]]. In most published work on GP, a [[LISP]]-style tree-structured expression is directly manipulated, whereas GE applies [[genetic operator]]s to an integer string, subsequently mapped to a program (or similar) through the use of a grammar, which is typically expressed in [[Backus–Naur form]]. One of the benefits of GE is that this mapping simplifies the application of search to different programming languages and other structures.
@@ Line 10: / Line 10: @@
 == GE's solution ==
-GE offers a solution to this {{which|date=January 2015}} 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 model is more in line with how genetics work in nature, where there is a separation between an organism's genotype and the final expression of phenotype in proteins, etc.
+GE offers a solution to the single-type limitation 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 model is more in line with how genetics work in nature, where there is a separation between an organism's genotype and the final expression of phenotype in proteins, etc.
 Separating genotype and phenotype allows a modular approach. 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 those used in [[genetic algorithms]]. This means, in principle, that any existing genetic algorithm package, such as the popular [http://lancet.mit.edu/ga/ 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.
@@ Line 20: / Line 20: @@
 == 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<ref name="rothlauf:2006">[https://doi.org/10.1007%2F11729976_29 DOI.org]</ref><ref>{{Cite web|url=http://www.cs.kent.ac.uk/pubs/2010/3004/index.html|title = Publication: Positional Effect of Crossover and Mutation in Grammatical Evolution - School of Computing - University of Kent}}</ref> which is a highly regarded property of genetic operators in evolutionary algorithms.<ref name="rothlauf:2006" />
+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<ref name="rothlauf:2006">{{cite book | chapter-url=https://doi.org/10.1007%2F11729976_29 | doi=10.1007/11729976_29 | chapter=On the Locality of Grammatical Evolution | title=Genetic Programming | series=Lecture Notes in Computer Science | date=2006 | last1=Rothlauf | first1=Franz | last2=Oetzel | first2=Marie | volume=3905 | pages=320–330 | isbn=978-3-540-33143-8 }}</ref><ref>{{Cite web|url=http://www.cs.kent.ac.uk/pubs/2010/3004/index.html|title = Publication: Positional Effect of Crossover and Mutation in Grammatical Evolution - School of Computing - University of Kent}}</ref> which is a highly regarded property of genetic operators in evolutionary algorithms.<ref name="rothlauf:2006" />
 == 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.)
+Although GE was originally described in terms of using an Evolutionary Algorithm, specifically, a Genetic Algorithm, other variants exist. For example, 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.)
-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.
+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. Other work showed that, with biased grammars that leverage domain knowledge, even random search can be used to drive GE.<ref>{{Citation |last1=O’Sullivan |first1=John |title=An Investigation into the Use of Different Search Strategies with Grammatical Evolution |date=2002 |url=http://link.springer.com/10.1007/3-540-45984-7_26 |work=Genetic Programming |volume=2278 |pages=268–277 |editor-last=Foster |editor-first=James A. |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |doi=10.1007/3-540-45984-7_26 |isbn=978-3-540-43378-1 |access-date=2022-08-08 |last2=Ryan |first2=Conor |editor2-last=Lutton |editor2-first=Evelyne |editor3-last=Miller |editor3-first=Julian |editor4-last=Ryan |editor4-first=Conor}}</ref>
+== Related Work ==
+GE was originally a combination of the linear representation as used by the Genetic Algorithm for Developing Software (GADS){{citation needed|date=November 2022}} and Backus Naur Form grammars, which were originally used in tree-based GP by Wong and Leung<ref>{{Cite book |last1=Wong |first1=Man Leung |last2=Leung |first2=Kwong Sak |title=Proceedings of 1995 IEEE International Conference on Evolutionary Computation |chapter=Applying logic grammars to induce sub-functions in genetic programming |date=November 1995 |chapter-url=https://ieeexplore.ieee.org/document/487477 |volume=2 |pages=737–740 vol.2 |doi=10.1109/ICEC.1995.487477|isbn=0-7803-2759-4 |s2cid=16071918 }}</ref> in 1995 and Whigham in 1996.<ref>{{Cite web |last=Whigham |first=P. |date=1996 |title=Search Bias, Language Bias and Genetic ProgrammingP |s2cid=16631215 |language=en}}</ref> Other related work noted in the original GE paper was that of Frederic Gruau,<ref>{{Citation |last=Gruau |first=Frédéric |title=Neural Network Synthesis Using Cellular Encoding And The Genetic Algorithm |date=1994 |citeseerx=10.1.1.29.5939 }}</ref> who used a conceptually similar "embryonic" approach, as well as that of Keller and Banzhaf,<ref>{{Cite web |last=Kellere |first=Robert E. |date=1996 |title=Genetic Programming Using Mutation, Reproduction and Genotype-phenotype Mapping from Linear Binary Genomes into Linear Lalr(1) Phenotypes Paper Category: Genetic Programming (gp) |s2cid=18095204 |language=en}}</ref> which similarly used linear genomes.
+== Implementations ==
+There are several implementations of GE. These include the following.
+{| class="wikitable"
+|+
+|'''Project name'''
+|'''Language'''
+|'''Year'''
+|'''Location'''
+|-
+|GRAPE
+|Python
+|2022
+|<nowiki>https://github.com/bdsul/grape</nowiki>
+|-
+|GELab
+|Matlab
+|2018
+|<nowiki>https://github.com/adilraja/GELAB</nowiki>
+|-
+|PonyGE2
+|Python
+|2017
+|<nowiki>https://arxiv.org/abs/1703.08535</nowiki>
+|-
+|gramEvol
+|R
+|2016
+|<nowiki>https://cran.r-project.org/web/packages/gramEvol/vignettes/ge-intro.pdf</nowiki>
+|-
+|PyNeurGen
+|Python
+|2012
+|<nowiki>http://pyneurgen.sourceforge.net/</nowiki>
+|-
+|Grammatical_ evolution
+|Ruby
+|2011
+|<nowiki>http://www.cleveralgorithms.com/nature-inspired/evolution/grammatical_evolution.rb</nowiki>
+|-
+|AGE
+|C, Lua
+|2011
+|<nowiki>http://nohejl.name/age/pdf/AGE-Documentation-1.0.2.pdf</nowiki>
+|-
+|PonyGE
+|Python
+|2010
+|<nowiki>https://code.google.com/archive/p/ponyge/downloads</nowiki>
+|-
+|GERET
+|Ruby
+|2010
+|<nowiki>https://github.com/bver/GERET/</nowiki>
+|-
+|GEVA
+|Java
+|2008
+|<nowiki>http://ncra.ucd.ie/Site/GEVA.html</nowiki>
+|-
+|ECJ
+|Java
+|2008
+|<nowiki>https://cs.gmu.edu/~eclab/projects/ecj/</nowiki>
+|-
+|GENN
+|C++
+|2007
+|<nowiki>https://ritchielab.org/research/past-research/52-grammatical-evolution-neural-networks</nowiki>
+|-
+|libGE
+|C++, S-Lang, tinycc
+|2004
+|<nowiki>http://bds.ul.ie/libGE/</nowiki>
+|}
 ==See also==
 * [[Genetic programming]]
 * [[Java Grammatical Evolution]]
+* [[Cartesian genetic programming]]
+* [[Gene expression programming]]
+* [[Linear genetic programming]]
+* [[Multi expression programming]]
 ==Notes==
@@ Line 39: / Line 121: @@
 * [https://web.archive.org/web/20110721124315/http://www.grammaticalevolution.org/tutorial.pdf Grammatical Evolution Tutorial].
-* [http://ncra.ucd.ie/geva Grammatical Evolution in Java].
+* [http://ncra.ucd.ie/geva Grammatical Evolution in Java] {{Webarchive|url=https://web.archive.org/web/20100311002142/http://ncra.ucd.ie/geva/ |date=2010-03-11 }}.
 * [https://web.archive.org/web/20101129085227/http://www.bangor.ac.uk/~eep201/jge/ jGE - Java Grammatical Evolution].
 * [http://bds.ul.ie The Biocomputing and Developmental Systems (BDS) Group] at the [http://www.ul.ie University of Limerick].
@@ Line 46: / Line 128: @@
 * [http://geret.org/ GERET], Grammatical Evolution Ruby Exploratory Toolkit.
 * [https://cran.r-project.org/web/packages/gramEvol/index.html gramEvol], Grammatical Evolution for [[R (programming language)|R]].
+{{Evolutionary computation}}
 {{DEFAULTSORT:Grammatical Evolution}}

v t e Evolutionary computation
Main Topics	Evolutionary algorithm Evolutionary data mining Evolutionary multimodal optimization Human-based evolutionary computation Interactive evolutionary computation
Algorithms	Cellular evolutionary algorithm Covariance Matrix Adaptation Evolution Strategy (CMA-ES) Cultural algorithm Differential evolution Evolutionary programming Genetic algorithm Genetic programming Gene expression programming Evolution strategy Natural evolution strategy Neuroevolution Learning classifier system
Related techniques	Swarm intelligence Ant colony optimization Bees algorithm Cuckoo search Particle swarm optimization Bacterial Colony Optimization
Metaheuristic methods	Firefly algorithm Harmony search Gaussian adaptation Memetic algorithm
Related topics	Artificial development Artificial intelligence Artificial life Digital organism Evolutionary robotics Fitness function Fitness landscape Fitness approximation Genetic operators Interactive evolutionary computation No free lunch in search and optimization Machine learning Mating pool Premature convergence Program synthesis
Journals	Evolutionary Computation (journal)