Genetic algorithm dynamics in two-well potentials with basins and barrier
Jonathan Shapiro, Adam Prügel‐Bennett · ePrints Soton (University of Southampton) · 1997
The dynamics of a simple genetic algorithm is analyzed on a simple two-well function of unitation. In the infinite population limit, there are phase transitions in the dynamics as the selections strength and crossover probability are changed. In one phase, the system always evolves to a population consisting only of strings from the local well starting from any initial population consisting some strings from the local well. In the second phase, the genetic algorithm can evolve to a population consisting of strings from the global well, but only if a finite fraction of the initial population was from the global well. In the third phase, the algorithm will evolve to a population consisting of stings from the global well from any initial population. For a finite population, the increasing correlation of the population changes the nature of the transition; this is analysed in a weak selection limit where the effects are small. Fluctuation effects, which cause the transition to be smooth in a finite population and are important, are not analyzed here. Comparison with simulations show that the results are qualitatively correct. There is a phase in which the GA evolves quickly to the global minimum, which can be orders of magnitude faster than a Monte Carlo algorithm; and another phase in which it evolves to a population dominated by strings from the local well. Quantitatively, the simulations and theory are not in good agreement due to the simplifications of the theory.