ABSTRACT
This chapter will present the essential components of the simulated annealing (SA) algorithm and review its origins and potential for solving a wide range of optimization problems, in a manner that is accessible to the widest possible audience. Some historical perspective and description of recent research results will also be provided. During the course of this review bibliographical references will be provided to guide the interested reader to sources that contain additional theoretical results and complete details of individual applications. Many problems in a variety of disciplines can be formulated as optimization problems; and most
of these can be solved by adopting one of two “popular” approaches: divide-and-conquer or hillclimbing techniques (other approaches can be adopted, see for example, [31], and see also Chapters 30-32). In the first approach, the solution is problem-dependent, and typically detailed information about the problem is required in order to develop a solution strategy. Also, not many problems can be subdivided into smaller parts that can be solved separately and then recombined. In the second approach, most hill-climbing algorithms are based on gradient descent methods. These methods suffer from a major drawback of getting trapped in a local minimum. That is, the algorithmmay get “trapped” in a valley, from which all paths lead to locally worse solutions, and will never get to an optimal solution that lies outside the valley. The SA algorithm avoids local minima by introducing an element of randomness into the search process [36]. Over the last few years the SA algorithm and its many extensions and refinements have been
extensively employed to solve a wide range of application domains, especially in combinatorial optimization problems [2,5,8,13,15,47,54,57,58]. An important characteristic of the SA algorithm is
and
that it does not require specialist knowledge about how to solve a particular problem. This makes the algorithm generic in the sense that it can be used in a variety of optimization problems without the need to change the basic structure of the computations. The versatility of SAhas attractedmany researchers over a number years, andhas recently spawned
a number of variations to the original algorithm, including parallel versions to speed up the rate of computations [18,19,25,42,51,62].
