An investigation into structured grammatical evolution initialisation

A key ingredient in any successful genetic programming is robust initialisation. Many successful initialisation methods used in genetic programming have been adapted to use with grammatical evolution, to varying levels success. This paper examines the effectiveness of some of the most popular of these initialisation techniques on structured grammatical evolution. Namely, we investigate Sensible Initialisation and Probabilistic Tree Creation 2, as well as the standard initialisation procedure used in structured grammatical evolution, Grow. We also propose a novel procedure called Local Optimised Probabilistic Tree Creation 2, which runs a quick greedy optimisation on the trees created. We do this using using two different grammar specifications, both with and without protected operators, and using an error based and correlation based fitness function. We examine their performance, as well as the diversity of solutions they create, on 8 well-known benchmarks. We observe that Local Optimised Probabilistic Tree Creation 2 created the fittest, or joint fittest, initialisation populations on every benchmark considered, bar one. Local Optimised Probabilistic Tree Creation 2 remained the best initialisation procedure when the grammar specification was changed, confirming it’s robustness. This did not necessarily result in overall better runs, however, and SGE runs with below average initialisation performance were seen to overcome their “bad start”. The diversity of solutions, particularly fitness diversity, at the end of the run was lower for Local Optimised Probabilistic Tree Creation 2 and Probabilistic Tree Creation 2 than for both sensible initialisation and grow. Local Optimised Probabilistic Tree Creation 2 was seen to take between 8 and 20 times longer to create the initial population than the other methods. This article is an extension of a paper which originally appeared at the Grammatical Evolution Workshop held as part of GECCO 2023.