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

### What people are saying - Write a review

We haven't found any reviews in the usual places.

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

### Common terms and phrases

Aarts accepted transitions analysis applications of simulated approach approximation algorithm average Boltzmann machine chapter circuit combinatorial optimization problems computation Computer-Aided Design constant control parameter cooling schedule Copt corresponding cost function cost value decrement rule defined discussed entropy equilibrium ergodicity figure final solution floorplan Geman and Geman Gidas Ginneken given by eq global minimum graph partitioning Hajek heuristic homogeneous Markov chain IEEE Int implementation inhomogeneous algorithm Kirkpatrick Laarhoven AAR85a length of Markov Lundy and Mees Markov chain length Mees LUN86 Mezard modules nets NLAP NP-complete number of transitions obtained Otten parallel permutation placement problem Port Chester prob probabilistic probability distribution problem instance Proc processors proposed quality of solution quasi-equilibrium random randomly rithm satisfied Sechen sequence set of configurations simulated annealing algorithm Skiscim solved spin glass stationary distribution statistical mechanics subsets theorem Timber Wolf tion tour length travelling salesman problem variables X(fc

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