.png){kind=icon}
.png){kind=icon}
Return
Symmetry breaking in population-based optimization
.png){kind=icon}
PRE
AI
DOI：10.1109/TEVC.2003.819419.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper argues that the performance of evolutionary algorithms working on hard optimization problems depends strongly on how the population breaks the symmetry of the search space. The splitting of the search space into widely separate regions containing local optima is a generic property of a large class of hard optimization problem. This phenomenon is discussed by reference to two well studied examples, the Ising perceptron and the satisfiability problem (K-SAT). A finite population will quickly concentrate on one region of the search space. The cost of crossover between solutions in different regions of search space can accelerate this symmetry breaking. This, in turn, can dramatically reduce the amount of exploration, leading to suboptimal solutions being found. An analysis of symmetry breaking using diffusion model techniques borrowed from classical population genetics is presented. This shows how symmetry breaking depends on parameters such as the population size and selection rate.
Keywords:
crossover
diffusion equations
evolutionary algorithms (EAs)
landscapes
replica symmetry
symmetry breaking
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
12
Papers:
1.8K
Citations:
2.4W
Organization
No organization information available