Illinois Genetic Algorithms Laboratory

Gaube, T., Rothlauf, F. (2001)
TR No.: 2001011 | Download PDF | Download PS

Abstract:
When using genetic and evolutionary algorithms (GEAs) for the optimal communication
spanning tree problem, the design of a suitable tree network encoding is crucial for
finding good solutions. The link and node biased (LNB) encoding represents the structure
of a tree network using a weighted vector and allows the GEA to distinguish between the
importance of the nodes and links in the network. This paper investigates whether the
encoding is unbiased in the sense that all trees are equally represented, and how the
parameters of the encoding influence the bias. If the optimal solution is
underrepresented in the population, a reduction in the GEA performance is unavoidable.
The investigation reveals that the commonly used simpler version of the encoding is
biased towards star networks, and that the initial population is dominated by only a few
individuals. The more costly link-and-node-biased encoding uses not only a node-specific
bias, but also a link-specific bias.
Similarly to the node-biased encoding, the link-and-node-biased encoding is also biased
towards star networks, especially when using a low weighting for the link-specific bias.
The results show that by increasing the link-specific bias, that the overall bias of the
encoding is reduced.
If researchers want to use the LNB encoding, and they are interested in having an
unbiased representation, they should use higher values for the weight of the
link-specific bias. Nevertheless, they should also be aware of the limitations of the
LNB encoding when using it for encoding tree problems. The encoding could be a good
choice for the optimal communication spanning tree problem as the optimal solutions tend
to be more star-like. However, for general tree problems the encoding should be used
carefully.