A Bilevel Optimization Strategy for the Mapping Process in Grammatical Evolution

Grammatical Evolution is a technique for evolving structured solutions using a genotype-to-phenotype mapping based on formal grammar. Optimization is typically performed on the genotype values. However, the use of permutations to guide mapping has been shown to improve solution performance. Traditionally, the focus has been on single-level optimization of the genotype values or the order in which codons are consumed during mapping. This motivates the use of a bilevel approach that enables the simultaneous optimization of genotype values and their ordering. This paper proposes a bilevel Grammatical Evolution approach called BiGE, in which the upper level optimizes the genotype values, whereas the lower level optimizes the order in which these same values are used in the mapping process. The approach was implemented using both Depth-First (DF) and Breadth-First (BF) mapping processes, which are the canonical mapping strategies in Grammatical Evolution. The proposed approach was evaluated on the Symbolic Regression Problem and compared with state-of-the-art approaches under identical experimental conditions. Statistical tests were performed to determine whether significant differences existed among the compared approaches. The results revealed statistically significant differences, indicating that incorporating a bilevel optimization strategy into the mapping process can improve the quality of the generated solutions