Since the generation of an optimal placement and routing is probably
NP-complete, any polynomial-time optimizations must be iterative in
nature. One of the most popular iterative optimization methods is
simulated annealing
[25][20][8][1][12][9][2][22][17].
This method is borrowed from materials science, where it is well known
that to produce a solid in a low energy state (such as a perfect
crystal), you first heat the system to a high temperature, and then
slowly cool it. At any given temperature, the probability that a
change in the structure with energy change will occur is
, where
is Boltzmann's constant
and
is the temperature of the system in degrees Kelvin. When the
temperature is high, the system can change radically and many changes
that do not lower the energy level are allowed. As the temperature
decreases, fewer and fewer ``bad'' changes are permitted, until
finally a fairly optimal state is achieved.
In the computational equivalent of this method, an initial system is
chosen and then iteratively optimized. During each pass, one of a
number of optimizations is chosen and applied to the current system.
A cost function is used to indicate the desirability of a given
system, and the change in cost () from the current system to
the new system is computed. The new system is accepted with
probability:
where is the ``temperature'' of the system.
is
gradually decreased according to an ``annealing schedule'' as more
optimizations are applied, thus causing the system to gradually accept
fewer and fewer ``bad'' changes.