6533b873fe1ef96bd12d4be3

RESEARCH PRODUCT

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

subject

description

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, 75% 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 ≥ 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 75% 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 ≈ 1.