What is a local search algorithm? Give two examples.
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.
What is hill climbing search?
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.
What is simulated annealing search?
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.”
What is the process of an evolutionary algorithm?
Population initialization
- > fitness function calculation —–
- > crossover |
- > mutation |
- > survivor selection ——————->
- > terminate & return best result
Name 3 things necessary for an EA to work.
- A way to represent solutions (phenotypes) as strings of symbols (genotypes).
- A fitness function that maps genotypes to phenotypes and maps phenotypes to a measure of “fitness”.
- Operators to reproduce and vary individual genotypes in such a way that inheritance of traits occurs.
How can you maximise an EA?
Crossover -> randomised average of parents
Mutation -> small random perturbation
