A preliminary comparison of tree encoding schemes for evolutionary algorithms

This paper presents a comparative study of six encodings which have been used to represent trees in evolutionary algorithms. The study has been divided into two steps: 1) The encoding methods have been evaluated taking into account the time necessary to perform operations such as decoding, crossover and mutation, the feasibility of solutions after those operations, and the corresponding heritability and locality; 2) The encoding methods have been employed in a genetic algorithm to solve three different instances (with 10, 25 and 50 nodes) of the optimal communication spanning tree problem. Finally, the results obtained with each of the encodings are statistically compared using Kruskal-Wallis non-parametric tests and multiple comparisons. The results of this study provide insight into the properties of current encoding schemes for network design problems.