Simulated Annealing

The original ideas of the simulated annealing (SA) methods dates back to 50s of the last century. Exactly, in 1953, Metropolis et al. introduced an efficient algorithm to simulated the equilibrium of a collection of atoms at a given temperature. This pioneering technique had inspired Kirkpatrick, Gelatt and Vecchi to simulate it in optimization and call it Simulated Annealing (SA). Since the presentation of Kirkpatrick, Gelatt and Vecchi, a lot of studies that invoke SA have emerged in the area of optimization. Actually, the theoretical aspects as well as the applications of SA have been extensively studied.

The SA algorithm successively generates a trial point in a neighborhood of the current solution and determines whether or not the current solution is replaced by the trial point based on a probability depending on the difference between their function values. Convergence to an optimal solution can theoretically be guaranteed only after an infinite number of iterations controlled by the procedure so-called cooling schedule. The main control parameter in the cooling schedule is the temperature parameter T. The main role of T is to let the probability of accepting a new move be close to 1 in the earlier stage of the search and to let it be almost zero in the final stage of the search. A proper cooling schedule is needed in the finite-time implementation of SA to simulate the asymptotic convergence behavior of the SA. The following algorithm states the steps of the standard SA method.

Standard Simulated Annealing Algorithm.

1. Initialization. Choose an initial solution x₀, and fix the cooling schedule parameters; initial temperature T_max, epoch length M, cooling reduction ratio λ ∈ (0, 1), and minimum temperature T_min. Set the temperature T := T_max and k := 0.

2. Epoch Loop. Repeat the following steps (2.1–2.3) M times.    

2.1. Generate a trial point y_k in the neighborhood of the current solution x_k.

2.2. Evaluate f on the trial point y_k, and compute p := 1, if f(y_k ) < f(x_k ); or  p := exp(−Df /T), otherwise, where Df := f(y_k ) − f(x_k ).

2.3. Choose a random number u from (0, 1) . If p ≥ u, set x_k+1 := y_k. Otherwise, set x_k+1 := x_k. Set k := k + 1.

3. Termination Condition. If the cooling schedule is completed (T ≤ T_min), terminate. Otherwise, decrease the temperature by setting T := λT, and go to Step 2.

One of the most powerful features of SA is its ability of easily escaping from being trapped in local minima by accepting up-hill moves through a probabilistic procedure especially in the earlier stages of the search. On the other hand, the main drawbacks that have been noticed on SA are its suffering from slow convergence and its wandering around the optimal solution if high accuracy is needed.