Finite Populations Induce Metastability in Evolutionary Search

Erik van Nimwegen, James P. Crutchfield, and Melanie Mitchell

96-08-054

We introduce an analytical model that predicts the dynamics of a simple evolutionary algorithm in terms of the flow in the space of fitness distributions. In the limit of infinite populations the equations of motion are derived in closed form. We show how finite populations induce periods of stasis---"fitness epochs"---and rapid jumps---"innovations." The analysis identifies the epochs with the flow's metastable fixed points and gives exact predictions of epoch fitness level, duration, and population distribution.