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 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.

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