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

with f ( H ) representing the fitness of schema H , the mean population fitness
<f> , the defining length d ( H ) 3 and the order o ( H ) 4 , the probability p c of
applying crossover and the probability p m to apply bitwise mutation.

Building Block Hypothesis

The analysis of the schema theorem has led to the BBH [47]. Broadly speaking
the BBH assumes that low-order schemata compete among each other and com-
bine to higher order schemata until the globally optimal solution is produced.
Goldberg claims that the BBH is supported by the above mentioned schema
theorem. Experiments have been performed which seem to be inconsistent with
the BBH, i.e. they show that uniform crossover performs better than 1-or 2-
point crossover. But uniform crossover has a very disruptive effect on strings
and blocks. In chapter 6 we try to catch the building blocks with self-adaptive
crossover.

Dynamical Systems Analysis

In order to describe the amelioration success of an ES local performance measures
are necessary. They are expected values of population states and enable the
evaluation of the local amelioration power of the ES, i.e. the success between
two consecutive generations [18]. The quality gain measures the progress in the
fitness space whereas the progress rate is a local performance measure in the
object parameter space. The progress rate ϕ is defined as the expected distance
change Δr of the parental population centroid toward the optimum y in the
object parameter space [18]

ϕ := E [ Δr ]= R ( g ) R ( g +1)

− (2.17)

with

Δr := r ( g ) r ( g +1)

− (2.18)

and

r ( . ) := y

( . )
p

y − . (2.19)

The capital R = E [ r ] denotes the expected value of the lower case letter r denot-
ing a random variable. Calculating ϕ is dicult and therefore mainly analyzed
for the sphere function F ( y )= c

α ,

R N and for the ridge function
class [15]. The sphere function is totally symmetric and its fitness values only
depend on the distance R to the optimum. Hence, the one-dimensional dynamic
of R reduces dynamics of N dimensions. Using an ES with isotropic Gaussian

y y ∈

3 The defining length d ( H ) of a schema is the distance between the outermost defined
positions of the schema parts.
4 The order o ( H ) of a schema is the number of positions which do not exhibit the #
symbol.