The Influence of Probabilistic Grammars on Evolution
Published in Companion Conference on Genetic and Evolutionary Computation (GECCO 23 Companion), 2023
Jessica Mégane, Nuno Lourenço, Penousal Machado, and Dirk Schweim
Published as Poster
Abstract
Context-Free Grammars (CFGs) are used in Genetic Programming (GP) to encode the structure and syntax of programs, enabling efficient exploration of potential solutions and generation of well- formed and syntactically correct programs. Probabilistic Context- Free Grammars (PCFG) can be used to model the distribution of solutions to help guide the search process. Structured Grammatical Evolution (SGE) is a grammar-based GP algorithm that uses a list of dynamic lists as its genotype, where each list represents the ordered indexes of production rules to expand for each non-terminal in the grammar. Two recent variants incorporate PCFG into the SGE framework, where the probabilities of the production rule change during the evolutionary process, resulting in improved performance.
This study examines the impact of these differences on the be- havior of SGE and its variants, Probabilistic Structured Grammati- cal Evolution (PSGE) and Co-evolutionary Probabilistic Structured Grammatical Evolution (Co-PSGE), in terms of population tree depth, genotype size, new solutions generated, and runtime. The re- sults indicate that the use of probabilistic alternatives can affect the growth of tree depth and size and increases the ability to generate new solutions
DOI
Recommended citation
Jessica Mégane, Nuno Lourenço, Penousal Machado, and Dirk Schweim. 2023. The Influence of Probabilistic Grammars on Evolution. In Proceedings of the Companion Conference on Genetic and Evolutionary Computation (GECCO ‘23 Companion). Association for Computing Machinery, New York, NY, USA, 991–999. https://doi.org/10.1145/3583133.3590706