TESTO PARALLELO INCASELLATO
Scopri come è facile capire l'inglese se c'è a fianco la traduzione parallela incasellata!

Simulated annealing (SA) is a generic probabilistic meta-algorithm for the global optimization problem, namely locating a good approximation to the global optimum of a given function in a large search space.

La Simulated annealing (tempra simulata) è una generica meta-euristica di tipo probabilistico per il problema dell'ottimizzazione globale, cioè trovare una buona approssimazione dell'ottimo globale di una data funzione in un vasto spazio di ricerca.

It was independently invented by S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi in 1983, and by V.Cerny in 1985.

È stata inventata indipendentemente da S. Kirkpatrick, C. D. Gelatt e M. P. Vecchi nel 1983, e da V. Cerny nel 1985.

The name and inspiration come from annealing in metallurgy, a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects.

Il nome e l'ispirazione derivano dal termine "tempratura" (annealing) della metallurgia, una tecnica implicante il riscaldamento e il raffreddamento controllato di un materiale per incrementare la dimensione dei suoi cristalli e ridurne i difetti.

The heat causes the atoms to become unstuck from their initial positions (a local minimum of the internal energy) and wander randomly through states of higher energy;

Il calore obbliga gli atomi a svincolarsi dalla loro posizione iniziale (un minimo locale dell'energia interna) e a vagare in modo casuale tra gli stati a più alta energia;

the slow cooling gives them more chances of finding configurations with lower internal energy than the initial one.

il lento raffreddamento dà loro più possibilità di trovare configurazioni con energia interna più bassa rispetto a quella iniziale.

Overview

Generalità

In the simulated annealing (SA) method, each point s of the search space is compared to a state of some physical system, and the function E(s) to be minimized is interpreted as the internal energy of the system in that state.

Nel metodo simulated annealing (SA), ciascun punto s dello spazio di ricerca è paragonato ad uno stato di qualche sistema fisico, e la funzione E(s) da minimizzare è rappresentata come l'energia interna del sistema in quello stato.

Therefore the goal is to bring the system, from an arbitrary initial state, to a state with the minimum possible energy.

Quindi lo scopo è quello di portare il sistema, da un arbitrario stato iniziale, ad uno stato con la minima energia possibile.

The basic iteration

L'iterazione base

At each step, the SA heuristic considers some neighbours of the current state s, and probabilistically decides between moving the system to state s' or staying put in state s.

Ad ogni passo, l'euristica SA considera alcuni stati prossimi dello stato attuale s, e probabilisticamente decide se muovere il sistema allo stato s' o rimanere fermo in s.

The probabilities are chosen so that the system ultimately tends to move to states of lower energy.

Le probabilità sono scelte in modo tale che in definitiva il sistema tenda a muoversi verso gli stati di minore energia.

Typically this step is repeated until the system reaches a state which is good enough for the application, or until a given computation budget has been exhausted.

Tipicamente questo passo è ripetuto fino al raggiungimento di uno stato che è abbastanza buono per l'applicazione, o fino all'effettuazione di una quantità predeterminata di calcoli.

The neighbours of a state

L'intorno di uno stato

The neighbours of each state are specified by the user, usually in an application-specific way.

L'intorno di ciascuno stato è specificato dall'utente, di solito in un modo valido per quel tipo di applicazione.

For example, in the traveling salesman problem, each state is typically defined as a particular tour (a permutation of the cities to be visited);

Per esempio, nel problema del commesso viaggiatore, ciascuno stato è tipicamente definito come un particolare giro (una permutazione delle città da visitare);

then one could define two tours to be neighbours if and only if one can be converted to the other by interchanging a pair of adjacent cities.

quindi si potrebbero definire due giri come due stati prossimi appartenenti ad un intorno se e solo se ciascuno può essere convertito nell'altro scambiando una coppia di città adiacenti.

Transition probabilities

Probabilità di transizione

The probability of making the transition to the new state s' is a function P(δE, T) of the energy difference δE = E(s' ) - E(s) between the two states, and of a global time-varying parameter T called the temperature.

