1 16-AdvancedTheory

2 Theory

• Motivation
• Analyzing performance in binary space
  • Schema theorem
• Analyzing performance in continuous space
• No Free Lunch theorem

3 Introduction

EAs are complex systems, involving random factors

Makes it difficult to give verifiable insights into EA behavior

4 The schema theorem

• 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

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

• 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