
Accession Number : ADA189382
Title : Analysis of Simulated Annealing Type Algorithms.
Descriptive Note : Doctoral thesis,
Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS
Personal Author(s) : Gelfand, Saul B ; Mitter, Sanjoy K
PDF Url : ADA189382
Report Date : May 1987
Pagination or Media Count : 107
Abstract : THE ANNEALING ALGORITHM IS A POPULAR MonteCarlo 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.
Descriptors : *ANNEALING, *COMBINATORIAL ANALYSIS, *OPTIMIZATION, *MONTE CARLO METHOD, ALGORITHMS, SIMULATION, APPROXIMATION(MATHEMATICS), ERROR CORRECTION CODES, MATHEMATICAL ANALYSIS, COMPUTER AIDED DESIGN, COST ANALYSIS, GRAPHS, POLYNOMIALS
Subject Categories : Statistics and Probability
Distribution Statement : APPROVED FOR PUBLIC RELEASE