Making the Edge-Set Encoding Fly by Controlling the Bias of its Crossover Operator

The edge-set encoding is a direct tree encoding which applies search oper-ators directly to trees represented as sets of edges. There are two variants of crossover operators for the edge-set encoding: With heuristics that con-sider the weights of the edges, or without heuristics. Due to a strong bias of the heuristic crossover operator towards the minimum spanning tree (MST) a population of solutions converges quickly towards the MST and EAs using this operator show low performance when used for tree opti-mization problems where the optimal solution is not the MST. This paper presents a modied crossover operator ( -TX) that allows us to control the bias towards the MST. The bias can be set arbitrarily between the strong bias of the heuristic crossover operator, or being unbiased. An investigation into the performance of EAs using the -TX for randomly created OCST problems of dierent types and OCST test instances from the literature present good results when setting the crossover-specic para-meter properly. The presented results suggest that the original heuristic crossover operator of the edge-sets should be substituted by the modied-TX operator that allows us to control the bias towards the MST.