An efficient proposal for the application of simulated annealing algorithms

Risultato della ricerca: Paper

2 Citazioni (Scopus)

Abstract

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.
Lingua originaleEnglish
Stato di pubblicazionePublished - 2014

Fingerprint

Simulated annealing
Cooling
Tabu search
Tuning
Genetic algorithms

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Engineering(all)
  • Software

Cita questo

@conference{cba5f1c1dcf2415a8569b26ff3a87b6c,
title = "An efficient proposal for the application of simulated annealing algorithms",
abstract = "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.",
author = "Gianfranco Passannanti and Toni Lupo and Antonella Certa",
year = "2014",
language = "English",

}

TY - CONF

T1 - An efficient proposal for the application of simulated annealing algorithms

AU - Passannanti, Gianfranco

AU - Lupo, Toni

AU - Certa, Antonella

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10447/96172

M3 - Paper

ER -