Skip to main content
Top

1987 | Book

Simulated Annealing: Theory and Applications

Authors: Peter J. M. van Laarhoven, Emile H. L. Aarts

Publisher: Springer Netherlands

Book Series : Mathematics and Its Applications

insite
SEARCH

About this book

It isn't that they can't see the solution. It is Approach your problems from the right end and begin with the answers. Then one day, that they can't see the problem. perhaps you will find the final question. O. K. Chesterton. The Scandal of Father 'The Hermit Clad in Crane Feathers' in R. Brown 'The point of a Pin'. van Oulik's The Chinese Maze Murders. Growing specialization and diversification have brought a host of monographs and textbooks or increasingly specialized topics. However, the "tree" of knowledg~ of mathematics and related fields does not grow only by putting forth new branches. It also ·happens, quite often in fact, that branches which were thought to be completely disparate are suddenly seen to be related. Further, the ~d and level of sophistication of mathematics applied in various sciences has changed drastically in recent years: measure theory is used (non-trivially) in regional and theoretical economics; algebraic geometry interacts with physics; the Minkowsky lemma, coding theory and the structure of water meet one another in packing and covering theory; quantum fields, crystal defects and mathematical programming profit from homotopy theory; Lie algebras are relevant to filtering; and prediction and electrical engineering can use Stein spaces. And in addition to this there are such new emerging subdisciplines as "experimental mathematics", "CFD", "completely integrable systems", "chaos, synergetics and large-scale order", which are almost impossible to fit into the existing classification schemes. They draw upon widely different sections of mathematics.

Table of Contents

Frontmatter
Chapter 1. Introduction
Abstract
During the past decades, the role of optimization has steadily increased in such diverse areas as, for example, electrical engineering, operations research, computer science and communication. Linear and non-linear optimization [WAG75], the search for an optimum of a function of continuous variables, has seen major breakthroughs in the fifties and sixties (the best known example being the simplex algorithm to solve linear programming problems, introduced by Dantzig in 1947 [DAN63]). Major results in combinatorial optimization [PAP82], the search for optima of functions of discrete variables, were obtained predominantly in the seventies. For example, for the Travelling Salesman Problem (TSP) [LAW85], probably the best known problem in combinatorial optimization, both approximation and optimization algorithms of high quality became available in the seventies ([LIN73] and [GRÖ77], respectively) and nowadays, TSPs of up to 318 cities are solved to optimality in reasonable computation times (less than 10 minutes CPU time on an IBM 370/168-computer) [CRO80].
Peter J. M. van Laarhoven, Emile H. L. Aarts
Chapter 2. Simulated annealing
Abstract
In its original form [KIR82], [ČER85] the simulated annealing algorithm is based on the analogy between the simulation of the annealing pf solids and the problem of solving large combinatorial optimization problems. For this reason the algorithm became known as “simulated annealing”. In condensed matter physics, annealing denotes a physical process in which a solid in a heat bath is heated up by increasing the temperature of the heat bath to a maximum value at which all particles of the solid randomly arrange themselves in the liquid phase, followed by cooling through slowly lowering the temperature of the heat bath. In this way, all particles arrange themselves in the low energy ground state of a corresponding lattice, provided the maximum temperature is sufficiently high and the cooling is carried out sufficiently slowly. Starting off at the maximum value of the temperature, the cooling phase of the annealing process can be described as follows.
Peter J. M. van Laarhoven, Emile H. L. Aarts
Chapter 3. Asymptotic convergence results
Abstract
Essential to the convergence proof for the homogeneous algorithm is the fact that, under certain conditions, the stationary distribution of a homogeneous Markov chain exists. The stationary distribution is defined as the vector q whose i-th component is given by [FELL50]
$${q_i} = \mathop {\lim }\limits_{k \to \infty } \Pr \{ X(k) = i|X(0) = j\} ,$$
(3.1)
for an arbitrary j.
Peter J. M. van Laarhoven, Emile H. L. Aarts
Chapter 4. The relation with statistical physics
Abstract
As pointed out in the introduction (chapter 1) there exists a clear analogy between the annealing of solids and the problem of solving large combinatorial optimization problems. The physical annealing process can be successfully modelled by using computer simulation methods from condensed matter physics [BAR76], [WOOD68]. These methods in turn are based on the theory of statistical mechanics which can be viewed as the central discipline of condensed matter physics [BIN78], [TOD83]. Starting off with the first paper on simulated annealing by Kirkpatrick et al. [KIR82], a number of authors elaborate on the relation between combinatorial optimization and statistical mechanics, either because of a phenomenological interest in the analogy (Bernasconi [BER87], Bonomi and Lutton [BON84], Kirkpatrick et al. [KIR82], [KIR83], [KIR85] and Mézard and Parisi [MÉZ85], [MÉZ86]) or because of a possible framework to model the convergence and the corresponding control of the simulated annealing algorithm (Aarts and Van Laarhoven [AAR85a], [AAR88a], Grest et al. [GRES86], Kirkpatrick et al. [KIR82], [KIR83], Otten and Van Ginneken [OTT84], Randelman and Grest [RAN86] and White [WHI84]). In this chapter a number of quantities are discussed that are defined in the theory of statistical mechanics for the description of a physical many-particle system at equilibrium and it will be elucidated how these quantities are related to the problem of solving large combinatorial optimization problems.
Peter J. M. van Laarhoven, Emile H. L. Aarts
Chapter 5. Towards implementing the algorithm
Abstract
As is shown in chapter 3, the simulated annealing algorithm in its original formulation converges with probability 1 to a globally minimal configuration in either one of the following two cases:
1.
for each value of the control parameter, c k , an infinite number of transitions is generated and limk→∞ c k (the homogeneous algorithm);
 
