search eh.res by keyword

Douglas,

Thanks for the thoughtful reply. The 10 percent improvement is, as you say,
non-trivial.

As you guessed, simulated annealing is an algorithm for finding a
reasonably good solution to intractable problems. It is a member of the
class of stochastic approximation algorithms. (This isn't meant to clarify
but to help you find this stuff if you want to read about it.) There are
two components of the algorithm.

There is a "shaking up" part that is "random" and is applied periodically.
The shakes become smaller over time (else the algorithm never would converge.)

The other part is a "standard" look for nearby improvements.

So the idea is

guess a place to start
look for local improvements

shake things up
look for local improvements

shake things up but not as much as before
look for local improvements

etc. to convergence.

This works reasonably well in practice for hard problems where just looking
for local improvements can lead one seriously astray.

Jerry Dwyer

Send comments and questions to admin@eh.net