Representing trees in genetic algorithms

Abstract

We consider the problem of representing trees (undirected, cycle-free graphs) in Genetic Algorithms. This problem arises, among other places, in the solution of network design problems. After comparing several commonly used representations based on their usefulness in genetic algorithms, we describe a new representation and show it to be superior in almost all respects to the others. In particular, we show that our representation covers the entire space of solutions, produces only viable offspring, and possesses locality, all necessary features for the effective use of a genetic algorithm. We also show that the representation will reliably produce very good, if not optimal, solutions even when the problem definition is changed.