Punctuated Equilibria in Simple Genetic Algorithms for Functions of Unitation
Sangyeop Oh
Electronic mail address: syoh@camars.kaist.ac.kr.
Hyunsoo Yoon
Electronic mail address: hyoon@camars.kaist.ac.kr.
Department of Computer Science,
Korea Advanced Institute of Science and Technology,
Advanced Information Technology Research Center,
Yoosung-goo, Daejon, Korea
Abstract
During a genetic search, the population may get stuck in a local optimum. The population can escape from this after a long duration. This phenomenon is called punctuated equilibrium. The punctuated equilibria observed in nature and computational ecosystems are known to be well described by diffusion equations. In this paper, simple genetic algorithms are theoretically analyzed to show that they can also be described by a diffusion equation when fitness is the function of unitation. Using theoretical results on the diffusion equation, the duration of equilibrium is shown to be exponential of such parameters as population size, 1/(mutation probability), and potential barrier. This is corroborated by simulation results for one-dimensional bistable potential landscapes with one local optimum and one global optimum.
