Genetic Algorithms using Grammatical Evolution

Files in This Item:
File Description SizeFormat 
nicolau06d.pdf1.33 MBAdobe PDFDownload
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

Download(s) 50

35
checked on May 25, 2018

Google ScholarTM

Check


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.