Prüfer numbers: a poor representation of spanning trees for evolutionary search

Abstract

The most important element in the design of a decoder-based evolutionary algorithm is its genotypic representation. The genotype decoder pair must exhibit efficiency, locality, and heritability to enable effective evolutionary search. Prüfer numbers have been proposed to represent spanning trees in evolutionary algorithms. Several researchers have made extravagant claims for the usefulness of this coding, but others have pointed out that Prüfer numbers, though concise and easy to decode, lack the essential properties of locality and heritability. This conflict motivates our study. We examine the properties of Prüfer numbers and compare Prufer numbers with other codings in evolutionary algorithms for four problems that involve spanning trees.