Multi-level diversity promotion strategies for Grammar-guided Genetic Programming

Grammar-guided Genetic Programming (G3P) is a family of Evolutionary Algorithms that can evolve programs in any language described by a context-free grammar. The most widespread members of this family are based on an indirect representation: a sequence of bits or integers (the genotype) is transformed into a string of the language (the phenotype) by means of a mapping function, and eventually into a fitness value. Unfortunately, the flexibility brought by this mapping is also likely to introduce non-locality phenomena, reduce diversity, and hamper the effectiveness of the algorithm. In this paper, we experimentally characterize how population diversity, measured at different levels, varies for four popular G3P approaches. We then propose two strategies for promoting diversity which are general, independent both from the specific problem being tackled and from the other components of the Evolutionary Algorithm, such as genotype-phenotype mapping, selection criteria, and genetic operators. We experimentally demonstrate their efficacy in a wide range of conditions and from different points of view. The results also confirm the preponderant importance of the phenotype-level analyses in diversity promotion.