The node-depth encoding: analysis and application to the bounded-diameter minimum spanning tree problem

Telma Woerle de Lima, Franz Rothlauf, Alexandre C. B. DelbemGECCO 2008 · DOI

TL;DR

This paper introduces and analyzes the "node-depth encoding" for representing trees in evolutionary algorithms. While the encoding's initialization process shows a bias towards trees with small diameters and star-like structures, its mutation operators are unbiased. When applied to the challenging Bounded-Diameter Minimum Spanning Tree Problem (BDMSTP), this biased initialization surprisingly doesn't consistently yield better results than an unbiased approach, though the node-depth encoding itself demonstrates competitive performance.

What Problem Does This Paper Address?

Evolutionary Algorithms (EAs) are powerful tools for complex optimization problems, especially those involving trees. However, the effectiveness of an EA heavily relies on how solutions (in this case, trees) are represented (encoded) and how genetic operators (like mutation and crossover) interact with that representation. This paper focuses on a specific tree encoding called "node-depth encoding," which combines elements of both direct and indirect representations. The authors aim to thoroughly understand the inherent biases of this encoding, particularly its initialization and mutation operators, and how these biases affect its performance on the Bounded-Diameter Minimum Spanning Tree Problem (BDMSTP). The BDMSTP is a significant problem in network design, aiming to find a minimum-weight spanning tree with a diameter no larger than a specified bound, and it's known to be NP-hard for certain diameter constraints.

Methods

The core of this paper is an in-depth analysis of the node-depth encoding.

  • Node-Depth Encoding: This encoding represents a tree as a list of (node, depth) pairs. The order of these pairs is crucial, as it dictates how the tree is reconstructed. It uses a genotype-phenotype mapping (typical of indirect encodings) but applies problem-specific search operators (typical of direct encodings).
  • Initialization Analysis: The paper investigates the initialization process of the node-depth encoding. This process involves creating a permutation of nodes and then assigning depths. The authors specifically examine if this initialization favors certain tree structures.
  • Mutation Operator Analysis: Two mutation operators, PAO (Preserve Ancestor Operator) and CAO (Change Ancestor Operator), are described. These operators work by transferring subtrees within the tree representation. The analysis focuses on whether these operators introduce any bias towards specific tree properties (like depth, diameter, or distance to MST/stars).
  • Bias Measurement: To quantify bias, the authors use several metrics:
  • Distance from MST: The number of edges differing between a generated tree and a true Minimum Spanning Tree.
  • Distance from Stars: The minimum distance to a "star" graph (where one central node connects to all others).
  • Diameter: The longest path in the tree.
  • Depth: The maximum depth of any node from the root.
  • BDMSTP Application: The node-depth encoding is then applied to the BDMSTP. Two variants of the EA are compared: one using the node-depth encoding's biased initialization (EANR) and another using an unbiased initialization based on Prüfer numbers (EANP).

Datasets

The paper uses standard Euclidean instances for the BDMSTP, sourced from Beasley's OR-library. These instances are used to evaluate the performance of the proposed EA variants. The problem sizes range from n=50 to n=1000 nodes, with various diameter bounds (k) applied. No new datasets were introduced.

Key Insights and Ideas

  • Initialization Bias is Real: The node-depth encoding's initialization process demonstrably favors trees with smaller depths and diameters, and it has a bias towards star-like structures. This is a significant finding because it means the initial population is not uniformly distributed across the search space.
  • Mutation Operators are Unbiased: In contrast to the initialization, the PAO and CAO mutation operators do not appear to introduce any bias. They maintain the statistical properties of the population, which is desirable for exploration.
  • Biased Initialization Doesn't Always Help: Counterintuitively, the bias towards small diameters in the initialization of the node-depth encoding did not consistently lead to better solutions for the BDMSTP compared to an unbiased initialization. This suggests that for complex problems like BDMSTP, the benefits of a biased initialization might be outweighed by other factors, or the bias might not align well with the problem's optimal solutions.
  • Node-Depth Encoding is Competitive: Despite the findings on initialization bias, the node-depth encoding, when used within an EA, shows good performance on the BDMSTP, often comparable to or better than other state-of-the-art algorithms, especially in terms of the number of search steps.

Key Results

  • Initialization Bias: Table 1 clearly shows that the node-depth initialization generates solutions with significantly lower average depth and diameter compared to an unbiased Prüfer number initialization. It also shows a bias towards star-like structures.
  • Mutation Unbiasedness: Figure 8 illustrates that metrics like average depth, diameter, distance to MST, and distance to stars remain relatively constant across generations when only mutation is applied, indicating no bias.
  • BDMSTP Performance: Table 2 compares the performance of the node-depth encoding EA (EANR) against other algorithms (JR-PEA, PEA-I, JR-ESEA) on BDMSTP instances. EANR achieves competitive "best" results, often with a significantly lower number of evaluations (search steps) compared to other methods. Figure 9 further shows that for larger diameter bounds (k), EANR (biased initialization) can sometimes outperform EANP (unbiased initialization), but this advantage is not consistent across all problem sizes and bounds.

Limitations and Future Work

  • Initialization Impact: The paper highlights that the biased initialization of the node-depth encoding does not systematically improve performance on the BDMSTP. This is attributed to the population size being small and many search steps being performed per individual, diminishing the initial impact.
  • Recombination: The node-depth encoding currently lacks a recombination operator, which could potentially enhance its performance by combining promising solutions.
  • Future Work: The authors suggest further exploration of the encoding's properties and its application to other tree-related problems. Investigating how to leverage or mitigate the initialization bias for specific problem types could also be a fruitful direction. The lack of a recombination operator is a clear area for future development.

Summary updated

BibTeX
@inproceedings{lima2008node,
  author = {Telma Woerle de Lima and Franz Rothlauf and Alexandre C. B. Delbem},
  title = {{The node-depth encoding: analysis and application to the bounded-diameter minimum spanning tree problem}},
  booktitle = {GECCO},
  year = {2008},
  doi = {10.1145/1389095.1389279},
}
Figure