La probabilità di porre in atto la transizione al nuovo stato s' è una funzione P(δE, T) della differenza delle energie δE = E(s' ) - E(s) tra i due stati, e un parametro globale T tempo-variante detto temperatura.

One essential feature of the SA method is that the transition probability P is defined to be nonzero when δE is positive, meaning that the system may move to the new state even when it is worse (has a higher energy) than the current one.

Una caratteristica essenziale del metodo SA è che la probabilità di transizione P è definita essere non nulla quando δE è positiva, intendendo con ciò che il sistema può spostarsi nel nuovo stato anche quando questo è peggiore (ha un'energia più alta) di quello attuale.

It is this feature that prevents the method from becoming stuck in a local minimum - a state whose energy is far from being minimum, but is still less than that of any neighbour.

È questa caratteristica che impedisce al metodo di bloccarsi in un minimo locale - uno stato la cui energia è lontana dall'essere minima, ma pur sempre inferiore a quella di ogni stato prossimo.

Also, when the temperature tends to zero and δE is positive, the probability P(δE, T) tends to zero.

Inoltre, quando la temperatura tende a zero e δE è positiva, la probabilità P(δE, T) tende a zero.

Therefore, for sufficiently small values T, the system will increasingly favor moves that go "downhill" (to lower energy values), and avoid those that go "uphill".

Quindi, per valori sufficientemente piccoli T, il sistema favorirà sempre più mosse che "scendono" (verso minori valori energetici), ed eviterà quelle che "salgono".

In particular, when T is 0, the procedure reduces to the greedy algorithm - which makes the move if and only if it goes downhill.

In particolare, quando T è 0, la procedura si riduce all'algoritmo greedy - che effettua la mossa se e solo se essa scende.

Also, an important property of the P function is that the probability of accepting a move decreases when (positive) δE grows bigger.

Ancora, un'importante proprietà della funzione P è che la probabilità di accettare una mossa decresce quando la δE (positiva) incrementa.

For any two moves that both have positive dE values the P function favours the smaller value (smaller loss).

Per due mosse qualsiasi che abbiano entrambe valori dE positivi la funzione P favorisce quello più piccolo (minore perdita).

When δE is negative, P(δE, T) = 1.

Quando δE è negativa, P(δE, T) = 1.

However, some implementations of the algorithm do not guarantee this property with the P function, but rather they explicitly check whether δE is negative, in which case the move is accepted.

E tuttavia alcune implementazioni dell'algoritmo non garantiscono questa proprietà con la funzione P, ma piuttosto verificano esplicitamente se δE è negativa, nel qual caso la mossa è accettata.

Obviously, the effect of the state energies on the system's evolution depends crucially on the temperature.

Ovviamente, l'effetto delle energie di stato sull'evoluzione del sistema dipende in modo cruciale dalla temperatura.

Roughly speaking, the evolution is sensitive only to coarser energy variations when T is large, and to finer variations when T is small.

Semplificando, l'evoluzione è sensibile solo a variazioni energetiche grezze quando T è grande, e a variazioni fini quando T è piccolo.

The annealing schedule

La schedulazione di annealing

Another essential feature of the SA method is that the temperature is gradually reduced as the simulation proceeds.

Un'altra caratteristica essenziale del metodo SA è che la temperatura viene gradualmente ridotta al procedere della simulazione.

Initially, T is set to a high value (or infinity), and it is decreased at each step according to some annealing schedule - which may be specified by the user, but must end with T=0 towards the end of the allotted time budget.

Inizialmente T è posto ad un valore alto (o infinito) ed è decrementato ad ogni passo in accordo a qualche schedulazione di annealing - che può essere specificato dall'utente, ma che deve terminare con T=0 verso la fine dei tempi preventivi assegnati.

In this way, the system is expected to wander initially towards a broad region of the search space containing good solutions, ignoring small features of the energy function;

In questo modo, ci si aspetta che il sistema inizialmente si muova verso una vasta regione dello spazio di ricerca contenente buone soluzioni, ignorando caratteristiche minori della funzione energia;

then drift towards low-energy regions that become narrower and narrower; and finally move downhill according to the steepest descent heuristic.

quindi devii verso regioni a bassa energia che diventano sempre più ristrette, e si muova finalmente in discesa in accordo con l'euristica più ripida.

In plain English

Esplicitamente

Given an incredibly hard problem, such as finding a set of 100 numbers that fit some characteristic, for which attempting to brute-force the problem would result in several million years worth of computation, this technique attempts to quickly find a "pretty good" answer by adjusting the current "set" (in this case some random sequence of 100 numbers) until a "better" answer is found (the way the adjustment is done depends on the problem).

Dato un problema straordinariamente complesso, come trovare un insieme di 100 numeri che rispondano a una particolare caratteristica, per il quale tentativi di risoluzione esatta si tradurrebbero in parecchi milioni di anni di calcolo, questa tecnica cerca di trovare rapidamente una risposta "piuttosto buona" aggiustando l'"insieme" attuale (in questo caso qualche sequenza casuale di 100 numeri) fino a trovare una risposta "migliore" (il modo in cui l'aggiustamento è fatto dipende dal problema).

