Syntactically Correct Genetic Programming

Ványi R, Zvada S (2004)

Publication Language: English

Publication Type: Conference contribution, Original article

Publication year: 2004

Conference Proceedings Title: Proceedings of the 3rd Grammatical Evolution Workshop (GEWS 2004)

Event location: Seattle, WA, USA US



When common Genetic Programming is used to solve a prob-
lem, the so-called closure property must be fulfilled. That is any solution
received by changing parse trees at any point has to be considered as a
candidate and must receive a fitness value. Sometimes maintaining this
property needs extra resources, since it may cause that several candidates
have to be corrected or replaced.
Sometimes it is possible to describe the correct solutions using a gram-
mar. This way the syntax of the accepted candidates can be given, and
during the evolution solely valid individuals, that is possible solution
candidates can be generated.
In this paper three methods for syntactically correct genetic program-
ming are examined. The first one is Strongly Typed Genetic Program-
ming, which extends Koza’s original GP by assigning signatures to func-
tion symbols. The second is Grammatical Evolution, which defines the
correct individuals by a context-free grammar. It is not exactly genetic
programming using a strict definition, but also works with complex indi-
viduals, though using a simple bitvector representation. The last one is
Derivation-Tree Based Genetic Programming that is similar to Gram-
matical Evolution but uses derivation trees to represent individuals.
Some extensions for the latter one are also given in this paper.

How to cite


Ványi, R., & Zvada, S. (2004). Syntactically Correct Genetic Programming. In Cagnoni, Stefano ; Keijzer, M. ; O'Neill, M. ; Ryan, C. (Eds.), Proceedings of the 3rd Grammatical Evolution Workshop (GEWS 2004). Seattle, WA, USA, US.


Ványi, Róbert, and Szilvia Zvada. "Syntactically Correct Genetic Programming." Proceedings of the Grammatical Evolution (GEWS 2004), Seattle, WA, USA Ed. Cagnoni, Stefano ; Keijzer, M. ; O'Neill, M. ; Ryan, C., 2004.

BibTeX: Download