Simulated annealing

La ricerca simulated annealing è un algoritmo di ricerca locale nato dal perfezionamento dell'algoritmo hill climbing stocastico. La ricerca locale inizia da un nodo corrente iniziale e la scelta del nodo successore è generata casualmente ( esplorazione randomizzata ). A differenza dell'algoritmo hill climbing stocastico, nell'algoritmo simulated annealing la probabilità di conferma delle "mosse peggiorative" ( mosse verso il basso ) è ponderata allo scarto del peggioramento e al tempo ( temperatura ) di esecuzione dell'algoritmo. L'algoritmo non esclude a priori l'analisi delle mosse peggiorative ma le ammette con una probabilità decrescente nel corso del tempo.

SIMULATED ANNEALING ESEMPIO

Per comprendere l'algoritmo è opportuno scendere nel dettaglio. A partire dal nodo corrente l'algoritmo simulated annealing seleziona casualmente nelle vicinanze un nodo successore il cui valore può essere maggiore o minore rispetto al nodo corrente.

  • Nodo migliore. Il valore del nodo successore Vs è superiore al nodo corrente Vc. L'algoritmo simulated annealing lo sostituisce al nodo corrente comportandosi esattamente come l'algoritmo hill climbing.
  • Nodo peggiore. Il valore del nodo successore Vs è inferiore al nodo corrente Vc. L'algoritmo simulated annealing approva o meno la scelta in base a una probabilità calcolata in funzione dello scarto tra i due valori ( ΔE = Vs - Vc ) e del tempo di elaborazione ( temperatura ) dell'algoritmo. Ad esempio, la probabilità P può essere calcolata nel seguente modo:

p = e E/T

Una funzione esponenziale Y=eX restituisce valori Y positivi tra 0 e ∞. Per valori di X compresi tra -∞ e 0 la funzione esponenziale restituisce un valore Y positivo compreso tra 0 e 1.

FUNZIONE ESPONENZIALE


Nell'algoritmo simulated annealing la variabile indipendente X della funzione esponenziale è determinata dal rapporto tra lo scarto ΔE e la variabile T ( temperatura ). Vediamo nel dettaglio il significato delle due variabili.

  • Scarto ΔE. Lo scarto ΔE è determinato dalla differenza tra il valore del nodo successore Vs e quello del nodo corrente Vc. Essendo il nodo successore un nodo peggiore rispetto al nodo corrente, lo scarto ΔE è sempre negativo. Quanto maggiore è lo scarto tra i valori dei nodi, tanto minore è la probabilità della scelta del nodo successore di essere confermata dall'algoritmo.
  • Temperatura T. La variabile T indica la "temperatura" di raffreddamento del processo. A partire da un valore iniziale positivo, la variabile T tende progressivamente verso lo zero con il passare del tempo. In altri termini, la variabile T (temperatura) è elevata nelle prime fasi di elaborazione dell'algoritmo mentre è bassa nelle fasi finali. Nel funzionamento dell'algoritmo quanto maggiore è il valore della variabile T (temperatura) tanto maggiore è la probabilità che una scelta peggiorativa sia confermata dall'algoritmo. In conclusione, a parità di scarto ΔE la probabilità di una scelta peggioritiva decresce col passare del tempo.

Esempio pratico. Nella tabella seguente abbiamo calcolato le diverse probabilità di scelta di un nodo peggiore in relazione allo scarto ΔE e alla temperatura T del processo. Col passare del tempo la temperatura T si riduce progressivamente da 1,5 a 0,25. Come si può facilmente osservare, a parità di scarto ΔE la probabilità di scelta decresce man mano che si riduce il valore della variabile T ( temperatura ).

Ad esempio, la scelta di un nodo peggiore con scarto ΔE=-1 ( rispetto al nodo corrente ) ha una probabilità d'essere confermata pari al 51% quando la temperatura è 1,5 (temperatura alta) e al 2% quando la temperatura è 0,25 (temperatura bassa). Ciò equivale a dire che le scelte peggiorative ( mosse verso il basso ) sono analizzate dall'algoritmo prevalentemente nelle fasi iniziali del ciclo di elaborazione mentre sono scartate nelle fasi finali.

Esplorazione random più efficiente. Al pari di un algoritmo hill climbing stocastico anche la ricerca simulated annealing ammette l'analisi delle mosse peggiori per evitare il rischio di bloccarsi su un massimo locale. Tuttavia, l'algoritmo simulated annealing pondera la scelta in base a una probabilità decrescente nel corso del tempo. Questa caratteristica dell'algoritmo simulated annealing consente di migliorare il livello di efficienza dell'esplorazione randomizzata rispetto a un algoritmo hill climbing stocastico.

Perché si chiama simulated annealing. Il nome simulated annealing dell'algoritmo prende spunto dal processo di raffreddamento dei metalli. Il processo "annealing" è utilizzato nella metallurgia per temprare un metallo. Il processo inizia sempre a elevate temperature per permettere al metallo di eliminare le impurità. La temperatura viene progressivamente ridotta per consentire al metallo di indurirsi. Tuttavia, la temperatura non viene ridotta bruscamente per consentire di continuare a lavorare sul metallo caldo ed eliminare le eventuali imperfezioni residue.

https://www.okpedia.it/simulated_annealing


Segnala un errore o invia un suggerimento per migliorare la pagina


Ricerca soluzioni

Problemi


FacebookTwitterLinkedinLinkedin