Genetic Algorithms using Grammatical Evolution

This thesis proposes a new representation for genetic algorithms, based on the idea of a genotype to phenotype mapping process. It allows the explicit encoding of the position and value of all the variables composing a problem, therefore disassociating each variable from its genotypic location. The GAuGE system (Genetic Algorithms using Grammatical Evolution) is developed using this mapping process. In a manner similar to Grammatical Evolution, it ensures that there is no under- nor over-specification of phenotypic variables, therefore always producing syntactically valid solutions. The process is simple to implement and independent of the search engine used; in this work, a genetic algorithm is employed. The formal definition of the mapping process, used in this work, provides a base for analysis of the system, at different levels. The system is applied to a series of benchmark problems, defining its main features and potential problem domains. A thorough analysis of its main characteristics is then presented, including its interaction with genetic operators, the effects of degeneracy, and the evolution of representation. This in-depth analysis highlights the system’s aptitude for relative ordering problems, where not only the value of each variable is to be discovered, but also their correct permutation. Finally, the system is applied to the real-world problem of solving Sudoku puzzles, which are shown to be similar to instances of planning and scheduling problems, illustrating the class of problems for which GAuGE can prove to be a useful approach. The results obtained show a substantial improvement in performance, when compared to a standard genetic algorithm, and pave the way to new applications to problems exhibiting similar characteristics.