A Comparative Analysis of Dynamic Locality and Redundancy in Grammatical Evolution

Abstract # ↰

Grammcal Evolution (GE) is an Evolutionary Algorithm which can address any problem whose solution space may be described in terms of a context-free grammar: its most salient feature is a procedure which maps genotypes to phenotypes using the grammar production rules. The search effectiveness of GE may be affected by low locality and high redundancy, which can prevent GE to comply with the basic principle that offspring should inherit some traits from their parents. Indeed, many studies previously investigated the locality and redundancy of GE as originally proposed in [Ryan et al., 1998]. In this paper, we extend those results by considering redundancy and locality during the evolution, rather than statically, hence trying to understand if and how they are influenced by the selective pressure determined by the fitness. Moreover, we consider not only the original GE formulation, but three other variants proposed later. We experimentally find that there is an interaction between locality/redundancy and other evolution-related measures, namely diversity and growth of individual size.