Part III Improvements and Conjectures
2002
Myriad interesting versions of simulated annealing can be found in the literature. Most of the variants were introduced to improve the algorithm or to adapt it to a particular application. Some appear to be genuine improvements; some seem to relinquish the connection to the statistical mechanical underpinnings of simulated annealing and can at best be considered ad hoc methods. This part of the book is intended to be an accessible guide to some of the existing options for the novice practitioner. While extensive use is made of the theory developed in Part II, the reader eager to get on with his or her problem can read this part first and refer back to results as needed. In keeping with the title of this book, we restrict our scope to conjectures and demonstrated enhancements of the annealing method itself. Many of these enhancements hinge on the idea of a natural scale for a problem and thus are again based on our metatheorem: The more we exploit the structure of a problem, the better. Basically, the elements of annealing that can be further developed and optimized relative to the simplest bare-bones version already discussed in Chapter 4 are • the annealing schedule, • the move class, • acceptance criterion, and • the degree and method of parallelization. The next chapter introduces the idea of ensemble—pooling information from several identical runs ideally performed simultaneously. Chapter 8 deals with a practical problem that naturally arises when using ensembles: how to distribute in the best possible way a fixed amount of computing resources to a set of random walkers. The extreme choices, letting one walker do all the work, and having many walkers do one step each, do not seem intuitively appealing, and indeed it turns out that a compromise can be found leading to a better result. The remaining chapters of this part of the book deal with more detailed questions like the choice of objective function, annealing schedule, acceptance rule, and move class.