Week 2 Flashcards
Different EA types
Generational
Steady state
Elitist
What are Recombination (crossover) techniques
Single-point
Multi-point
Uniform
Different EA selection techniques
Rank-based
Roulette-based
Tournament
Different Replacer techniques
Weakest
First weaker
Different Mutation techniques
Single Gene
Multiple Gene
Different EA parameters
Population size
Generations/iterations
Mutation rate
Crossover rate
Tournament size
What is Hillclimbing
Generate random solution
Mutate a copy, evaluate the fitness,
If the mutant is not worse, replace solution with mutant
If a termination condition is reached, stop. Else repeat.
What is a neighbourhood?
The set of all possible mutants of s.
What is a typical landscape
The huge majority of landscape has poor fitness, there are tiny areas where decent solutions lurk. Big random changes are very likely to take us away from nice areas.
Most are multimodal
4 types of landscape
Unimodal
Plateau
Multimodal
Deceptive
What problems does Hillclimbing have with typical landscapes?
Needs to allow downhill moves - a family of methods called local search does this
Have a population - so we can have poor solutions around and give them a chance to develop
Types of local search
Monte-carlo (accept x with some random probability if its worse)
Tabu search (evaluate all immediate neighbours of c, choose the best to be the next solution (even if not improving, unless it is recently visited, then choose next best)
Problems with local search
Gets stuck in local optima (less than HC though)
What is Population-Based search?
Rather than having a single current solution we have a population of them. (multiple generations of populations)
This means we need a selection method to choose the ones to mutate
With more than one solution available we can mate, recombine, crossover etc two or more solutions.
What are the 2 types of genetic algorithm?
Generational
Steady-state
Generational genetic algorithm
Genetic operators applied repeatedly to generate new population
Generational elitist algorithms copy n best individuals unchanged to the next generation.
Steady state genetic algorithm
Genetic operators applied N times (N small, 1 or 2) and bad solutions replaced.
What is weakest first replacement?
Find first solution in population which is weaker than new solution and replace it.
What is roulette wheel selection?
Spinning a roulette wheel of solutions with sectors proportional to fitness.
Doesnt work when we are trying to minimise fitness or negative fitness
Requires similar scaling
What is rank-based selection?
Fitnesses in the pop are ranked from popsize (fittest) down to 1 (least fit)
Selection probabilities are proportional to rank.
Can power the rank to bias it.
What is tournament selection?
Choose t individuals randomly
Choose the best of the t individuals
Very tunable
Avoids superfit/superpoor
Very simple to implement and efficient
- needs to tune tournament size param
Why do we need good selection methods
Exploitation vs exploration
Represent our strategy for deciding which areas of the search space to focus our efforts on
How can we encode a chromosome of a solution
Integer vectors
Binary strings
Real values
Permutations
Trees
What is single gene mutation
Choose a gene at random, change it to a new value e.g. 352782 -> 312872
M-gene is multiple instances of this
