Probability and Algorithms (1992) / Chapter Skim
Currently Skimming:
2 Simulated Annealing
2 Simulated Annealing
Pages 17-30
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 17... ...
for finding the global minimum of a cost function that may possess several local minima. It works by emulating the physical process whereby a solid is slowly cooled so that when eventually its structure is "frozen," it happens at a minimum energy configuration.
|
From page 18... ...
= 0. The rationale behind the SA algorithm is best understood by considering a homogeneous Markov chain ~T(t)
|
From page 19... ...
. The SA algorithm can also be viewed as a local search algorithm in which (unlike the usual deterministic local search algorithms)
|
From page 20... ...
glider a slowly varying cooling schedule T(t) remain pretty much unchanged if a related cooling schedule is used in which the temperature is held constant for fairly long time periods.
|
From page 21... ...
One can also pursue this approximation by piecewise constant schedules directly, without introducing eigenvalue estimates. The main idea is that, at low temperatures, the statistics of a homogeneous chain can be accurately bounded by viewing it as a singularly perturbed Markov chain and using rather crude large-deviation bounds (Tsitsiklis, 198S, 1989~.
|
From page 22... ...
time units is at most Be~~~/0, for suitable positive constants B and b. So, for very large times, the performance of a random walk would seem to be better than the performance guarantees of simulated annealing.
|
From page 23... ...
Proving rapid mixing for large SA Markov chains at small temperatures is a challenging task. One class of problems for which there is some hope of obtaining positive complexity results arises in the context of image processing.
|
From page 24... ...
The relaxation times of Markov random fields have been extensively studied (see, e.g., I,iggett, 1988) , but under rawer special assumptions on one Junctions Jij aria 9ij,ke- Thus, the available results are not yet applicable to the cost functions that arise in · e image processlug.
|
From page 25... ...
3. For the traveling salesman problem, SA consistently outperforms solutions found by repeated application of iterative improvement, based on 2-opt or 3-opt transitions, but it is a consistent loser when compared with the well-known algorithm of Lin and Kernighan (1973~.
|
From page 26... ...
In addition to the above mentioned developments in image processing, SA and various alternative versions based roughly on it have been used in statistical applications. Bohachevsky et al.
|
From page 27... ...
(1985b) , Nonstationary Markov chains and convergence of the annealing algorithm, J
|
From page 28... ...
, Probabilistic bounds and heuristic aigm rithms for coloring large random graphs, Technical Report 82-CSE-6, Department of Computer Science and Engineering, Southern Methodist University, Dallas, Tex. Kernighan, B., and S
|
From page 29... ...
(1988) , A survey of large time asymptotics of simulated annealing algorithms, in Stochastic Differential Systems, Stochastic Control Theory and Applications, W
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.