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 2018 : 6 citations
Bartoli, A., Castelli, M., & Medvet, E. (2018). Weighted Hierarchical Grammatical Evolution. IEEE Transactions on Cybernetics.
Brum, A., & Ritt, M. (2018, July). Automatic Design of Heuristics for Minimizing the Makespan in Permutation Flow Shops. In 2018 IEEE Congress on Evolutionary Computation (CEC) (pp. 1-8). IEEE.
Chicago
Brum, A., & Ritt, M. (2018, April). Automatic Algorithm Configuration for the Permutation Flow Shop Scheduling Problem Minimizing Total Completion Time. In European Conference on Evolutionary Computation in Combinatorial Optimization (pp. 85-100). Springer, Cham.
de Souza, M., & Ritt, M. (2018, July). An Automatically Designed Recombination Heuristic for the Test-Assignment Problem. In 2018 IEEE Congress on Evolutionary Computation (CEC) (pp. 1-8). IEEE
de Souza, M., & Ritt, M. (2018, April). Automatic Grammar-Based Design of Heuristic Algorithms for Unconstrained Binary Quadratic Programming. In European Conference on Evolutionary Computation in Combinatorial Optimization (pp. 67-84). Springer, Cham.
Nicolau, M., & Agapitos, A. (2018). Understanding Grammatical Evolution: Grammar Design. In Handbook of Grammatical Evolution (pp. 23-53). Springer, Cham.
Year 2017 : 6 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.
Klotz, D., Herrnegger, M., & Schulz, K. (2017). Symbolic regression for the estimation of transfer functions of hydrological models. Water Resources Research, 53(11), 9402-9423.
Medvet, Eric. "A Comparative Analysis of Dynamic Locality and Redundancy in Grammatical Evolution."
Harvard
