On the bias and performance of the edgeset encoding

The edge-set encoding is a direct encoding for trees which directly repre-sents trees as sets of edges. In contrast to indirect representations, where usually standard operators are applied to a list of strings and the re-sulting phenotype is constructed by an appropriate genotype-phenotype mapping, encoding-specic initialization, crossover, and mutation oper-ators have been developed for the edge-set encoding, which are directly applied to trees. There are two dierent variants of operators: heuristic versions that consider the weights of the edges and non-heuristic versions. An investigation into the bias of the dierent variants of the operators shows that the heuristic variants are biased towards the minimum span-ning tree (MST), that means solutions similar to the MST are favored. In contrast, non-heuristic versions are unbiased. The performance of edge-sets is investigated for the optimal communication spanning tree (OCST) problem. Results are presented for randomly created problems as wel