Phase Transitions and Symmetry Breaking in Genetic Algorithms with Crossover
OA Location
Author(s)
Rogers, Alex
Prügel-Bennett, Adam
Jennings, NR
Type
Journal Article
Abstract
In this paper, we consider the role of the crossover operator in genetic algorithms. Specifically, we study optimisation problems that exhibit many local optima and consider how crossover affects the rate at which the population breaks the symmetry of the problem. As an example of such a problem, we consider the subset sum problem. In so doing, we demonstrate a previously unobserved phenomenon, whereby the genetic algorithm with crossover exhibits a critical mutation rate, at which its performance sharply diverges from that of the genetic algorithm without crossover. At this critical mutation rate, the genetic algorithm with crossover exhibits a rapid increase in population diversity. We calculate the details of this phenomenon on a simple instance of the subset sum problem and show that it is a classic phase transition between ordered and disordered populations. Finally, we show that this critical mutation rate corresponds to the transition between the genetic algorithm accelerating or preventing symmetry breaking and that the critical mutation rate represents an optimum in terms of the balance of exploration and exploitation within the algorithm.
Date Issued
2006
Citation
Theoretical Computer Science, 2006, 358, pp.121-141
Start Page
121
End Page
141
Journal / Book Title
Theoretical Computer Science
Volume
358
Identifier
http://eprints.soton.ac.uk/262413/
Subjects
Science & Technology
Technology
Computer Science, Theory & Methods
Computer Science
COMPUTER SCIENCE, THEORY & METHODS
symmetry breaking
phase transition
crossover
genetic algorithms
Computation Theory & Mathematics
08 Information And Computing Sciences
01 Mathematical Sciences
Notes
keywords: genetic algorithm, phase transition, symmetry breaking
Article Number
1