Theoretical and computational aspects of simulated annealing. (English) Zbl 0659.90062

CWI Tracts, 51. Amsterdam: Centrum voor Wiskunde en Informatica. viii, 168 p. Dfl. 25.30 (1988).
This tract is devoted to the simulated annealing algorithm for solving the combinatorial optimization problem: \(\min_{i\in {\mathcal R}}C(i)\), where \({\mathcal R}\) is at most countably infinite and C: \({\mathcal R}\to R\). The simulated annealing algorithm is characterized as a randomized version of an iterative improvement algorithm, producing a sequence of configurations (elements of \({\mathcal R})\) according to a Markovian transition law. Thus, from a configuration i, the algorithm moves to a new configuration j belonging to a neighbourhood \({\mathcal R}_ i\) of i with the probability: \(P_{ij}(c)=G_{ij}(c)A_{ij}(c)\), if \(j\neq i\), and \(P_{ij}(c)=1-\sum_{k\neq i}G_{ik}(c)A_{ik}(c)\), if \(j=i\), where \((G_{ij}(c))_ j\) is the uniform distribution on \({\mathcal R}_ i\), \[ A_{ij}(c)=\exp (-\frac{C(j)-C(i)}{c}),\quad if\quad C(j)>C(i),\quad and\quad A_{ij}(c)=1,\quad if\quad C(j)\leq C(i), \] and c is the control parameter. After some introductive discussions the following problems are studied: asymptotic behavior of the algorithm, finite-time behavior of simulated annealing, empirical analysis of simulated annealing, and the Bayesian approach to simulated annealing.
Reviewer: Anton Ştefănescu


90C27 Combinatorial optimization
65K05 Numerical mathematical programming methods
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming