The Annealing Algorithm - Ginneken, L. P. P. P. van

. .

Sommaire:
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.