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

artificial players [111]. Later we evolved the rules based on random initializa-
tions [112]. In both approaches mutation was implemented as bit flipping of the
grid entries. Recombination combines the rules of two different rule bases of the
population. The experiments showed that the evolved players were in most cases
comparable or better than the original artificial players of the computer game.
We successfully experimented with coevolution, i.e. the training of two EA based
players at the same time.

2.4 Theories of Evolutionary Algorithms

The theoretical analysis of evolutionary techniques is suffering from the huge
complexity of their many random factors. Current research tries to investigate
at least little insight into predictive models for the behavior of EAs as well
as providing the means for the design of ecient optimizers for given problem
classes. In the EA community there is still a lot of discussion about the rela-
tion of theoretical and experimental analysis. The work at hand is not restricted
to the experimental analysis of the proposed methods. This is why we include
this survey of theoretical EA research. Theoretical research about EAs can be
divided into the following main parts: no free lunch, building block hypothe-
sis, dynamical systems analysis, statistical systems analysis, Markov chains and
runtime analysis.

No Free Lunch

In the no free lunch (NFL) theorem Wolpert and Macready [161] showed that, if
we average over the space of all possible problems, all algorithms have the same
performance. This statement is feasible for non-revisiting algorithms with no
problem-specific knowledge. One of the important questions is whether the set
of practical problems is representative for all problems or whether it is a certain
subset for which the NFL theorem does not hold. At least algorithm engineers
should be aware that award-winning algorithms on some problems will show
poor results on other problems.

Holland's Schema Theorem:

A schema is a set of individuals with undefined genes at defined locations. It
can be seen as a hyperplane in the search space. Using the “don't care” symbol
#, 10#### is an example for a binary schema, 100101 is one possible instance
of this schema of 2 4 possible ones in this case. The schema-theorem states that
schemata with high fitness increase their number of instances within the pop-
ulation from generation to generation [38]. Let m ( H, z ) be the proportion of
individuals representing schema H at time z . The schema theorem states that
m ( H, t +1) >m ( H, t ), i.e.

1 p c ·

f ( H )
<f> ·

d ( H )
l

m ( H, t +1) ≥ m ( H, t ) · − · [1 − p m · o ( H )] (2.16)

− 1