Accession Number:

ADA170174

Title:

Analysis of Simulated Annealing for Optimization.

Descriptive Note:

Technical rept.,

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS

Personal Author(s):

Report Date:

1985-09-01

Pagination or Media Count:

34.0

Abstract:

Simulated annealing is a popular Monte Carlo algorithm for combinatorial optimization. The annealing algorithm simulates a nonstationary finite state Markov chain whose state space is the domain of the cost function to be minimized. We analyze this chain focusing on those issues most important for optimization. In all of our results we consider an arbitrary partition optimization important special cases are when I is the set of minimum cost states or a set of all states with sufficiently small cost. We give a lower bound on the probability that the chain visits I at some time. This bound may be useful even when-the algorithm does not converge. We give conditions under which the chain converges to I in probability and obtain an estimate of the rate of convergence as well. We also give conditions under which the chain visits I infinitely often visits I almost always, or does not converge to I with probability 1. Author

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE