Improving Module Identification and Use in Grammatical Evolution

Exploiting patterns within a solution or reusing certain functionality is often necessary to solve certain problems. This paper proposes a new method for identifying useful modules. Modules are only considered if they are prevalent in the population and they are seen to have a positive effect on an individual's fitness. This is achieved by finding the covariance of an individual's fitness with the presence of a particular subtree in the overall expression.While there are many successful systems that dynamically add modules during Genetic Programming (GP) runs, doing so is not trivial for Grammatical Evolution (GE), due to the fact that it employs a mapping process to produce individuals from binary strings, which makes it difficult to dynamically change the mapping process during a run.We adopt a multi-run approach which only has a single stage of module addition to mitigate the problems associated with continuously adding newly found functionality to a grammar. Based on the well-known Price Equation, our system explores the covariance between traits to identify useful modules, which are added to the grammar, before the system is restarted. Grammar Augmentation through Module Encapsulation (GAME) was tested on seven problems from three different domains and was observed to significantly improve the performance on 3 problems and never showing harmful effects on any problem. GAME found the best individual in 6 of the 7 experiments.