Local Search Flashcards
What is local search?
Optimisation algorithms that are used to find the best possible solution withing a given search space.
What is the idea behind Iterative improvement algorithms?
Storing a current state and trying to improve.
What is a hill-climbing search?
From a selected point, loop continuously in the direction of increasing value (towards goal) until a peak is reached.
What search is hill climbing similar to?
Greedy search. Hill-climbing is a greedy local search.
What is simulated annealing?
Variant of hill-climbing, allows “bad” moves to escape local maxima.
How many downhill/bad moves are allowed in simulated annealing?
It gradually decreases the size and frequency of a bad move. (accepts less bad moves as time goes on)
What are some hill-climbing variations?
- Stochastic hill climbing
- First-choice hill climbing
- Random-restart hill climbing
What is stochastic hill climbing?
- Random selection among the uphill moves, ignore some neighbours
- The selection probability can vary with the steepness of the uphill move.
What is first-choice hill climbing?
A variant of stochastic hill climbing that generates successors randomly until a better one is found.
What is random-restart hill climbing?
Hill climbing with restarts in random places to avoid getting stuck in local maxima
How do we know if the best state has been reached in simulated annealing?
If the temperature T decreases slowly enough.
What is genetic algorithms?
Optimization techniques inspired by the principles of natural selection and genetics. Candidate solutions mutate/iteratively evolve towards an optimal solution.
What are the pros of genetic algorithms?
- Faster (and lower memory requirements) than searching a very large search space.
- Easy, if your candidate representation and fitness function are correct, a solution can be found without any explicit analytical work.
What are the cons of genetic algorithms?
- Randomised: not optimal or even complete
- Can get stuck on local maxima (crossovers can help mitigate this)
- Hard to work out how to best represent a candidate as a bit string.
What are gradient descent/ascent algorithms?
A modification to Hill Climbing, looks at the local gradient and takes the direction of largest change. Takes steps of size proportional to the gradient.
