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

### MSC:

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