The Dandelion code: A new coding of spanning trees for genetic algorithms

There are many applications where it is necessary to find an optimal spanning tree. For several of these, recent research has suggested the use of genetic algorithms (GAs). Historically, the Prufer code has been one of the most popular representations for spanning trees, due largely to the bijective mapping between genotype and phenotype. However, it is has attracted much criticism for its low locality, a primary reason for its poor performance in GAs. Other representations such as direct encoding and network random keys have been shown to be far more effective. In 2001, an alternative called the Blob code was identified and adapted for use in GAs. It was shown to exhibit significantly higher locality than the Prufer code. For a simple test problem, a GA using the Blob code was found to substantially outperform one using the Prufer code. This paper suggests an alternative called the Dandelion code, which is more efficient and exhibits yet higher locality. Although both direct encoding and NetKeys are shown to give better results on the test problems used in this paper, the Dandelion code should be considered as a strong alternative, particularly for very large networks.