Article Preview
TopIntroduction
In all areas of engineering, physical and social sciences, one encounters problems involving the optimization of some objective function. Usually, the problem to solve can be formulated precisely but is often, difficult or impossible to solve either analytically or through conventional numerical procedures. This is the case when the problem is non-convex and so inherently nonlinear and multimodal. In fact it is now well established that the frontier between the efficiently solvable optimization problems and the others rely on its convexity (Rockafellar, 1993). This is confirmed by the fact that very efficient algorithms for solving convex problems exist (Boyd & Vandenberghe, 2004), whereas the problem of non-convex optimization remains largely open despite an enormous amount of effort devoted to its resolution.
In this context, several heuristic methods, also called metaheuristics, have been developed in the last two decades, which have demonstrated a strong ability to solve problems that were previously difficult or impossible to solve (Fogel, 2006, Kirkpatrick & Gelatt, 1983, Toscano, 2013). These metaheuristics include simulated annealing (SA), genetic algorithm (GA), particle swarm (PS), to cite only the most used in the framework of continuous optimization problems.
Simulated annealing (SA) is a random-search method introduced by S. Kirkpatrick in 1983 and by V. Cerný in 1985 (Kirkpatrick & Gelatt, 1983, Cerny, 1985). The name comes from a technique used in metallurgy, called annealing, which consists in heating and slowly cooling a metal to obtain a “well ordered” solid state of minimal energy (Dréo et al., 2006). An interesting property of SA is its ability to avoid getting stuck in a local minima. This is obtained by using a random procedure which not only accepts changes that decrease the cost function J (assuming a minimization problem), but also some changes that increase it. The latter are accepted with a probability exp(-ΔJ/T), where ΔJ is the increase in J and T is a control parameter, which by analogy with the physical annealing is known as the system temperature. The main advantage of the SA is that it achieves a good quality solution, i.e. the absolute error to the global minimum is generally lower than that obtained via other metaheuristics. Moreover, it is versatile and easy to implement. The main drawbacks of SA lie mainly in the choice of the various parameters involved by this algorithm. The results obtained are indeed very sensitive to the parameter settings. Consequently, the problem of the selection of the “good parameters” (for a given cost function) is a crucial issue, which is however not yet entirely solved. Another weakness of the method, linked to the problem of parameter setting, is its excessive computing time in most applications. More detailed developments on SA, both practical and theoretical, can be found in (Spall 2003, Dréo et al., 2006).