Intro to ML: Evolutionary Algorithms

If we have elitism in our evolutionary algorithm, which of the following is TRUE:

• The next generation completely replaces the current generation

• The fitness of the population’s best individual cannot decrease

• We use a mix of the current and new generations, typically using 10% of the new generation

Answer explanation

Recall, Elitism is when a small fraction (usually 10%) of the previous population is kept for the next round, ensuring that best performance of an individual in the population cannot decrease. If the kids disappoint mum or dad can step in!

Which of the following statements are true about Novelty Search:

• Novelty Search requires a fitness function

• Novelty Search requires a behavioural descriptor

• The novelty archive stores all the encountered types of solutions

• The novelty archive keeps only the best solution found.

Answer explanation

Check definitions in slides. Novelty is simply a search for new behaviours. Contrast this with Novelty Search with Local Competition (NSLC).

Which of the following statements about Selection Operators is FALSE?

For each selection:

• With the roulette wheel: an individual with twice the fitness of another individual is twice as likely to be selected

• With a simple tournament: The individual with the most fitness will always be selected

• With a simple tournament: The individual with the least fitness will never be selected

Answer explanation

Simple tournament selection operators choose random pairs of individuals and pick the best individual from this randomly selected group. The best performing individual maybe never get selected and you need to be at least the second worst in the population to hope to be the best in the randomly selected pair.

How can you deal with a fitness function that may take negative values in a roulette wheel selection operator:

• It is not possible to use the roulette wheel in these cases

• We can scale the fitness values between 0 and 1 and then use the roulette wheel as per usual

• Use the roulette wheel as per usual

Answer explanation

A negative fitness, if naively inputed into a roulette wheel, could yield negative probabilities which does not make sense.

Which of the following would be the best fitness function for a robot trying to drive a car without crashing it:

• The number of crashes while driving

• Miles driven without crashes

• Time spent in the car

Answer explanation

'Time spent in car' would allow for collapse, where the trivial solution of not moving anywhere would be favourable. And I hope you can realise that 'number of crashes per mile' is not something we want to maximise - remember we maximise the fitness function in the Evo setting!

When using the cross-over operator, if one of the children is the same as one of the parents, then both of the parents must be identical

• True

• False

Answer explanation

consider these 2 parents with a cross over point at 'x'

parent 1: 0100x100001

parent 2: 0100x111010

Child 1: 0100111010

Child 2: 0100100001

Without additional mechanisms in place, like diversity preservations, an EA can get stuck at local optimums like just like gradient descent.

• True

• False

Answer explanation

EAs do not explicitly favour diversity therefore populations often have similar characteristics. Even though noise can be injected through steps such as tournament selection, crossover and mutation, this might not be enough to push the population under the local maxima. It is important to note that while diversity schemes are aimed at overcoming local maxima, they too can get stuck!

The cross-over operator is mandatory in Evolutionary Algorithms

• True

• False

Answer explanation

Check slides

Which of the following statements are true about the concept of behavioural descriptor:

• It is used to define different types of solutions

• It is used to compute distances between solutions

• It always includes the fitness function

• It is never related to the fitness function

Answer explanation

e.g. Novelty search vs NLSC