Phase Transitions and Symmetry Breaking in Genetic Algorithms with Crossover Export

@article{citeulike:1750028, 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.}, author = {Rogers, A. and Pr\"{u}gel-Bennett, A. and Jennings, N. R.}, citeulike-article-id = {1750028}, citeulike-linkout-0 = {http://eprints.ecs.soton.ac.uk/12413/}, journal = {Theoretical Computer Science}, keywords = {crossover, evolutionary-computation, genetic-algorithm, metaheuristic, mutation, operator, parameter-setting, phase-transition}, month = {April}, number = {1}, pages = {121--141}, posted-at = {2007-10-10 12:22:33}, priority = {5}, title = {Phase Transitions and Symmetry Breaking in Genetic Algorithms with Crossover}, url = {http://eprints.ecs.soton.ac.uk/12413/}, volume = {358}, year = {2006} }

TY - JOUR ID - citeulike:1750028 L3 - citeulike-article-id:1750028 N2 - 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. IS - 1 JF - Theoretical Computer Science EP - 141 TI - Phase Transitions and Symmetry Breaking in Genetic Algorithms with Crossover VL - 358 SP - 121 KW - crossover KW - evolutionary-computation KW - genetic-algorithm KW - metaheuristic KW - mutation KW - operator KW - parameter-setting KW - phase-transition AU - Rogers, A AU - Prügel-Bennett, A AU - Jennings, NR PY - 2006/04// UR - http://eprints.ecs.soton.ac.uk/12413/ ER -