The edge-window-decoder representation for tree-based problems

摘要

We describe the "edge-window-decoder" strategy (EWD), a decoder-based redundant encoding strategy for tree-based combinatorial problems, and explore its performance on three well-known tree-based network optimization problems: the degree constrained minimum spanning tree problem (DCMST), the optimum communication spanning tree problem (OCST), and the quadratic minimum spanning tree problem (q-MST). Each is an NP-hard problem, and in each case the best previously published approach (for obtaining fast solutions on large instances) is an evolutionary algorithm (EA), characterized by a specialized encoding. EWD simply encodes a tree as a list of nodes (in which nodes may be repeated), and a tree is built from this list via a "tree construction routine" (TCR). A particular instantiation of EWD involves choosing a specific TCR, and choosing specific designs for the mutation and crossover operators (which work only at the genotype (list of nodes) level). Different combinations of TCRs and operators are described and explored and found to be suited to different classes of problem. We compare these several instantiations of EWD with other encodings (including the previous best reported for each problem) over several benchmark instances, as well as randomly generated instances. We find that instantiations of EWD generally perform favorably, clearly outperforming the best comparative approach in two of the three problem classes, and close to best in the third. Some analyses of EWD in terms of its locality, heritability, and bias are provided. These indicate that EWD shows high locality and heritability, and an intermediate level of bias toward the MST of the problem under consideration. In particular, the basic EWD encoding strategy is unbiased, but its good performance on a range of tree-based problems appears to be explainable in terms of the bias inherent in the associated operators. Further, experiments show that EWD strategies using one particular biased operator are able to apply a consistent intermediate level of bias "pressure" over time, thus allowing the search to range more freely in the early stages over the less represented areas of the landscape, rather than (as is the case with the other biased encoding/operator combinations compared against) quickly bec-oming committed to MST-like regions.