9.2: Runtime Analysis

Goal of design and analysis of algorithms

• Correctness

• Computational complexity

Goals of evolutionary algorithms

• Convergence

• Time complexity

Schema Theory

Proposed to understand the behaviour of the simple genetic algorithm - cannot explain performance or limit behaviour of EAs.

Convergence

Ideally, the EA should find the solution in finite steps with probability 1. If the solution is held forever often, the algorithm has converged to the optimum.

Conditions for Convergence

• Positive probability to reach any point in the search space from any other point.

• Best found solution is never removed from the population.

Canonical GAs vs Elitist GAs

Canonical GAs (mutation, crossover, proportional selection) do not converge - Elitist GAs do converge.

Runtime of an EA

A random variable, Tf:

• Estimating E(Tf), the expected runtime of the EA for f;

• Estimating P(Tf <= t), the success probability of the EA in t steps for f.

(u + L) EA

Initialise P0 with u individuals chosen uniformly at random from {0, 1}^n.

for t = 0, 1, 2, … until the stopping condition is set, do:

1. Create L new individuals by:

   1. Choosing x in P_t uniformly at random

   2. Flipping each bit in x with probability p

2. Creating the new population P_(t + 1)

   1. Choosing the best u individuals out of u + L

u in (u + L) EA

Population size.

L in (u + L) EA

How many new individuals to generate.

(1 + 1) EA

Initialise x uniformly at random from {0, 1}^n.

do:

1. Create x’ by flipping each bit in x with p = 1/n.

2. If f(x’) >= f(x) then:

   1. x = x’

Until the stopping condition is met.

Fitness-Based Partitions

A tuple (A1, A2, …, Am) is an f-based partition of f : X → R if:

• A1 U A2 U … U Am = X

• Ai and Aj is empty for i ≠ j

• f(A1) < f(A2) < … < f(Am)

• f(Am) = max_x f(x)