Simulated annealing

Simulated annealing ( simulated annealing ) is a heuristic optimization method. The method is used for finding an approximate solution of optimization problems that preclude their high complexity, the complete testing every possibility and simple mathematical method. This method is used for example in the floorplanning during a chip design.

The basic idea is the simulation of a cooling process, such as during annealing in materials science. After heating a metal, the slow cooling ensures that the atoms have enough time to organize themselves and to form stable crystals. This is achieved close to the optimum one low-energy state.

Transferred to the optimization process, the temperature corresponding to a probability that may be an intermediate result of optimization also deteriorate. The Metropolis algorithm is the basis of simulated annealing. Unlike a local search algorithm, the process can leave a local optimum again and find a better one.

Motivation

The algorithm of simulated annealing can be easily motivated on the basis of physical considerations. Wanted is an energetically most favorable state of a system, which can be described using the Boltzmann statistics. According to the Boltzmann statistics, the probability to encounter a microstate with energy given by the probability distribution

The Boltzmann constant and temperature. The energy of the lowest energy state is, so you can set up the following equation:

Since the lowest energy state, applies. Since and thus holds that the absolute amount of the exponent is larger for decreasing temperatures. Taking account of the negative sign of the exponent is therefore less likely to lower temperatures to find an excited energy state. You thus lowers the temperature of the system slowly, so the lowest energy state is encountered with increasing probability.

Algorithm

Problem

Given the range of values ​​, a fitness function, an ambient term and a termination criterion.

Wanted is an approximate solution of the global minimum of about.

Initialization

Choose a starting solution. Choose a monotonically to zero temperature falling sequence and a sequence that specifies how many steps a temperature is maintained. Start times and.

Local change

Falls: Choose a neighbor from the environment, otherwise set and, looking back a neighbor.

Selection

• Applicable laws and, if necessary, set
• Applies only translate with probability.

Demolition or further

If not replaced by, sit and start again with a local change.

Otherwise, if the termination condition so that the approximate solution is also not satisfied and found to begin in the next time cycle again with a local change and set.

Notes

The probability that a poorer is accepted, is greater because of less deterioration and, as a monotonically decreasing sequence is the beginning of the process is also likely.

As a neighbor should be chosen depends on the present problem. In computer science, often the value range and is regarded as a bit vector. A neighbor of, for example, by flipping ( inverting ) are selected one or more bits (see Wegener 2005).

There are various termination conditions conceivable. For example, only a maximum number of iterations are allowed, a sufficient fitness defined set a lower limit for cooling, or a number of time points is defined over which no longer changed.

Graphical clarification

The problem of simulated annealing can be illustrated graphically.

Suppose you are looking for in a two-dimensional landscape of the (global) lowest point. The landscape itself consists of many different deep dents. The simple search strategy ( seeking the next lowest point ) corresponds to the behavior of a ball, which is exposed in this landscape. It rolls to the next local minimum and remains there. In the simulated annealing of the ball is always dealt a shock which becomes more " cooling " weaker. This is ideally strong enough to remove the bullet from a shallow dip ( local minimum ), but not enough to escape from the global minimum.