Heuristics and metaheuristics
Looking for a good solution when the best is out of reach: greedy, local search and local optimum, then simulated annealing, tabu search and the genetic algorithm, and the trade-off between quality and computing time.
- 26 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
A few cards from the deck
Heuristic: what is it?
Show the answer
A method designed for a specific problem that quickly finds a good solution without guaranteeing that it is the best.
It is accepted when the optimum is too costly to compute: the nearest neighbour for a tour is an example.
Current solution of cost 14 (minimising). Its four neighbours cost 15, 16, 13 and 17, and the one of cost 13 is tabu (no aspiration criterion). Which neighbour does tabu search pick?
- The one of cost 15, even though it worsens the solution
- The one of cost 13, because it improves the solution even though it is tabu
- None: the current solution is a local optimum, the search stops
- The one of cost 17, to move as far as possible from the current solution
Show the answer
The one of cost 15, even though it worsens the solution
Tabu search takes the best non-forbidden neighbour, even if it worsens: 15. That worsening lets it leave a local optimum. The reverse move is then added to the tabu list, to prevent going back.
In simulated annealing, a neighbour worse by Δ is accepted with probability …, where T is the ….
Show the answer
In simulated annealing, a neighbour worse by Δ is accepted with probability e^(−Δ/T), where T is the temperature.
The larger Δ, the smaller the probability; the larger T, the closer to 1. A better neighbour is always accepted.
Metaheuristic: what is it?
Show the answer
A general search strategy, applicable to many different problems, which steers a heuristic so that it escapes mediocre solutions.
It does not depend on one problem: only the representation of a solution and the definition of a neighbour change. Simulated annealing, tabu search and the genetic algorithm are three examples.