Simulated Annealing

Kirkpatrick had introduced the concept of simulated annealing or SA to the field of combinatorial optimization. SA procedure was analogous to the mode of the physical annealing described by Metroplis, here particles of solid arrange themselves into thermal equilibrium at a described temperature. Simulated annealing incorporates "hill-climbing" moves in order to ignore local optimal solution. SA method starts along with an arbitrary state Ω as the estimate of the optimal solution. A new state x′ is randomly chosen, if x ∈ Ω is the estimated optimal solution in k^th iteration. If f (x) define the objective function value and

 f( x′) ≤ f ( x) such as f ( x′) is better than f (x) for the case of  minimization, the algorithm admits move from x to x′ and x′ becomes the new estimated optimal solution. x′ will be accepted even while it is a worse state, if  f ( x′) ≥ f ( x) there is a chance. It is done because of the possibility that there may be a better solution hidden behind x′. More specially, a uniform random number R_a ~ R_a[0,1] is generated; if R_a < exp ¦- (t(x') - t(x))/T_k¦ the worse solution x′ is accepted, here T_k is the temperature at k^th iteration. Or else, x stays the estimate of the optimal solution. The cooling schedule plays a major role in guiding the solutions towards the optima. Other cooling schedule that can be utilized is as specified by,

                                            T_k  =C/ln (1 + k ).......................Eqn4

Annealing schedule asymptotically approaches to the global minimum like k → ∞. In practice, above cooling schedule needs too much computational time. Consequently, several other non-optimal schedules such work well in practice are generally used, as like:

                                                   T ← αT..........................Eqn5

Here α is called the cooling coefficient along with 0.8 ≤ α ≤ 1.0.

Mostly, simulated annealing or SA is a random search method and this is related to physical annealing of solids. A solid is heated to crystallization temperature and after that freeze this slowly to accomplish consistent hardness through the solid. Optimum solution of the large size grouping optimization problem or difficulty is being got by simulating the annealing of a solid.