Evolutionary Algorithms - Self-Adaptive Heuristics for Evolutionary Computation - page 24

mutations σ and a given parental state R [18], the progress rate ϕ only depends
on the parameters R , N and σ in the following way:

ϕ ∗ := ϕ N
R

and σ ∗ := σ N
R

(2.20)

Using these normalizations it can be shown that the normalized progress rate ϕ ∗
depends only on the normalized step size σ ∗ and the search space dimension N .
But as the dependency on N is quite weak the asymptotic case N

,ϕ ∗ =

→∞

f ( σ ∗ ) often suces [18].
Michael Vose's dynamical systems approach belongs to the infinite population
models [155]. This approach models EAs in infinite search spaces. It makes use
of a vector whose components represent the proportion of the population of a
certain type. A mixing matrix represents the operators mutation and recombina-
tion while a selection matrix represents the selection operator and the objective
function. Research concentrates on the formulation of models for the matrices
and various interesting results can be gathered from this kind of analysis.

Statistical Mechanics Analysis

The statistical mechanics analysis is a macroscopic approach assuming that a
number of variables influence the whole system similar to the modeling of com-
plex systems in physics [138]. It allows the analysis of the mean and variance of
a population. Although its results are very accurate predicting the behavior of
real EAs the analysis is restricted to the above mentioned features.

Markov Chain Analysis

The evolutionary system can be seen as a stochastic process [38], i.e. as a time-
discrete Markov chain if a couple of conditions are fulfilled. Each state represents
the different possible populations. Among the conditions is that the system can
at any time be characterized by a certain state and that the state transitions
depend on the current state exclusively regardless from the past sequence of
states. From this condition a transition matrix M canbeformulatedwhose
entry M ij gives the probability to move from state i to state j in one step. The
( i, j )-th entry of the matrix M n contains the probability to move from state i to
state j in n steps. Markov chains have been analyzed extensively in the past and
many results from this analysis can be applied to EAs. An example is the result
of Rudolph [124]: a GA with nonzero mutation and elitism will always converge
to the global optimum, but not necessarily without elitism.

Runtime Analysis

The runtime analysis of EAs concentrates on the analysis of the number of gen-
erations until the optimum can be found. The research concentrates on showing