Evolutionary Algorithms
Main features of evolution (simplified):
- Population of individuals
- Reproduction with inheritance
- Genetic variation
- Natural selection
We can frame evolution as an algorithmic process with the above factors.
See slide 12 for a reading that criticises the use of metaphors in natural computing.
General Genetic Algorithm (CGA)
- Population with candidate solutions
- Evaluate candidate quality
- Iterate until termination
- Select candidates for reproduction
- Recombine selected candidates
- Mutate resulting candidates
- Evaluate new candidates
- Select candidates for the next generation
Termination conditions:
- Satisfying candidate solution
- Predefined number of iterations/generations reached
- Population converged on some level of individual variation
Canonical Genetic Algorithm (CGA)
The following design choices result in CGA:
- Binary representation
- Fixed population size
- Evaluation function
- Roulette wheel selection
- Single point crossover
- Point mutation
- Entire population replaced at each iteration ("generation gap")
Design choices
- How to represent candidates
- Population size and initialization
- Evaluation (fitness) function
- Candidate selection mechanism
- ...
- ...
Variation operators
Crossover operator
- Two individuals randomly chosen from mating pool
- Crossover with probability $p_c=1$
- Crossover point chosen randomly
- Swap the chromosomes after the selected crossover point
Mutation
- Applied on bit-by-bit bases (per 'gene')
- Each gene mutates with some low probability e.g. $p_m=0.001$
Evaluation CGA
- CGA does not converge to a global optimum
- CGA with addition of elitist selection scheme (the best individual of the previous generation always survives) we do have convergence to a global optimum.
Schema Theorem
Schema represents a set of candidate solutions, for canonical: a set of binary strings.
H = 0*11* with * being a wildcard matches a set of candidate solutions, e.g. 00110, 01110
The string 10 of length $l=2$ belongs to $2^l$ different schemas.
- Schema theorem serves as the analysis tool for the GA process
- Explain why GAs work by showing the expectation of schema survival
- Applicable to CGA
We will analyse how schema's evolve over time.
And we want to know if a schema is disrupted.
Schema order o(H)
The order of a schema is the number of its fixed bits, i.e. number of bits that are not wildcard * in the schema H.
Example: If H = 0*1 then o(H)=2.
A schema with a higher order (so more fixed bits) is easier to disrupt.
Schema length d(H)
The defining length of a schema is the difference between its last and first fixed string position.
d(H=*1*01)=5-2=3
Easier to disrupt for larger lengths (due to being more susceptible to crossover)
Fitness
Average fitness, see slide 32.
- m(H,k): n instances of H in population at generation k
- m(x,k): n copies of x in population at generation k
- f(x) fitness of x
Effects on Schema in CGA
Assume selection proportional to fitness.
See slide 35.
Schemas with fitness greater than the population average are likely to appear more in the next generation.
Stopped taking notes