On the Bias and Performance of the Edge-Set Encoding

The edge-set encoding of trees directly represents trees as sets of their edges. Nonheuristic operators for edge-sets manipulate trees´ edges without regard for their weights, while heuristic operators consider edges´ weights when including or excluding them. In the latter case, the operators generally favor edges with lower weights, and they tend to generate trees that resemble minimum spanning trees. This bias is strong, which suggests that evolutionary algorithms (EAs) that employ heuristic operators will succeed when optimum solutions resemble minimum spanning trees (MSTs) but fail otherwise. The one-max tree problem is a scalable test problem for trees where the optimum solution can be predefined. Heuristic operators for edge-sets fail when optimum solutions are random trees or stars. Similarly, for the optimal communication spanning tree (OCST) problem, heuristic operators are efficient only for problem instances where optimal solutions are slightly different from MSTs. In contrast, for both problems the performance of nonheuristic operators is approximately independent of the type of the optimal solution. Therefore, heuristic operators for edge-sets should be used only if optimal solutions closely resemble MSTs. If optimal solutions have low or no bias towards MSTs, heuristic operators for edge-sets fail, and nonheuristic operators should be preferred.