- Motivation
- Analyzing performance in binary space
- Schema theorem

- Analyzing performance in continuous space
- No Free Lunch theorem

EAs are complex systems, involving random factors

Makes it difficult to give verifiable insights into EA behavior

- Analysis developed by Holland
*Schema*: hyperplane in the search space# is ‘don’t care’ symbol

- Example: 11###
- Schema can have instances (for example total of 8)
- Fitness of schema is mean fitness of instances

- Implicit parallelism: population will usefully process
*O(μ**3**)*schemata, where*μ*_ _ is the population size - Order: number of positions not having the # sign
- Defining length: distance between outermost defined positions
*H*= 1##0#1#0,*o(H)*= 4,*d(H)*=8-1=7

*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* *)*

Walsh functions

Building block hypothesis

Markov chain analysis

Statistical mechanics approach

Reductionist approaches

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

- The NFL theorem allows to make statements about the comparative
performance of different algorithms across all problems: they are all
the same
- When a new algorithm is the best for a class of problems, it will perform poorly on other classes
- For a given problem circumvent NFL by adding problem-specific knowledge