- author = "Miguel Nuno Fialho dos Santos Nicolau",
- title = "Genetic Algorithms using Grammatical Evolution",
- school = "CSIS Department, University of Limerick",
- year = "2006",
- address = "Ireland",
- month = sep,
- keywords = "genetic algorithms, genetic programming, Grammatical Evolution, GAuGE System, sGA, Mastermind, oneMax, ZeroOneMax, Binary Matching, BinInt, InvFinInt, HIFF, HIFFS, TrapT-4, TrapL-4, Order Learning, Linkage Learning, Size of search spaces, Sudoku, PMX crossover, Cycle Crossover, RKGA, LLGA, MIMIC, COMIT, BMDA, ECGA, BOA, hBOA, SSv, SSp",
-
URL = "
http://hdl.handle.net/10197/8262",
-
URL = "https://researchrepository.ucd.ie/entities/publication/0f220a48-229e-42ce-8182-e44c2bb0b118",
-
URL = "https://researchrepository.ucd.ie/server/api/core/bitstreams/e48b05f0-9856-4695-9ed7-fffc0492de0b/content",
- size = "234 pages",
-
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 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.",
-
notes = "External Examiner: Riccardo Poli
Supervisor: Conor Ryan",
