Copyright: © Pedro Mendes 1998, all rights reserved
Citation: © Pedro Mendes 1998, all rights reserved


Simulated annealing

This help file contains information about the Gepasi optimisation module Simulated annealing.

Be warned that simulated annealing can run for hours or even days! (no, Gepasi has not crashed!)

Introduction to simulated annealing

This implementation of SA

Bibliography

Simulated Annealing tunable parameters:

 Tolerance  - Convergence stopping criterium: the method stops when the change in the objective function has been smaller than this value in the last two temperature steps. (This is an absolute tolerance)

 T0 – Initial temperature of the system. The higher the temperature, the larger the probability that a global optimum is found. Note that the temperature should be very high in the beginning of the method (the system should be above the “melting” temperature). This value has the same units as the objective function, so what represents “high” is different from problem to problem.

 dT – Rate by which the temperature is reduced from one cycle to the next, given by the formula:    T(new) = T(old) * dT  . The simulated annealing algorithm works best if the temperature is reduced at a slow rate, so this value should be closer to 1. (but values closer to 1 will also cause the algorithm to run slower).

Simulated Annealing characteristics:

 global optimiser

 accepts bounds on the adjustable parameters

 enforces constraints on the variables

 stochastic optimisation

Simulated Annealing termination:

 Simulated annealing terminates at the end of a temperature cycle, if the objective function value changed by less than Tolerance in the last 2 temperature cycles.


Brief introduction

Simulated annealing is an optimization algorithm first proposed by Kirkpatrick et al. (1983) and was inspired by statistical mechanics and the way in which perfect crystals are formed. Perfect crystals are formed by first melting the substance of interest, and then cooling it very slowly. At large temperatures the particles vibrate with wide amplitude and this allows a search for global optima. As the temperature decreases so do the vibrations until the system settles to the global optimum (the perfect crystal).

The simulated annealing optimization algorithm uses a similar concept: the objective function is considered a measure of the energy of the system and this is maintained constant for a certain number of iterations (a temperature cycle). In each iteration, the parameters are changed to a nearby location in parameter space and the new objective function value calculated; if it decreased, then the new state is accepted, if it increased then the new state is accepted with a probability that follows a Boltzmann distribution (higher temperature means higher probability of accepting the new state). After a fixed number of iterations, the stopping criterion is checked; if it is not time to stop, then the system’s temperature is reduced and the algorithm continues.

Simulated annealing is a stochastic algorithm that is guaranteed to converge if ran for an infinite number of iterations. It is one of the most robust global optimization algorithms, although it is also one of the slowest. (Be warned that simulated annealing can run for hours or even days!).

Bibliography


Bibliography

 Kirkpatrick, S., Gelatt, J., C.D. & Vecchi, M. P. (1983) “Optimization by simulated annealing” Science 220, 671-680.

 Corana, A., Marchesi, M., Martini, C. & Ridella, S. (1987) “Minimizing multimodal functions of continuous variables with the "simulated annealing" algorithm” ACM Trans. Math. Softw. 13, 262-280.


This implementation of Simulated Annealing

This implementation of simulated annealing is based on the code of Corana et al. (1987). This implementation has tuned some of the parameters of the original implementation as follows:

 Each temperature cycle lasts for 50*p2  or 100*p iterations (whichever is smaller), with n being the number of optimization parameters.

 At each step, a new candidate solution is accepted if: a) it reduced the objective function value, or b) it increased the objective function value with a probability equal to [image] , where f is the increase in objective function value, and T  is the current temperature.

 The stopping criterion is applied to the last two temperature cycles (i.e. the change in objective function between this temperature and the previous must have been smaller than the Tolerance in the last two cycles).

Please consult the bibliography for further details on simulated annealing.