The Annealing Algorithm

1. Front Matter

   Pages i-xi

   PDF

2. The Annealing Algorithm: A Preview

   • R. H. J. M. Otten, L. P. P. P. van Ginneken

   Pages 1-20

3. Preliminaries from Matrix Theory

   • R. H. J. M. Otten, L. P. P. P. van Ginneken

   Pages 21-46

4. Chains

   • R. H. J. M. Otten, L. P. P. P. van Ginneken

   Pages 47-64

5. Chain Statistics

   • R. H. J. M. Otten, L. P. P. P. van Ginneken

   Pages 65-78

6. Annealing Chains

   • R. H. J. M. Otten, L. P. P. P. van Ginneken

   Pages 79-93

7. Samples from Normal Distributions

   • R. H. J. M. Otten, L. P. P. P. van Ginneken

   Pages 95-113

8. Score Densities

   • R. H. J. M. Otten, L. P. P. P. van Ginneken

   Pages 115-126

9. The Control Parameter

   • R. H. J. M. Otten, L. P. P. P. van Ginneken

   Pages 127-139

10. Finite-Time Behavior of the Annealing Algorithm

    • R. H. J. M. Otten, L. P. P. P. van Ginneken

    Pages 141-151

11. The Structure of the State Space

    • R. H. J. M. Otten, L. P. P. P. van Ginneken

    Pages 153-165

12. Implementation Aspects

    • R. H. J. M. Otten, L. P. P. P. van Ginneken

    Pages 167-177

13. Back Matter

    Pages 179-201

    PDF

The goal of the research out of which this monograph grew, was to make annealing as much as possible a general purpose optimization routine. At first glance this may seem a straight-forward task, for the formulation of its concept suggests applicability to any combinatorial optimization problem. All that is needed to run annealing on such a problem is a unique representation for each configuration, a procedure for measuring its quality, and a neighbor relation. Much more is needed however for obtaining acceptable results consistently in a reasonably short time. It is even doubtful whether the problem can be formulated such that annealing becomes an adequate approach for all instances of an optimization problem. Questions such as what is the best formulation for a given instance, and how should the process be controlled, have to be answered. Although much progress has been made in the years after the introduction of the concept into the field of combinatorial optimization in 1981, some important questions still do not have a definitive answer. In this book the reader will find the foundations of annealing in a self-contained and consistent presentation. Although the physical analogue from which the con­ cept emanated is mentioned in the first chapter, all theory is developed within the framework of markov chains. To achieve a high degree of instance independence adaptive strategies are introduced.

• Mathematica
• algorithms
• analog
• combinatorial optimization
• model
• optimization
• quality
• statistics
• combinatorics

`I highly recommend this book for colleagues versed in simulated annealing, particularly those who lean toward theory.'
D. Greening, Computer Reviews, June 1990

• Delft University of Technology, The Netherlands

  R. H. J. M. Otten

• Eindhoven University of Technology, The Netherlands

  L. P. P. P. Ginneken

Policies and ethics