An efficient proposal for the application of simulated annealing algorithms

Complex nonlinear optimization problems require specific resolution techniques. These problems are often characterized by a solution space that presents many local optima. In these cases, local search algorithms, as the classical descent neighborhood search method, have a heavy drawback: the optimization algorithm generally converges towards a local minimum. To avoid getting trapped in a local minimum, the optimization algorithm must allow to accept worse solutions than the current one. Several kinds of algorithms have been ideated for this purpose and they differ for the acceptance criteria of a pejorative solution. Among such algorithms it is possible to remember the Taboo Search (TS) and the Simulated Annealing (SA). Another class of algorithms, i.e. the Genetic Algorithms (GAs), is based on the evolution of a set (population) of initial solutions. Such classes of algorithms have been applied to several different fields of research. Our interest is addressed to the SA algorithms, in particular to the cooling law, which is fundamental for the SA efficiency. In particular, in the present paper a new cooling law has been proposed for an optimization procedure based on the use of the Simulated Annealing algorithms. The proposal advanced has been tested on the job shop scheduling problem with sequences-dependent set-up times [1] taking into account cases study already treated in the literature [2]. The results show that its utilization allows obtaining a very higher convergence quickness than that one arising from the use of a traditional cooling law. Another strong advantage, that derives from the implementation of algorithms based on the use of the proposal formulation, is the possibility to bypass the classical tuning phase, so determining a further reduction of the global run-time.