The new set of numbers, or "neighbor", if more optimal, is then used as the current set and the process is repeated.

Il nuovo insieme di numeri o "stato prossimo", se più ottimale, è quindi usato come quello attuale e il processo viene ripetuto.

Sometimes a problem may arise when one approaches what is known as a local minimum, in this case, a set of numbers that is the "most optimized" for its current "region".

A volte può presentarsi un problema  quando si approssima quello che è conosciuto come un minimo locale, in questo caso, un insieme di numeri che è il "più ottimizzato" per la sua attuale "regione".

In an attempt to find a better optimization, this technique may use various methods to "jump out of" the current "pit", such as searching for better optimizations randomly by a factor of the inverse amount of the previous adjustment.

Nel tentativo di trovare una migliore ottimizzazione questa tecnica può usare vari metodi per "saltar fuori" dalla "buca" corrente, come cercare delle migliori ottimizzazioni casualmente per mezzo di un fattore della quantità inversa del precedente aggiustamento.

Keep in mind that implementations of this method are strictly problem specific, and so the way in which one finds an optimization will vary from problem to problem.

Teniamo presente che le implementazioni di questo metodo sono strettamente dipendenti dal problema, e così il modo con il quale si trova un'ottimizzazione cambierà da problema a problema.

Convergence to optimum

Convergenza all'ottimo

It can be shown that, for any given finite problem, the probability that the simulated annealing algorithm terminates with the global optimal solution approaches 1 as the annealing schedule is extended.

Può essere dimostrato che, per ogni problema finito dato, la probabilità che l'algoritmo simulated annealing (tempra simulata) termini con la soluzione globale ottima approssima 1 all'estendersi temporale della schedulazione di annealing.

This theoretical result is, however, not particularly helpful, since the annealing time required to ensure a significant probability of success will usually exceed the time required for a complete search of the solution space.

Questo risultato teorico non è, comunque, particolarmente utile, poiché il tempo di annealing richiesto per assicurare una significativa probabilità di successo eccederà di solito il tempo richiesto per una ricerca completa nello spazio delle soluzioni.

Pseudo-code

Pseudo-codice

The following pseudo-code implements the simulated annealing heuristic, as described above, starting from state s0 and continuing to a maximum of kmax steps or until a state with energy emax or less is found.

Il seguente pseudo-codice implementa l'euristica simulated annealing, come descritta sopra, partendo dallo stato s0 e continuando per un massimo di kmax passi o fino a quando si trovi uno stato con energia emax o inferiore.

The call neighbour(s) should generate a randomly chosen neighbour of a given state s;

La chiamata della funzione neighbour(s) dovrebbe generare uno stato prossimo casualmente scelto di un dato stato s;

the call random () should return a random value in the range [0, 1).

la chiamata a random () dovrebbe ritornare un valore casuale nell'intervallo [0, 1).

The annealing schedule is defined by the call temp(r), which should yield the temperature to use, given the fraction r of the time budget that has been expended so far.

