Simulated Annealing

Simulated Annealing (SA) is a probabilistic method used to approximate the global optimum of a function.^[1] Inspired by the metallurgical process of annealing, where metal is heated and then slowly cooled to achieve a uniform crystalline structure, SA applies this concept to optimize a search process. The algorithm mimics the heating and gradual cooling to navigate towards an optimal solution, leveraging temperature as a metaphor for the search space exploration intensity.^[2]

SA cam be used to solve combinatorial problems like the TSP as demonstrated above.

The Algorithm

The state s of some physical systems, and the function E(s) to be minimized, is analogous to the internal energy of the system in that state. The goal is to bring the system, from an arbitrary initial state, to a state with the minimum possible energy.

The animation above dempnstrates the SA Algorithm searching for the maximum. Since there are many local minima here, the simple hill climb algorithm cannot be used. By cooling the temperature slowly the maximum is found.

The Basic Iteration

In Simulated Annealing, the algorithm evaluates a neighboring state s* of the current state s, and decides whether to transition to s* or remain in s based on calculated probabilities. This decision-making process favors moves towards states with lower energy.

The procedure repeats until an acceptable solution is found or the computational resources are depleted, guiding the system towards optimal or near-optimal solutions efficiently.^[3]

Acceptance Criterion

The acceptance criterion determines whether a new solution is accepted or rejected. This depends on the energy difference between the new solution and the current solution, as well as the current temperature.

The classic acceptance criterion of SA comes from statistical mechanics, and it is based on the Boltzmann probability distribution. A system in thermal equilibrium at temperature T can be found in a state with energy E with a probability proportional to:

exp(-E/ kT)

T : Temperature of a system
E : Energy of a state
k : Boltzmann Constant

The likelihood of the system adopting a high-energy state diminishes at lower temperatures, facilitating the escape from local minima to identify the global minimum. Solutions with lower energy are always accepted, while those with higher energy are accepted based on the above probability, crucial for the algorithm's ability to explore and optimize the solution space effectively.

Temperature Schedule

The temperature schedule dictates the system's temperature changes over time. Initially, a high temperature allows the exploration of a broad solution spectrum, including those inferior to the current solution. With progressing iterations, the temperature is methodically reduced, making the algorithm increasingly selective and favoring the acceptance of superior solutions with greater probability. This strategic adjustment enhances the algorithm's efficiency in converging towards the optimal solution.

Restarts

Restarting in Simulated Annealing involves returning to a previously encountered superior solution (sbest) with its corresponding energy (ebest) and potentially resetting the annealing schedule. This strategy is employed when progress stalls or deteriorates from the optimal path. Restart criteria vary, including a fixed number of steps, a significant disparity between the current and best energy levels, or even randomly. This mechanism helps to overcome local minima and reorient the search towards the global optimum.

Pseudocode

The following pseudocode presents the simulated annealing heuristc as described above. The algorithm terminates when the temperature has cooled to a certain level T_{min} or when the energy of the current solution is lower than a fixed threshold E_{th}.

References