The Influence of Probabilistic Grammars on Evolution
Jessica Mégane, Nuno Lourenço, Penousal Machado, Dirk Schweim · 2023
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.