Genetic Algorithms using Grammatical Evolution
|Title:||Genetic Algorithms using Grammatical Evolution||Authors:||Nicolau, Miguel||Permanent link:||http://hdl.handle.net/10197/8262||Date:||Sep-2006||Abstract:||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.||Funding Details:||Science Foundation Ireland||Type of material:||Doctoral Thesis||Publisher:||University of Limerick||Copyright (published version):||2006 the Author||Keywords:||Genetic programming;Grammatical evolution||Language:||en||Status of Item:||Peer reviewed|
|Appears in Collections:||Business Research Collection|
Show full item record
This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.