Record Details

Some results characterizing the finite time behaviour of the simulated annealing algorithm

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Some results characterizing the finite time behaviour of the simulated annealing algorithm
 
Creator DESAI, MP
 
Subject markov-chains
cooling schedules
convergence
simulated annealing algorithm
finite time behaviour
minimum cost state
probabilistic search technique
 
Description The Simulated Annealing algorithm is a probabilistic search technique for finding the minimum cost state in a set Omega. The algorithm has been successfully used to obtain near-optimal solutions for problems for which no other effective algorithms exist. For example, problems in integrated circuit layout and in finite impulse response (FIR) filter design have been solved using annealing. In most applications, Omega is finite set, and the annealing algorithm may be modelled as a time-inhomogeneous Markov chain on Omega with transition probabilities that are powers of a time varying parameter epsilon. It has been shown by several researchers that if epsilon is driven to 0 sufficiently slowly, then the algorithm will eventually find a minimum cost state in Omega with probability 1. In this paper, we will focus on the finite-time behaviour of the annealing algorithm. In particular, we will summarize some results relating the number of steps taken by the algorithm to the quality of the solutions obtained. These results provide qualitative as well as quantitative information about the status of the annealing algorithm after a finite number of steps. This will be illustrated using some examples.
 
Publisher INDIAN ACADEMY SCIENCES
 
Date 2011-08-02T07:33:55Z
2011-12-26T12:53:46Z
2011-12-27T05:40:46Z
2011-08-02T07:33:55Z
2011-12-26T12:53:46Z
2011-12-27T05:40:46Z
1999
 
Type Article
 
Identifier SADHANA-ACADEMY PROCEEDINGS IN ENGINEERING SCIENCES, 24(), 317-337
0256-2499
http://dx.doi.org/10.1007/BF02823146
http://dspace.library.iitb.ac.in/xmlui/handle/10054/8711
http://hdl.handle.net/10054/8711
 
Language en