On the Non-uniform Redundancy of Representations for Grammatical Evolution: The Influence of Grammars

Created by W.Langdon from gp-bibliography.bib Revision:1.7630

@InCollection{Schweim:2018:hbge,

• author = "Dirk Schweim and Ann Thorhauer and Franz Rothlauf",
• title = "On the Non-uniform Redundancy of Representations for Grammatical Evolution: The Influence of Grammars",
• booktitle = "Handbook of Grammatical Evolution",
• publisher = "Springer",
• year = "2018",
• editor = "Conor Ryan and Michael O'Neill and J. J. Collins",
• chapter = "3",
• pages = "55--78",
• keywords = "genetic algorithms, genetic programming, Grammatical Evolution",
• isbn13 = "978-3-319-78716-9",
• DOI = "doi:10.1007/978-3-319-78717-6_3",
• abstract = "The representation used in grammatical evolution (GE) is non-uniformly redundant as some phenotypes are represented by more genotypes than others. This article studies how the non-uniform redundancy of the GE representation depends on various types of grammars. When constructing the phenotype tree from a genotype, the used grammar determines Bavg, the average branching factor. Bavg measures the expected number of non-terminals chosen when mapping one genotype codon to a phenotype tree node. First, the paper illustrates that the GE representation induces a bias towards small trees. This bias gets stronger with lower Bavg. For example, when using a grammar with Bavg = 0.5, 75percent of all genotypes encode a phenotype tree of size one (codon length 10, two bits per codon, no wrapping, and random bit initialisation). Second, for Bavg ge 1, the expected size of a phenotype tree is infinite. The resulting bias towards invalid trees increases with higher Bavg. For example, for a grammar with Bavg = 2.25, around 75percent of all genotypes encode invalid trees. In summary, the GE encoding is strongly non-uniformly redundant and the bias depends on Bavg. As a compromise between the different biases, the results of this study suggest setting Bavg approx 1.",
• notes = "Part of \cite{Ryan:2018:hbge}",

}

Genetic Programming entries for Dirk Schweim Ann Thorhauer Franz Rothlauf

Citations