The Annealing Algorithm

1 The Annealing Algorithm: A Preview. - 1. 1 Combinatorial optimization. - 1. 2 Moves and local minima. - 1. 3 Hill climbing. - 1. 4 Simulated annealing. - 1. 5 Applications. - 1. 6 Mathematical model. - 1. 7 Discussion. - 2 Preliminaries from Matrix Theory. - 2. 1 Matrices. Notation and basic properties. - 2. 2 Pseudo-diagonal normal forms. - 2. 3 Norms and limits of matrices. - 2. 4 Quadratic forms. - 2. 5 Discussion. - 3 Chains. - 3. 1 Terminology. - 3. 2 Linear arrangement an example. - 3. 3 The chain limit theorem. - 3. 4 Reversible chains. - 3. 5 Discussion. - 4 Chain Statistics. - 4. 1 Density Functions. - 4. 2 Expected values. - 4. 3 Sampling. - 4. 4 Maximum likelyhood densities. - 4. 5 Aggregate functions. - 4. 6 Discussion. - 5 Annealing Chains. - 5. 1 Towards low scores. - 5. 2 Maximal accessibility. - 5. 3 The acceptance function. - 5. 4 Properties of annealing chains. - 5. 5 Discussion. - 6 Samples from Normal Distributions. - 6. 1 Characteristic functions. - 6. 2 Quadratic forms and characteristic functions. - 6. 3 Sampling distributions. - 6. 4 Asymptotic properties of sampling distributions. - 6. 5 Discussion. - 7 Score Densities. - 7. 1 The density of states. - 7. 2 Weak control. - 7. 3 Strong control. - 7. 4 Three parameter aggregates. - 7. 5 Discussion. - 8 The Control Parameter. - 8. 1 Initialization. - 8. 2 Decrements in the control parameter. - 8. 3 A stop criterion. - 8. 4 Proper convergence. - 8. 5 Discussion. - 9 Finite-Time Behavior of the Annealing Algorithm. - 9. 1 Rate of convergence of chains. - 9. 2 Minimum number of iterations. - 9. 3 Finite-time optimal schedules. - 9. 4 Discussion. - 10 The Structure of the State Space. - 10. 1 Chain convergence. - 10. 2 The topography of the state space. - 10. 3 The set of moves. - 10. 4 Global convergence. - 10. 5 Discussion. - 11 Implementation Aspects. - 11. 1 An implementation. - 11. 2 The selection function. - 11. 3 Other speed-up methods. - References. Language: English