On the Bias and Performance of the Edge-Set Encoding

The edge-set encoding is a direct encoding for trees which directly representstrees as sets of edges. In contrast to indirect representations, whereusually standard operators are applied to a list of strings and the resultingphenotype is constructed by an appropriate genotype-phenotypemapping, encoding-specic initialization, crossover, and mutation operatorshave been developed for the edge-set encoding, which are directlyapplied to trees. There are two dierent variants of operators: heuristicversions that consider the weights of the edges and non-heuristic versions.An investigation into the bias of the dierent variants of the operatorsshows that the heuristic variants are biased towards the minimum spanningtree (MST), that means solutions similar to the MST are favored. Incontrast, non-heuristic versions are unbiased. The performance of edgesetsis investigated for the optimal communication spanning tree (OCST)problem. Results are presented for randomly created problems as wellas for test instances from the literature.[...]