Week 2

Question 1

Different EA types

Answer 1

Generational
Steady state
Elitist

Question 2

What are Recombination (crossover) techniques

Answer 2

Single-point
Multi-point
Uniform

Question 3

Different EA selection techniques

Answer 3

Rank-based
Roulette-based
Tournament

Question 4

Different Replacer techniques

Answer 4

Weakest
First weaker

Question 5

Different Mutation techniques

Answer 5

Single Gene
Multiple Gene

Question 6

Different EA parameters

Answer 6

Population size
Generations/iterations
Mutation rate
Crossover rate
Tournament size

Question 7

What is Hillclimbing

Answer 7

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.

Question 8

What is a neighbourhood?

Answer 8

The set of all possible mutants of s.

Question 9

What is a typical landscape

Answer 9

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

Question 10

4 types of landscape

Answer 10

Unimodal
Plateau
Multimodal
Deceptive

Question 11

What problems does Hillclimbing have with typical landscapes?

Answer 11

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

Question 12

Types of local search

Answer 12

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)

Question 13

Problems with local search

Answer 13

Gets stuck in local optima (less than HC though)

Question 14

What is Population-Based search?

Answer 14

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.

Question 15

What are the 2 types of genetic algorithm?

Answer 15

Generational
Steady-state

Question 16

Generational genetic algorithm

Answer 16

Genetic operators applied repeatedly to generate new population
Generational elitist algorithms copy n best individuals unchanged to the next generation.

Question 17

Steady state genetic algorithm

Answer 17

Genetic operators applied N times (N small, 1 or 2) and bad solutions replaced.

Question 18

What is weakest first replacement?

Answer 18

Find first solution in population which is weaker than new solution and replace it.

Question 19

What is roulette wheel selection?

Answer 19

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

Question 20

What is rank-based selection?

Answer 20

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.

Question 21

What is tournament selection?

Answer 21

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

Question 22

Why do we need good selection methods

Answer 22

Exploitation vs exploration
Represent our strategy for deciding which areas of the search space to focus our efforts on

Question 23

How can we encode a chromosome of a solution

Answer 23

Integer vectors
Binary strings
Real values
Permutations
Trees

Question 24

What is single gene mutation

Answer 24

Choose a gene at random, change it to a new value e.g. 352782 -> 312872
M-gene is multiple instances of this

Question 25

What is uniform crossover

Answer 25

Generate a random binary mask
Use it to decide which genes swap and which stay.