Context sensitive grammatical evolution: a novel attribute grammar based approach to the integration of semantics in grammatical evolution

peer-reviewed
The merit of Evolutionary Algorithms (EAs) as a means of automatic problem solving has been demonstrated numerous times on a diverse set of problem types across a range of different domains. The central hypothesis of this thesis is that by improving the expressiveness of EAs we can better support their deployment in domains in which context sensitive decision making is useful. After describing the principal structures and operations which allow EAs operate effectively as a general problem solving technique, we describe a sample problem and outline how two EA types, Genetic Programming (GP) and Grammatical Evolution (GE), might be configured to solve it. After some foundational elements of the discipline game design are presented, we highlight how a move towards more formal specifications of design elements presents new opportunities for the deployment of EAs as a means of Procedural Content Generation (PCG). Subsequently a set of experiments are described in which a system, designed to support encoding of data type information using a variant of GP called Strongly Typed Genetic Programming (STGP), is used to generate Player Character (PC) controllers for the digital video game Ms. Pac-Man. Following this an overview of Formal Grammars (FGs) is presented and the principal structures and operations of a third EA type, GE, are described. After which a number of more expressive FGs than Context Free Grammar (CFG), the grammar traditionally used with GE, are outlined. Finally, we outline a new GE variant designed to support usage Attribute Grammars (AGs), a means of specifying solution semantics in addition to syntax, and outline a set of experiments conducted using it. After highlighting the gains that can be made by using this GE variant in traditional problem domains such as symbolic regression, we discuss its potential as a means of PCG in digital video games. as a means of automatic problem solving has been demonstrated numerous times on a diverse set of problem types a