On the Influence of Grammars on Crossover in Grammatical Evolution

Standard grammatical evolution (GE) uses a one-point crossover ("ripple crossover") that exchanges codons between two genotypes. The two resulting genotypes are then mapped to their respective phenotypes using a Backus-Naur form grammar. This article studies how different types of grammars affect the resulting individuals of a ripple crossover. We distinguish different grammars based on the expected number of non-terminals chosen when mapping genotype codons to phenotypes, B-avg. The grammars only differ in B-avg but can express the same phenotypes. We perform crossover operations on the genotypes and find that grammars with B-avg > 1 lead to high numbers of either very small trees or invalid individuals. Due to the re-sampling of the invalid individuals, the algorithmic runtime is higher compared to grammars with a small B-avg, despite being able to express the same phenotypes. In grammars with B-avg <= 1, the bias towards small trees is reduced and instead, the frequency of valid large trees is increased. Our results give insights on favorable grammar designs and underline the central role of grammar design in GE.