Pruefer Numbers: A Poor Representation of Spanning Trees for Evolutionary Search

摘要

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. Priifer 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 Priifer 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 Priifer numbers and compare Priifer numbers with other codings in evolutionary algorithms for four problems that involve spanning trees. Our conclusion is definite: Priifer numbers cause poor performance in evolutionary algorithms and should be avoided.