1 16-AdvancedTheory

2 Theory

3 Introduction

EAs are complex systems, involving random factors

Makes it difficult to give verifiable insights into EA behavior

4 The schema theorem

5 The schema theorem SGA (1/3)

Pd ( H,x ) = probability that the action of operator x on an instance of schema H is to destroy it

Ps(H) = probability that a string containing an instance of H is selected

Holland applied analysis on SGA using fitness proportional parent selection, one-point crossover (1X), bitwise mutation, generational survivor selection

For genotype of length l that contains an example of schema H:

Probability of a schema being selected:where n( H,t ) is the number of examples, f(H) the fitness of the schema H an the mean population fitness

Expected number of instances of H in population after selection is:

Proportion of individuals representing schema H at subsequent time-steps is:where pc and pm are probabilities of applying crossover and bitwise mutation

Schema theorem: schemata of above-average fitness would increase the number of instances from generation to generation: m( H ,t+1) > m( H,t )

6 Other analyses

Walsh functions

Building block hypothesis

Markov chain analysis

Statistical mechanics approach

Reductionist approaches

7 Analyzing performance in continuous space

Theory more advanced than with discrete search spaces

G. Rudolph has shown existence of global proofs of convergence

Progress rate : distance of the center of mass of the population from the global optimum as a function of time

Quality gain : expected improvement in fitness between generations

8 No Free Lunch (NFL) theorem