Simulated Annealing- Analogies to the Operations.

If simulated annealing is run for a sufficiently long time and with the appropriate cooling schedule, it is guaranteed to converge to the global minimum [Mitra et al, 1985; van Laarhoven and Aarts 1987].

This blog explains in intuitive terms why the above statement holds true is so. Two analogies are given to illustrate the operation of this algorithm. Which we have tried to explore in the course of this blog.

The First Analogy:

Simulated annealing is compared to the annealing process in metals in the first analogy, from which the algorithm gets its name. If a metal is stressed and has an imperfect crystal structure, heating it to a very high temperature and then cooling it slowly is one way to restore its atomic placement. The atoms have enough kinetic energy at high temperatures to break free from their current incorrect positions. As the material cools, the atoms begin to settle into their proper lattice positions.

When a material is cooled too quickly, the atoms do not have enough time to move to their proper lattice positions, and defects are frozen in the crystal structure. Similarly, there are many random permutations in the initial configuration of simulated annealing at high temperature. These allow cells in the wrong places to be dislodged from their original positions. As the temperature drops, the cells gradually become trapped in their ideal positions.

In the Second Analogy:

The action of simulated annealing is compared to a ball in a hilly terrain inside a box in the second analogy [Szu 1986]. The ball would roll downhill unaffected until it reached a pit, where it would rest indefinitely, even if the pit was high above the minimum valley. The box must be shaken vigorously enough for the ball to cross the highest peak in its path and enter the global minimum valley. Simultaneously, it must be shaken gently enough that the ball cannot escape the global minimum valley once it has entered it.

It must also be shaken for long enough to have a good chance of reaching the global minimum valley. These characteristics are reflected in the parameters of the algorithm. The probabilistic acceptance function and the initial temperature determine the strength or gentleness of the vibrations, while the cooling schedule and the inner loop criterion determine the duration of the vibrations.

This blog would be followed by blogs on Simulated Annealing — Timber Wolf Approach(Part-1 and Part-2) and Futuristic advancements in Simulated Annealing where more nuances about Simulated annealing would be explored.

This Blog has been published as a part of a blog series on the topic “VLSI Cell Placement Techniques” which is a Co-Curriculum activity in our college (Vishwakarma Institute Of Technology, Pune) which is aimed at giving the students a comprehensive understanding of the Industry Practices in the field of Digital Design. We hope this blog has been a informative read for you.