Facts, Conjectures, and Improvements for Simulated Annealing

Peter Salamon
San Diego State University
San Diego, California
Paolo Sibani
University of Southern Denmark
Odense, Denmark
Richard Frost
San Diego State University
San Diego, California
Society for Industrial and Applied Mathematics
Philadelphia
SIAM

Contents
List of Figures ix
Preface xi
Acknowledgments xiii
I Overview 1
1 The Place of Simulated Annealing in the Arsenal of Global Optimization 3
2 Six Simulated Annealing Problems 7
2.1 Problem Definitions 7
2.2 Move Classes 14
3 Nomenclature 17
4 Bare-Bones Simulated Annealing 19
II Facts 23
5 Equilibrium Statistical Mechanics 25
5.1 The Number of States That Realize a Distribution 26
5.2 Derivation of the Boltzmann Distribution 29
5.3 Averages and Fluctuations 33
6 Relaxation Dynamics—Finite Markov Chains 35
6.1 Finite Markov Chains 36
6.2 Reversibility and Stationary Distributions 40
6.3 Relaxation to the Stationary Distribution 41
6.4 Equilibrium Fluctuations 43
6.4.1 The Correlation Function 44
6.4.2 Linear Response and the Decay of the Correlation Function 45
6.5 Standard Examples of the Relaxation Paradigm 47
6.5.1 Two-State System 47
6.5.2 A Folk Theorem—Arrhenius' or Kramers' Law 49
6.6 Glassy Systems 51
III Improvements and Conjectures 53
7 Ensembles 55
8 The Brick Wall Effect and Optimal Ensemble Size 57
9 The Objective Function 63
9.1 Imperfectly Known Objective 63
9.2 Implications of Noise 64
9.3 Deforming the Energy 65
9.4 Eventually Monotonic Deformations 65
10 Move Classes and Their Implementations 67
10.1 What Makes a Move Class Good? 67
10.1.1 Natural Scales 67
10.1.2 Correlation Length and Correlation Time 68
10.1.3 Relaxation Time at Finite T 69
10.1.4 Combinatorial Work 70
10.2 More Refined Move Schemes 70
10.2.1 Basin Hopping 70
10.2.2 Fast Annealing 71
10.2.3 Rejectionless Monte Carlo 72
11 Acceptance Rules 75
11.1 Tsallis Acceptance Probabilities 76
11.2 Threshold Accepting 76
11.3 Optimality of Threshold Accepting 76
12 Thermodynamic Portraits 79
12.1 Equilibrium Information 79
12.1.1 Histogram Method 81
12.2 Dynamic Information 84
12.2.1 Transition Matrix Method 84
12.3 Time-Resolved Information 86
12.A Appendix: Why Lumping Preserves the Stationary Distribution . . . . 87
13 Selecting the Schedule 89
13.1 Start and Stop Temperatures 90
13.2 Simple Schedules 90
13.2.1 The Sure-to-Get-You-There Schedule 90
13.2.2 The Exponential Schedule 91
13.2.3 Other Simple Schedules 91
13.3 Adaptive Cooling 92
13.3.1 Using the System's Scale of Time 92
13.3.2 Using the System's Scale of Energy 93
13.3.3 Using Both Energy and Time Scales 93
13.4 Nonmonotonic Schedules 96
13.5 Conclusions Regarding Schedules 97
14 Estimating the Global Minimum Energy 99
IV Toward Structure Theory and Real Understanding 103
15 Structure Theory of Complex Systems 105
15.1 The Coarse Structure of the Landscape 106
15.2 Exploring the State Space Structure: Tools and Concepts 107
15.3 The Structure of a Basin 110
15.4 Examples 111
15.A Appendix: Entropic Barriers 114
15.A.1 The Master Equation 115
15.A.2 Random Walks on Flat Landscapes 115
15.A.3 Bounds on Relaxation Times for General Graphs 116
16 What Makes Annealing Tick? 119
16.1 The Dynamics of Draining a Basin 119
16.2 Putting It Together 120
16.3 Conclusions 121
V Resources 123
17 Supplementary Materials 125
17.1 Software 125
17.1.1 Simulated Annealing from the Web 125
17.1.2 The Methods of This Book 126
17.1.3 Software Libraries 126
17.2 Energy Landscapes Database 127
Bibliography 129
Index 139

Genetic algorithm - Wikipedia, the free encyclopedia
Main page - Introduction to Genetic Algorithms

Practical Genetic Algorithms
Introduction to Genetic Algorithms
Other Genetic Algorithm Books
Download