Simulated annealing algorithm

The goal is to obtain optimal or nearly optimal solutions for a given problem. Thus first of all we need to define a finite set V of vertices, which correspond to the solutions of the problem, and a non-negative real function, called penalty,

pen : V → R,
for which we would like to find a vertex v ε V such that the value pen(v) is minimal or nearly minimal, so that such optimal v will serve as a solution. This abstract statement sounds simple but in applications the vertices may represent complex configurations or situations.

Some pairs of the vertices are connected by directed edges, so that together, the vertices and the edges, they form a directed graf G := (V E), where E is the set of all edges. Edges are just one-way roads which allow us to travel directly from one vertex to another. An edge leading from vertex v to vertex w is also called (in simulated annealing) a move from v to w. Simulated annealing is applied only to connected graphs, meaning that one can reach any vertex from any other via a finite sequence of consecutive edges (moves).

It is up to the designer of the algorithm to define the graph G = (V E) and the penalty function pen : V → R. One may do it well or one may do it poorly. It's an art. The same goes for the selection of other elements of the algorithm.

In addition, we consider also a real parameter T ≥ 0, called temperature, or rather a decreasing sequence of temperatures T(0) ≥ T(1) ≥ ... ≥ 0, which approach (or even attains) the limit value 0.

The algorithm, i.e. the search for the optimal vertex, works as follows: we start a travel over graph G at a high initial temperature T(0) and in an initial vertex v(0). Let's assume that we are already in vertex v(n) at temperature T(n). Now algorithm selects randomly a candidate for a move from vertex v(n). Let v(n+1) be the destination of the candidate move. If the penalty has decreased, pen(v(n+1)) then v(n+1) is accepted. If not then it is accepted with the probability prob(n) which approaches zero together with the temperature. If the candidate is rejected then another candidate v(n+1) is selected, and the same acceptance procedure applies to it; and so on, until a candidate is accepted.

Remark 1 In addition to simulated annealing algorithm there are also other optimizing algorithms which serve similar purpose. One of them is the so-called genetic algorithm, which is like simulated annealing but richer: besides moves it has also procreation, where one gets a new vertex out of a pair of two previous ones. This provides more possibilities (while it is harder now to provide a scientific foundation as solid as in the case of simulated annealing).

Remark 2 The algorithm may look just for one solution. Then after finding it, it may stop. Or it may look for many solutions. Then after finding a consecutive solution it restarts itself.