Introduction

SA algorithm is based on the analogy between the simulation of the annealing of solids and the problem of solving of large combinatorial optimization problems. In condensed matter physics, annealing denotes a physical process in which a solid in a heat bath is heated up by increasing the temperature of the bath to a maximum value at which all particles arrange themselves randomly in the liquid phase, followed by cooling through slowly lowering the temperature of the bath. In this way, all particles arrange themselves in the low energy ground state of a corresponding lattice, provided the maximum temperature is sufficiently high and the cooing is carried out sufficiently slowly.

To simulate the evolution to thermal equilibrium of a solid, Metropolis et al. proposed a Monte Carlo method, which generates sequences of states of the solid. A small randomly generted perturbation is applied to a randomly chosen particle. If the difference in energy Delta E between the current state and slightly perturbed one is negative, the process is continued with the new state. If Delta E = 0 the new state is accepted with a probability of acceptance based on Boltsmann's distribution. The Metropolis algorithm can also be used to generate sequences of configurations of a combinatorial optimization problem.