On the Movement of Vertex Fixed Points in the Simple GA

ABSTRACT The Vose dynamical system model of the simple genetic algorithm models the behavior of this algorithm for large population sizes and is the basis of the exact Markov chain model. Populations consisting of multiple copies of one individual correspond to vertices of the simplex. For zero mutation, these are fixed points of the dynamical system and absorbing states of the Markov chain. For proportional selection, the asymptotic stability of vertex fixed points is understood from previous work. We derive the eigenvalues of the differential at vertex fixed points of the dynamical system model for tournament selection. We show that as mutation increases from zero, hyperbolic asymptotically stable fixed points move into the simplex, and hyperbolic asymptotically unstable fixed points move outside of the simplex. We calculate the derivative of local path of the fixed point with respect to the mutation rate for proportional selection. Simulation analysis shows how fixed points bifurcate with larger changes in the mutation rate and changes in the crossover rate