The Edge-Set Encoding Revisited: On the Bias of a DirectRepresentation for Trees

The edge-set encoding is a direct tree representation which directly representstrees as sets of edges. There are two variants of the edge-set encoding:the edge-set encoding without heuristics, and the edge-set encoding withheuristics. An investigation into the bias of the edge-set encoding showsthat the crossover operator of the edge-set encoding without heuristics isunbiased, that means it does not favor particular types of trees. In contrast,the crossover operator with heuristics is biased towards the simpleminimum spanning tree (MST) and generates more likely trees that areMST-like. As a result, the performance of the edge-set encoding withoutheuristics does not depend on the structure of the optimal solution. Usingthe heuristic crossover operator results only in high GA performance if theoptimal solution of the problem is slightly dierent from the simple MST.[...]