La schedulazione di annealing è definita dalla chiamata a temp(r), che dovrebbe dare la temperatura da usare, data la frazione r del tempo preventivato che è stato speso finora.

Selecting the parameters

Selezione dei parametri

In order to apply the SA method to a specific problem, one must specify the state space, the neighbour selection method (which enumerates the candidates for the next state s'), the probability transition function, and the annealing schedule.

Per applicare il metodo SA ad uno specifico problema occorre indicare lo spazio degli stati, il metodo di selezione dello stato prossimo (che elenca i candidati per il successivo stato s' ), la funzione di probabilità delle transizioni e la schedulazione di annealing.

These choices can have a significant impact on the method's effectiveness.

Queste scelte possono avere un impatto significativo sull'efficacia del metodo.

Unfortunately, there are no choices that will be good for all problems, and there is no general way to find the best choices for a given problem.

Sfortunatamente non ci sono scelte buone per tutti i problemi, e non c'è alcun modo generale per trovare le migliori scelte per un dato problema.

It has been observed that applying the SA method is more of an art than a science.

È stato osservato che applicare il metodo SA è più un'arte che una scienza.

State neighbours

Stati prossimi

The neighbour selection method is particularly critical.

Il metodo di selezione dello stato prossimo è particolarmente critico.

The method may be modeled as a search graph - where the states are vertices, and there is an edge from each state to each of its neighbours.

Può essere modellato come un grafo di ricerca - dove gli stati sono vertici, e c'è un lato da ciascuno stato a ciascuno dei suoi vicini.

Roughly speaking, it must be possible to go from the initial state to a "good enough" state by a relatively short path on this graph, and such a path must be as likely as possible to be followed by the SA iteration.

Banalizzando deve essere possibile andare da uno stato iniziale a uno "abbastanza buono" per mezzo di un cammino relativamente corto su questo grafo, e tale cammino deve avere la probabilità più forte possibile di essere seguito dall'iterazione SA.

In practice, one tries to achieve this criterion by using a search graph where the neighbours of s are expected to have about the same energy as s.

In pratica si prova a realizzare questo criterio usando un grafo di ricerca in cui ci si aspetta che gli stati prossimi di s abbiano circa la sua stessa energia.

Thus, in the traveling salesman problem above, generating the neighbour by swapping two adjacent cities is expected to be more effective than swapping two arbitrary cities.

Così, nel problema del commesso viaggiatore suindicato, si pensa sia più efficace generare il successivo stato scambiando due città adiacenti piuttosto che due città arbitrarie.

It is true that reaching the goal can always be done with only n-1 general swaps, while it may take as many as n(n-1)/2 adjacent swaps.

È vero che il raggiungimento dello scopo può sempre essere ottenuto con soli n-1 scambi generali, mentre può richiedere fino a n(n-1)/2 scambi adiacenti.

However, if one were to apply a random general swap to a fairly good solution, one would almost certainly get a large energy increase;

Comunque, se si applicasse uno scambio generale casuale a una soluzione abbastanza buona, si otterebbe quasi certamente un grande incremento di energia;

whereas swapping two adjacent cities is likely to have a smaller effect on the energy.

laddove lo scambio di due città adiacenti è probabile abbia un effetto minore sull'energia.

Transition probabilities

Probabilità di transizione

The transition probability function P is not as critical as the neighbourhood graph, provided that it follows the general requirements of the SA method stated before.

La funzione di probabilità delle transizioni P non è così critica come il grafo degli stati prossimi, a condizione che esso segua i requisiti generali del metodo SA stabiliti prima.

Since the probabilities depend on the temperature T, in practice the same probability function is used for all problems, and the annealing schedule is adjusted accordingly.

Poiché le probabilità dipendono dalla temperatura T, in pratica la stessa funzione di probabilità è usata per tutti i problemi, e la schedulazione di annealing è adeguata di conseguenza.

The "classical" formula

La formula "classica"

In the original formulation of the method by Kirkpatrick et. al, the transition probability P(δE, T) was defined as 1 if δE < 0 (i.e., downhill moves were always performed);

Nella formulazione originale del metodo di Kirkpatrick et. al, la probabilità di transizione P(δE, T) è definita come 1 se δE < 0 (cioè, le mosse in discesa erano sempre effettuate);

otherwise, the probability would be

altrimenti la probabilità sarebbe

This formula comes from the Metropolis-Hastings algorithm, used here to generate samples from the Maxwell-Boltzmann distribution governing the distribution of energies of molecules in a gas.

Questa formula derivante dall'algoritmo di Metropolis-Hastings è usata qui per produrre esempi della funzione di Maxwell-Boltzmann che governa la distribuzione di energie delle molecole in un gas.

Other transition rules can be used, also.

Possono essere usate anche altre regole di transizione.

Annealing schedule

Schedulazione di annealing

The annealing schedule is less critical than the neighbourhood function, but still must be chosen with care.

La schedulazione di annealing è meno critica della funzione degli stati prossimi, ma deve ugualmente essere scelta con cura.

The initial temperature must be large enough to make the uphill and downhill transition probabilities about the same.

La temperatura iniziale deve essere grande abbastanza da rendere circa uguali le probabilità di transizione di salita e discesa.

To do that, one must have some estimate of the value of dE for a random state and its neighbours.

Per fare questo, si deve avere qualche stima del valore di dE per uno stato casuale e i suoi stati prossimi.

The temperature must then decrease so that it is zero, or nearly zero, at the end of the alloted time.

La temperatura deve quindi diminuire fino a diventare uguale a zero, o quasi, al termine del periodo di tempo assegnato.

A popular choice is the exponential schedule, where the temperature decreases by a fixed factor a < 1 at each step.

Una scelta frequente è data dalla schedulazione esponenziale, dove la temperatura decresce ad ogni passo di un fattore fisso a < 1.

Related methods

Metodi correlati

Tabu search (TS) is similar to simulated annealing, in that both traverse the solution space by testing neighbours of an individual solution.

La tabu search (TS) è simile alla simulated annealing, nel senso che entrambe attraversano lo spazio delle soluzioni testando l'intorno di una soluzione singola.

While simulated annealing generates only one neighbouring solution, tabu search generates many solutions and moves to the best solution of those generated.

Mentre la simulated annealing genera solo una soluzione prossima, la tabu search ne genera molte e si muove verso quella migliore tra quelle generate.

In order to prevent cycling and encourage greater movement through the solution space, a tabu list is maintained of partial or complete solutions.

Allo scopo di prevenire ricicli e incoraggiare movimenti maggiori attraverso lo spazio di ricerca, viene usata una tabu list di soluzioni parziali o complete.

It is forbidden to move to a solution that contains elements of the tabu list, which is updated as the solution traverses the solution space.

È proibito spostarsi verso una soluzione che contiene elementi della tabu list che viene continuamente aggiornata man mano che la soluzione attraversa lo spazio delle soluzioni.

Genetic algorithms (GA) maintain a pool of solutions rather than just one.

Gli algoritmi genetici (AG) si basano su un gruppo di soluzioni piuttosto che su una sola.

The process of finding superior solutions mimics that of evolution, with solutions being combined or mutated to alter the pool of solutions, with solutions of inferior quality being discarded.

Il processo di ricerca delle soluzioni ottime imita quello dell'evoluzione, con combinazioni o mutazioni che alterano il gruppo iniziale, scartando quelle di qualità inferiore.

Ant Colony Optimization (ACO) uses many ants (or agents) to traverse the solution space and find locally productive areas.

L'Ant Colony Optimization (ACO) ovvero ottimizzazione delle colonie di formiche usa molte formiche (o agenti) per attraversare lo spazio delle soluzioni e trovare aree localmente produttive.

While usually inferior to simulated annealing and other forms of local search, it is able to produce results in problems where no global or up-to-date perspective can be obtained, and thus the other methods cannot be applied.

Nonostante dia solitamente prestazioni inferiori alla simulated annealing e ad altre forme di ricerca locale, è in grado di produrre risultati in problemi in cui non è possibile ottenere una euristica globale o aggiornata per cui gli altri metodi non possono essere applicati.