Accession Number : ADA204553

Title :   Simulated Annealing with Noisy or Imprecise Energy Measurements.

Descriptive Note : Final rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS

Personal Author(s) : Gelfand, S. B. ; Mitter, S. K.

Report Date : JAN 1989

Pagination or Media Count : 19

Abstract : The annealing algorithm (Ref. 1) is modified to allow for noisy or imprecise measurements of the energy cost function. This is important when the energy cannot be measured exactly or when it is computationally expensive to do so. Under suitable conditions on the noise/imprecision, it is shown that the modified algorithm exhibits the same convergence in probability to the globally minimum energy states as the annealing algorithm (Ref. 2). Since the annealing algorithm will typically enter and exit the minimum energy states infinitely often with probability one, the minimum energy state visited by the annealing algorithm is usually tracked. The effect of using noisy or imprecise energy measurements on tracking the minimum energy state visited by the modified algorithms is examined. Keywords: Simulated annealing, Combinatorial optimization, Noisy measurements, Markov chains, computer simulation. (kt)

Descriptors :   *ANNEALING, *COMPUTERIZED SIMULATION, ALGORITHMS, COMBINATORIAL ANALYSIS, COSTS, ENERGY, FUNCTIONS, MARKOV PROCESSES, MEASUREMENT, NOISE, OPTIMIZATION, SIMULATION.

Subject Categories : Computer Programming and Software
      Ceramics, Refractories and Glass
      Metallurgy and Metallography

Distribution Statement : APPROVED FOR PUBLIC RELEASE