Analysis of Simulated Annealing Type Algorithms.

Abstract

THE ANNEALING ALGORITHM IS A POPULAR Monte-Carlo algorithm for combinatorial optimization. The annealing algorithm consists of simulating a nonstationary finite state Markov chain whose state space is the domain of the cost function, called energy, to be minimized. The degree of randomization in the annealing algorithm is controlled by a parameter, called temperature, which is slowly decreased to zero. The convergence in probability and the rate of convergence of the annealing chain for the special case of an energy function with two local minima is analyzed. The sample path properties of annealing chains (with arbitrary energy functions) are examined. A modification of the annealing algorithm which makes noisy measurements of the energy function is given. The annealing algorithm is extended for optimization on general spaces.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1987
Accession Number
ADA189382

Entities

People

  • Sanjoy K. Mitter
  • Saul B. Gelfand

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computer Science
  • Differential Equations
  • Electrical Engineering
  • Engineering
  • Equations
  • Gaussian Noise
  • Heuristic Methods
  • Image Processing
  • Markov Chains
  • Markov Processes
  • Partial Differential Equations
  • Probability
  • Random Variables
  • Statistical Mechanics
  • Stochastic Processes
  • Weak Convergence

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Materials Science and Engineering.

Technology Areas

  • Space