Simulated Annealing .*;
Simulated annealing was created when researchers noticed the analogy between their search algorithms and metallurgists' annealing algorithms. The idea is to achieve a goal state without reaching it too fast. In metallurgy, for example, the process of hardening steel requires specially timed heating and cooling to make the iron and carbon atoms settle just right. In mathematical search algorithms, we want to focus on promising solutions without ignoring better solutions we might find later. In other words, we want to reduce error to the global minima without getting stuck in less successful local minima.
The basic algorithm is sweet and simple:
- Create the first solution, and get its energy value.
- While temperature > minimum temperature...
- Make a copy of the solution.
- Modify the copy.
- Get the copy's energy value.
- Keep the better of these two solutions.
- Reduce the temperature.
The algorithm stops when the temperature reaches a preset minimum value.
The important thing to keep in mind is that "keeping the better solution" does NOT necessarily mean the one with the lower energy value. If the modified copy solution turns out to be better than the previous solution, great. We're making progress. But if it's not better, how would we know, by any logic, which way to go from here? We've got to find something better than the best solution. If the best solution still contains errors, chances are we've done the best we can in one of the local minima. To get free of a local minima, we have no choice but to except worse solutions, scaling the walls of error, until we've risen out of the local minima and can begin exploring neighboring possibilities. This is where a special acceptance algorithm comes in.
We accept the better solution based on:
P = exp(-delta / Temp)
where delta is the difference between the copy's energy and the previous solution's energy.
As the temperature gradually decreases, the difference in energy values has a profound effect on acceptance. When the energy difference is low at higher temperatures, the algorithm will accept most anything. When the energy difference is high at lower temperatures, the algorithm is very discriminating.