Simulated annealing

Three IBM researchers showed that a hard optimisation problem can be solved by sometimes accepting a worse step and gradually lowering the chance of doing so.

The analogy is direct: slow cooling gives a metallurgist a crystal of lower energy than rapid quenching does. Temperature here is the parameter governing willingness to accept a worsening. The method was applied to circuit placement and to the travelling salesman problem. The same stochastic acceptance underlies the Boltzmann machine two years later.