10 - Evolutionary Computation Review Flashcards
Evolutionary Algorithms
A subset of evolutionary computation.
In this module, assume that the difference between Evolutionary Algos and Evo Computation is..
the difference between algorithm and computation
Main idea of evo algos (steps)
Start with random initial population
- test individuals
- assign fitness
- terminate?
- select
- reproduce and mutate, repeat.
global function optimisation purpose
Find the global max or min of the function
Selection via truncation
In N individuals, select K best
Roulette Wheel Selection
Draw a random number and see whether that drops onto a particular individual
Normalise fitness
Tournament Selection
Select K random individuals, see which performs best and select that
Selection Pressure
Balance between exploitation and exploration. Chance of being selected as parent
Eg in a pop of 100.
- selecting 50 parents would be low selection pressure
- selecting 5 parents = high selection pressure
High selection pressure good or bad?
Bad, get stuck in narrow solution which doesn’t generalise well.
Good balance needed for diversity.
4 Termination Criteria
- Stop with max num of generations
- Stop with max computation time
- Stop with desired fitness value
- Stop when fitness does not improve any more
Not required
Genetic Algorithms
Encode a solution (Evo Algo) into bits.
Eg genotype [010001100] can be used to encode a 3x3 matrix which is a representation of the phenotype (solution)
n 1 2 3
1 0 1 0
2 0 0 1
3 1 0 0
Genotype vs Phenotype representation
Genotype as a matrix
Phenotype as a directed graph
9bits encode the presence of a link. 36 bits represent the value of each link
For 010 001 100
This means trhe first part is 1 to, second is 2 to and third is 3 to.
Which bits are active?
(from left) 2nd, 6th and 7th
9bits encode the presence of a link. 36 bits represent the value of each link
For 010 001 100
and 0000 1100 0000 1000 0000 0011 0100 0000 0000
What is the value on a graph between each part of the genotype? (1,2,3)
1 -> 2 = 12
2-> 3 = 3
3 -> 1 =
Why do some mutations have a larger effect than others?
Take 0000 for example
If a mutation occurs to make 0001 then that is a change of 1
If a mutation occurs to make 1000 then that is a change of 8
Evolution Strategy
(μ,λ)-ES or (μ + λ) - ES
μ size of parent pop
λ size of offspring population
, parent is not part of new gen
+ parent is part of new gen
(20,100)-ES
20 parents gen 100 children. Parents are discarded/discharged.
Each gen the top 20 individuals are selected to be parents
(1+100)-ES
Only one solution is the parent. Each gen, 100 children and the 1 parent is included (+).
Best of them becomes new parent
In Evolution Strategy, why my + be better than ,
If you’ve already found the best solution + prevents discarding it
Why is (1,1)-ES not very meaningful?
Only creates solutions randomly
Steady State ES
What is it? What is the selection pressure? Serial or parallel?
(μ+1)-ES
No generation gap. One parent generates one offspring and one individual is removed.
Low selection pressure and suited to parallel computing
Evolving the mutation rate is called
Self adaptive adaptation
Mutation rate vector tells you
what is a good mutation
(xi,sigi) for all i in {1,..,mu}
x is parameters of solution and sigi is the standard deviations for Gaussian mutations (strategy parameters)
Genetic Programming Aim
Automatic programming by creating a working program from a high-level statement of a problem
Represented by trees
Genetic Programming Definition solution
Represented as a tree whose non-leaf nodes are operators and leaf nodes are terminals
A tree captures the syntax of a formal expression. (arithmetic etc)
Operator Sets in GP
Arithmetic: + - / *
Math: sin, cos, exp
Bool: AND, OR NOT
Assignment: =
Conditional; IF THEN ELSE
Iterative: FOR, WHILE, REPEAT
Terminal Set in GP
Constants
Variables
0-arity functions: rand, go-right
; in GP
used to separate commands
IF in GP
Has 3 children
IF this, then do this, else do this
Mutation in Genetic Programming
Select a random node and replace it with a function or terminal
Crossover in GP
Taking subtrees and adding them to others
Symbolic Regression Goal
Predict by understanding how values are generated. Training weights w to approximate any function
2 Symbolic Regression difficulties
- We only have limited data
- Noise
Main characteristics of GP
- SOlution is naturally dynamic in size/complexity
- Solution can be a program itself (self improvement)
- Search space in a GP app could be considerably larger than in a fixed-length EA
- Could be used to design topology of a elec circuit
