How does Simulated Annealing help avoid getting stuck in a local minimum?
Simulated Annealing helps avoid getting stuck in a local minimum by probabilistically accepting worse solutions, especially in the early stages of the search. This acceptance is controlled by a parameter called 'temperature', which starts high and gradually decreases, allowing the algorithm to explore the solution space more broadly before converging.
Conditions
- Requires an initial solution and a high initial temperature.
- Uses a cooling schedule to gradually decrease the temperature.
- Employs an acceptance criterion to decide whether to accept a worse solution based on the current temperature.
Reasoning, step by step
- Start with an initial solution and a high temperature.
- Propose a change to the solution.
- If the change improves the solution, accept it.
- If the change worsens the solution, accept it with a probability that depends on the current temperature.
- Gradually decrease the temperature according to a cooling schedule.
- Repeat until the temperature is low and the solution has converged.
Example
The video animates Simulated Annealing on a map with about 100 cities, showing the temperature decreasing from 96.53 to 7.04, while the distance generally decreases from 85162 km to 29126 km, occasionally increasing when a worse solution is accepted.
Common misconceptions
- Believing that Simulated Annealing always accepts worse solutions.
- Assuming that the temperature parameter has no effect on the probability of accepting worse solutions.
Watch the explanation
1:33 – 1:59Watch this moment ↗
Explore next
Answers are generated from source material and independently checked. Consult the original video or creator if something is unclear.