Simulated Annealing: Theory and ApplicationsIt 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. |
Contents
Introduction | 1 |
Simulated annealing | 7 |
22 Mathematical model of the algorithm | 12 |
Asymptotic convergence results | 17 |
312 Existence of the stationary distribution | 18 |
313 Convergence of the stationary distribution | 20 |
32 The inhomogeneous algorithm | 27 |
322 Sufficient conditions for convergence | 28 |
63 Probabilistic value analysis | 82 |
64 Performance on combinatorial optimization problems | 88 |
Chapter 7 Applications | 99 |
72 Applications in computeraided circuit design | 100 |
722 Placement | 101 |
723 Routing | 110 |
724 Other applications in computeraided circuit design | 118 |
73 Applications in other areas | 128 |
323 Necessary and sufficient conditions for convergence | 35 |
The relation with statistical physics | 39 |
42 Equilibrium dynamics | 40 |
43 Typical behaviour of the simulated annealing algorithm | 44 |
44 Phase transitions | 48 |
45 Relation with spin glasses | 50 |
Towards implementing the algorithm | 55 |
52 Conceptually simple cooling schedules | 59 |
53 More elaborate cooling schedules | 62 |
54 Improvements of the generation mechanism for transitions | 71 |
Performance of the simulated annealing algorithm | 77 |
62 Worstcase performance results | 79 |
732 Boltzmann machines | 131 |
733 Miscellaneous applications | 135 |
Some miscellaneous topics | 139 |
811 General algorithms | 140 |
812 Tailored algorithms | 143 |
813 Special parallel implementations | 147 |
82 Continuous optimization | 148 |
822 Applications of simulated annealing to continuous problems | 151 |
Summary and conclusions | 153 |
Bibliography | 157 |
| 177 | |
Other editions - View all
Common terms and phrases
Aarts accepted transitions analysis applications of simulated approach approximation algorithm average Boltzmann machine bound Černy chapter circuit Ck+1 combinatorial optimization problems computation Computer-Aided Design constant control parameter cooling schedule Copt corresponding cost function cost value decrement rule defined denotes discussed entropy equilibrium ergodicity figure final solution Gidas Ginneken given by eq global minimum graph graph partitioning Hajek heuristic homogeneous Markov chain IEEE Int implementation inhomogeneous algorithm iterative improvement Kirkpatrick Laarhoven AAR85a Lundy and Mees Markov chain length Mees LUN86 Mézard modules NLAP NP-complete number of transitions obtained Otten parallel partition permutation placement problem Port Chester probabilistic problem instance Proc processors quality of solution quasi-equilibrium random randomly rithm Ropt satisfied Sechen section 5.2 sequence set of configurations simulated annealing algorithm solved spin glass stationary distribution statistical mechanics subsets Timber Wolf tion tour length travelling salesman problem
Popular passages
Page iv - SERIES EDITOR'S PREFACE Approach your problems from the right end and begin with the answers. Then one day, perhaps you will find the final question. The Hermit Clad in Crane Feathers