Local Search and Evolutionary Algorithms

Question 1

What is a local search algorithm? Give two examples.

Answer 1

An algorithm where the path to the goal is irrelevant, the goal state is the solution. The state space is the set of “complete” configurations. It keeps a single current state and tries to improve it, e.g. hill climbing search and simulated annealing search.

Question 2

What is hill climbing search?

Answer 2

Choose a random point on the function, look at the neighbourhood N (a range of points either side of it), and chooses the side with the highest node. It will keep choosing the highest node until a maxima is reached, i.e. it only goes down on each side. It can, however, get stuck a local maxima.

Question 3

What is simulated annealing search?

Answer 3

Like hill climb search, but occasionally taking downward steps to explore the state space.

“Escape local maxima by allowing some ‘bad’ moves but gradually decrease their frequency.”

Question 4

What is the process of an evolutionary algorithm?

Answer 4

Population initialization

• > fitness function calculation —–
• > crossover |
• > mutation |
• > survivor selection ——————->
• > terminate & return best result

Question 5

Name 3 things necessary for an EA to work.

Answer 5

1. A way to represent solutions (phenotypes) as strings of symbols (genotypes).
2. A fitness function that maps genotypes to phenotypes and maps phenotypes to a measure of “fitness”.
3. Operators to reproduce and vary individual genotypes in such a way that inheritance of traits occurs.

Question 6

How can you maximise an EA?

Answer 6

Crossover -> randomised average of parents

Mutation -> small random perturbation