On the convergence of stationary distributions in simulated annealing algorithms
type: Item
instance of: scholarly article
title: On the convergence of stationary distributions in simulated annealing algorithms
zbMATH Open document ID: 0638.65054
DOI: 10.1016/0020-0190(88)90024-5
author: U. Faigle
author: Rainer Schrader
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
review text: Simulated annealing is an iterative probabilistic algorithm designed to find good solutions for discrete optimization problems. At each iterative step a deterioration of the objective function is accepted with a certain probability. This probability depends upon a parameter t called the temperature and approaches zero as t approaches zero. Thus optimal objective values are attained as the temperature is decreased to zero. Computational experiments have indicated that convergence to the optimum state need not occur if the temperature t is decreased too quickly. Research suggests that the most favourable procedure to use is to iterate at a fixed temperature for a sufficiently large number of iterations before lowering the parameter t to a new level. In this way relatively few different parameters are required to reach a solution. Intuitively this procedure suggests generating the equilibrium distribution for each temperature with the expectation that these distributions will converge to the optimum as t tends to zero. It is the purpose of this paper to lend theoretical support to this supposition. The results are obtained within the framework of Markov processes. By considering directly the limit of the stationary distributions, it has been possible for the authors to prove convergence to the optimum for a comprehensive class of simulated annealing algorithms based on connected undirected neighbourhood graphs. One consequence of the generality of the proof is the considerable flexibility it facilitates in the design of simulated annealing algorithms which can be exd its specific differences with the other approaches, mainly the K \& R standard. For higher sophisticated programming techniques can be consulted and other (already) classical texts, but this one is indispensable for the moment, let they be beginners or advanced programmers in C language.
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C15
Mathematics Subject Classification ID: 65C99
zbMATH DE Number: 4041184
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: Markov chain
zbMATH Keywords: equilibrium distribution
zbMATH Keywords: Simulated annealing
zbMATH Keywords: discrete optimization problems
zbMATH Keywords: convergence
zbMATH Keywords: Markov processes
zbMATH Keywords: stationary distributions
reviewed by: Neculai Curteanu
MaRDI profile type: Publication
full work available at URL: 0020-0190(88)90024-5
OpenAlex ID: W1998834658
cites work: Simulated annealing methods with general acceptance probabilities
cites work: A thermodynamically motivated simulation procedure for combinatorial optimization problems
cites work: Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
cites work: Q3798158
cites work: Q5538132
cites work: Q4184988
cites work: Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
cites work: Using simulated annealing to solve routing and location problems
cites work: Cooling Schedules for Optimal Annealing
cites work: Optimization by Simulated Annealing
cites work: Convergence of an annealing algorithm
cites work: Equation of State Calculations by Fast Computing Machines
cites work: Probabilistic exchange algorithms and Euclidean traveling salesman problems
cites work: Non-negative matrices and Markov chains. 2nd ed
description: scientific article; zbMATH DE number 4041184