2.
for each value ck one transition is generated and ck goes to zero not faster than O ([log k]−1) (the inhomogeneous algorithm).
 
Peter J. M. van Laarhoven, Emile H. L. Aarts
Chapter 6. Performance of the simulated annealing algorithm
Abstract
The performance analysis of an approximation algorithm concentrates on the following two quantities:
  • the quality of the final solution obtained by the algorithm, i.e. the difference in cost value between the final solution and a globally minimal configuration;
  • the running time required by the algorithm.
Peter J. M. van Laarhoven, Emile H. L. Aarts
Chapter 7. Applications
Abstract
Ever since its introduction in 1982, simulated annealing has been applied to many combinatorial optimization problems in such diverse areas as computer-aided design of integrated circuits, image processing,code design, neural network theory, etc. In many of these areas, previous algorithms, if existing at all, performed quite poorly and the territory was ripe for an easy-to-implement approach with a modicum of sophistication [JOHN87].
Peter J. M. van Laarhoven, Emile H. L. Aarts
Chapter 8. Some miscellaneous topics
Abstract
In this chapter, parallel implementations of the simulated annealing algorithm on multi-processor architectures (section 8.1) are described as well as an extension of the algorithm to problems with continuous variables (section 8.2).
Peter J. M. van Laarhoven, Emile H. L. Aarts
Chapter 9. Summary and conclusions
Abstract
In this monograph we have presented a review of the theory and applications of simulated annealing. The simulated annealing algorithm is formulated using the theory of Markov chains and the convergence of the algorithm is analysed within this scope.
Peter J. M. van Laarhoven, Emile H. L. Aarts
Backmatter
Metadata
Title
Simulated Annealing: Theory and Applications
Authors
Peter J. M. van Laarhoven
Emile H. L. Aarts
Copyright Year
1987
Publisher
Springer Netherlands
Electronic ISBN
978-94-015-7744-1
Print ISBN
978-90-481-8438-5
DOI
https://doi.org/10.1007/978-94-015-7744-1