Abstract
Simulated annealing is a probabilistic local search method for global combinatorial optimisation problems allowing gradual convergence to a near-optimal solution. It consists of a sequence of moves from a current solution to a better one according to certain transition rules while accepting occasionally some uphill solutions in order to guarantee diversity in the domain exploration and to avoid getting caught at local optima. The process is managed by a certain static or dynamic cooling schedule that controls the number of iterations. This meta-heuristic provides several advantages that include the ability of escaping local optima and the use of small amount of short-term memory. A wide range of applications and variants have hitherto emerged as a consequence of its adaptability to many combinatorial as well as continuous optimisation cases, and also its guaranteed asymptotic convergence to the global optimum.
TopPrinciples Of Simulated Annealing
Local search represents a main category of meta-heuristics that includes hill climbing, tabu search (Glover, 1986), simulated annealing (Kirkpatrick et al., 1983), and variable neighbourhood search (Mladenovic & Hansen, 1997). Local search algorithm is based on the idea consisting of starting at a given feasible solution and making, at each iteration, a sequence of moves from the current solution to a neighbouring one that improve the objective function. A neighbouring solution is determined according to a certain defined neighbourhood structure. For instance, for a solution consisting of a vector of a certain length, all vectors differing from by one component would be considered as neighbouring solutions. The iterative process is continuously repeated until reaching a (global) optimal solution or a near-optimal one if a time or iteration bound was erected. This heuristic has been initially known as hill climbing or iterative improvements. The subsequent meta-heuristics within this category have been developed with the aim to deal with some identified issues relevant to the search loop size and being caught at local optima.
Key Terms in this Chapter
Multi-Objective Optimisation: Also Multicriteria or Multi-attribute optimisation. The mathematical field dealing with optimisation problems that involve more than one objective function to be simultaneously optimised.
Statistical Mechanics: The mathematical physics field using probability theory to deal with thermodynamic behaviour of systems with large number of states.
Pareto Optimality: The quality of being optimal for a solution of any given multi-objective optimisation problem. Compared to mono-objective optimisation, the Pareto optimality is attained by means of a set of solutions, called Pareto set, rather than a single solution. A Pareto optimal solution corresponds to the best trade-off between all considered objective functions and implies no other solution exists that can improve at least one of the objective functions without any deterioration for any one of the others.
Heuristic: A low level method allowing to construct a feasible solution for a given problem. Due to its constructive aspect, meta-heuristics often involve one or more heuristic to construct initial or intermediate solutions.
Preference Structure: A term of decision science that refers to a generalisation of the concept of aggregating the objective functions under consideration into one objective function. It is a set of qualitative relations between the objectives or alternatives for which the resolution leads to a certain trade-off.
Greedy Algorithm: A constructive algorithm that takes the best alternative in every component choice without taking into account the quality of the whole solution.
Careful Annealing: A process in metallurgy consisting of heating a metal or alloy to a high temperature until the molecules become within a melted state and applying thereafter a slow cooling until they achieve a ground state.