This descending bearing system gave birth to the Metropolis algorithm of 1953 and then to simulated annealing by IBM in 1983.
The algorithm step by step
- To take an initial solution R=R0 and an initial temperature T=T0. The initial state is obtained by a heuristic (descent or greedy).
- Generating a random solution R(i+1) in the neighborhood of the current solution:
- To compare R(i+1) and Ri with Metropolis rule
- To repeat until you find a stable solution (or after a certain number of iterations)
- To decrease the temperature T to a threshold temperature Tmin, or to a stable solution.
Since T is large at the beginning, many solutions degrading the current solution can be chosen. This allows to escape from a local optimum. The following figure presents the value of the objective function. The temperature makes it possible to « jump » to a less « good » zones to exit a « valley ». The balls and signals in the following figure show up to what height the balls can « jump », that is to say the tolerance of negative variation of the objective function in obtaining a new solution.
If the temperature is low, it is more difficult to escape from a local optimum: