Structured Grammatical Evolution: A Dynamic Approach

Grammars have attracted the attention of researchers within the Evolutionary Computation field, specially from the Genetic Programming community. The most successful example of the use of grammars by GP is Grammatical Evolution (GE). In spite of being widely used by practitioners of different fields, GE is not free from drawbacks. The ones that are most commonly pointed out are those linked with redundancy and locality of the representation. To address these limitations Structured Grammatical Evolution (SGE) was proposed, which introduces a one-to-one mapping between the genotype and the non-terminals. In SGE the input grammar must be pre-processed so that recursion is removed, and the maximum number of expansion possibilities for each symbol determined. This has been pointed out as a drawback of SGE and to tackle it we introduce Dynamic Structured Grammatical Evolution (DSGE). In DSGE there is no need to pre-process the grammar, as it is expanded on the fly during the evolutionary process, and thus we only need to define the maximum tree depth. Additionally, it only encodes the integers that are used in the genotype to phenotype mapping, and grows as needed during evolution. Experiments comparing DSGE with SGE show that DSGE performance is never worse than SGE, being statistically superior in a considerable number of the tested problems.