Simulated annealing : an introduction

Simulated annealing is a general approach for approximately solving large combinatorial optimization problems. The algorithm is based on an intriguing combination of ideas from at first sight completely unrelated fields of science, viz. combinatorial optimization and statistical physics. On the one hand the algorithm can be viewed as an analogue of an algorithm used in statistical physics for computer simulation of the annealing of a solid to its minimum-energy state, on the other hand it can be considered as a generalization of the well-known iterative improvement approach to combinatorial optimization problems. In this introductory paper we give a mathematical description of the simulated annealing algorithm and discuss its behaviour from both a theoretical and a practical point of view. The latter is illustrated by applying the algorithm to the travelling salesman problem. This paper was written to familiarize the readers of Statistica Neerlandica with simulated annealing. It is a summary of papers written earlier by the authors and does not contain any new material