Simulated annealing

Simulated annealing is a powerful technique for coming up with approximate solutions to hard combinatorial optimization problems.

Several Tcl'ers have expressed interest in writing something about the topic, and this page is here in hopes of prompting more interest.

One application of simulated annealing is Solving cryptograms. The code on that page has a fairly generic implementation of the basics that could be lifted out and applied elsewhere. In fact it was lifted out of another application that did screen layouts of Message Sequence Charts, and had the screen layout problem replaced with the codebreaking problem.

Other applications are placement-and-route of transistors on a chip, chips on a pcb, logical cells in an FPGA, all kinds of scheduling problems, ...

Vince my opinion and experience of these sorts of things is that the actual algorithm used (simulated annealing or tabu search or hill-climbing or ....) is less important than the representation of the problem which is used (which defines the fitness landscape over which the search operates).

NEM: An interesting variant on simulated annealing is the fascinating CopyCat framework developed by Hofstadter/Mitchell, which has a concept of temperature which is more dynamic: the degree of randomness in the process can also rise due to feedback pressures, rather than monotonically reducing in line with a fixed schedule. [L1 ]

lm For the record, simulated annealing is also used in crystallography for the refinement of a model structure (protein, organic compound, nucleic acid, ...) against experimental data taking chemical constraints (bond length, angles, ...) into account. The refinement is done using a temperature bath, the temperature is here to be seen as an energy tank. The refinement could be done at a given temperature, or slow cooled with time. Simulated annealing is the method of choice since end of 80's for macromolecular refinement.