Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/35592
Title: Grammar Based Evolutionary Design
Authors: Assunção, Filipe Guerreiro 
Orientador: Machado, Fernando Jorge Penousal Martins
Keywords: Genetic Programming; Grammar Evolution; Alignment; Fitness Assignment
Issue Date: 20-Jul-2015
Serial title, monograph or event: Grammar Based Evolutionary Design
Place of publication or event: Coimbra
Abstract: A novel evolutionary approach for evolving grammars is presented. It is composed of two main methodologies. In the first one, individuals are represented as a graph, where nodes stand for production rules, and connections between them to the flow of control and parameters. In the second one, a tree representation is used; individuals are derivation trees, from a pre-defined grammar. Inner nodes represent non-terminals, and leaves terminals. It is proved that both representations are able to properly evolve the desired solutions (in this case, images and music). After conducting experiments with the above approaches, running separately, we try to merge components from both of them in order to assess if any improvement is achieved. Graph-mutation has proven to generate the worst results, using both tree and graph-crossovers. When tree-mutation is used the performance obtained with tree and graph-crossovers tends to be similar. Nevertheless, an analysis at a population level, reveals that tree-crossover outperforms the graph one. Considering these results, we searched forms of improving the graph-crossover operator, by means of alignment, thus taking into account the structure of the graphs. Aligning two graphs choosing then the cutting points from the list returned by the algorithm, where the matched pairs of nodes have the least alignment cost, has proven to lead to better performance. Finally, we address the problem of assessing the quality of families of images, proposing a fitness function for the assessment of families of individuals. Families are seen as sets of artifacts that should share common characteristics, allowing one to intuitively classify them as belonging to the same family. Results show the validity of the method and prove that, to evolve a family, both the qualities of the set and of each individual must be taken into consideration.
Description: Dissertação de Mestrado em Engenharia Informática apresentada à Faculdade de Ciências e Tecnologia da Universidade de Coimbra
URI: http://hdl.handle.net/10316/35592
Rights: openAccess
Appears in Collections:UC - Dissertações de Mestrado
FCTUC Eng.Informática - Teses de Mestrado

Files in This Item:
File Description SizeFormat
Grammar Based Evolutionary Design.pdf30.39 MBAdobe PDFView/Open
Show full item record

Page view(s)

120
checked on Nov 24, 2021

Download(s)

115
checked on Nov 24, 2021

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.