This article studies a stochastic model of an evolutionary algorithm
that evolves a “population” of potential solutions to a
minimization problem. The minimization process is based on two operators.
First, each solution is regarded as an individual that attempts a random search
on a graph, involving a probabilistic operator called exploration. The
second operator is called selection. This deterministic operator creates
interaction between individuals. The convergence of the evolutionary process is
described within the framework of simulated annealing. It can be quantified by
means of two quantities called the critical height and the optimal
convergence exponent, which both measure the difficulty of the algorithm to
deal with the minimization problem. This work describes the critical height for
large enough population sizes. Explicit bounds are given for the optimal
convergence exponent, using a few geometric quantities. As an application, this
work allows comparisons of the evolutionary strategy with independent parallel
runs of the simulated annealing algorithm, and it helps deciding when one
method should be preferred to the other.