CISUC

Unveiling the properties of structured grammatical evolution

Authors

Abstract

Structured grammatical evolution (SGE) is a new genotypic representation for grammatical evolution (GE). It comprises a hierarchical organization of the genes, where each locus is explicitly linked to a non-terminal of the grammar being used. This one-to-one correspondence ensures that the modification of a gene does not affect the derivation options of other non-terminals. We present a comprehensive set of optimization results obtained with problems from three different categories: symbolic regression, path finding, and predictive modeling. In most of the situations SGE outperforms standard GE, confirming the effectiveness of the new representation. To understand the reasons for SGE enhanced performance, we scrutinize its main features. We rely on a set of static measures to model the interactions between the representation and variation operators and assess how they influence the interplay between the genotype-phenotype spaces. The study reveals that the structured organization of SGE promotes an increased locality and is less redundant than standard GE, thus fostering an effective exploration of the search space.

Journal

Genetic Programming and Evolvable Machines , pp. 1-39, February 2016

DOI


Cited by

Year 2017 : 5 citations

 Shunya Maruta and Yi Zuo and Masahiro Nagao and Eisuke Kita (2017). Grammati- cal Evolution Using Tree Representation Learning. In Neural Information Processing (pp.346-355)

 Medvet, E., Daolio, F., and Tagliapietra, D. (2017). Evolvability in Grammatical Evolu- tion. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO.

 Medvet, E., and Tušar, T. (2017). The DU Map: A Visualization to Gain Insights into Genotype-Phenotype Mapping and Diversity.

 Nicolau, M. (2017). Understanding grammatical evolution: initialisation. Genetic Pro- gramming and Evolvable Machines, 1-41.

 Medvet, Eric. "A Comparative Analysis of Dynamic Locality and Redundancy in Grammatical Evolution."
Harvard