Analysis and Design of Representations for Trees

In the previous chapter, we illustrated that our framework modeling the influence of representations on the performance of GEAs not only works for binary phenotypes, but also for problems where the phenotypes are integers. However, it is possible to go one step further and to look at problems where the phenotypes and genotypes are completely different. One example for these types of problems are tree optimization problems. Trees are special types of graphs. Representations for trees must incorporate the additional restriction of a graph to be a tree. Therefore, if the genotypes are strings, there is a large semantic gap between tree structures (phenotypes) and strings (genotypes). In contrast to general network problems, where a representation simply has to indicate which links are used for the graph, no natural or intuitive “good” tree representations exist which are accessible for GEAs. As a result, researchers have proposed a variety of different tree representations with different properties. However, up till now no theory-based analysis exists about how GEA performance is influenced by the different types of tree representations.