Session:

LBP - Late Breaking Papers

Title:

Crossover and Mutation in Genetic Algorithms Using Graph-Encoded Chromosomes

Authors:

Sam Stone
Brian Pillmore
Walling Cyre

Abstract:

Abstract. Graph chromosomes provide an elegant and flexible structure whereby genetic algorithms can encode applications not easily represented by the conventional vector, list, or tree chromosomes. While general-purpose mutation operators for graph-encoded genetic algorithms are readily available, a graph-encoded GA also requires a general-purpose crossover operator that enables the GA to efficiently explore the search space. This paper describes the existing graph crossover operators and proposes a new crossover operator, GraphX. By operating on the graph's representation, rather than the graph's structure, the GraphX operator avoids the unnecessary complexities and performance penalties associated with the existing fragmentation/recombination operators. Experiments verify that the GraphX operator outperforms the traditional fragmentation/recombination operators, not only in terms of the fitness of the offspring, but also in terms of the amount of CPU time required to perform the crossover operation.