Simulated Annealing Rough

Simulated Annealing is a metaheuristic: it sometimes accepts worse neighbors, controlled by a decreasing temperature. The goal is to escape local minima.

It is not an exact algorithm; parameters (temperature schedule) are counted.

$$P=\exp(-\Delta/T)\quad(\Delta\gt 0)$$

Where used

Heuristic for hard optimization problems (layout, scheduling) when exact search is too costly. Industrially related to other metaheuristics.

Depth

Simulated Annealing is a stochastic search heuristic. A neighbor solution is generated from the current solution. Improvements are accepted, and deteriorations can also be accepted with a probability that depends on temperature and loss of quality.

At the beginning, a high temperature allows for broad exploration. A cooling schedule later reduces the probability of unfavorable steps and stabilizes the search. The quality of the result depends on the neighborhood, the starting solution, the temperature scale, and the available runtime; a finite execution does not generally guarantee an optimum.

Difficulty levels

1. Define the neighborhood and evaluation function of a problem.
2. Compare acceptance probabilities qualitatively with temperature.
3. Adjust cooling and the number of repetitions experimentally.

Pitfalls

Cooling too quickly makes the procedure nearly deterministic early on. Cooling too slowly consumes a lot of time without stabilization. An unsuitable neighborhood can also make important areas practically unreachable.