Grammar Based Evolutionary Design

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.