Ricottura simulata

La ricottura simulata^[1] (dall'inglese simulated annealing) è una strategia utilizzata per risolvere problemi di ottimizzazione, che mira a trovare un minimo globale quando si è in presenza di più minimi locali.

Il termine "ricottura" è un'analogia con l'omonimo concetto nella scienza dei metalli, dov'è usato per descrivere il processo di eliminazione di difetti reticolari dai cristalli tramite riscaldamento seguito da lento raffreddamento.^[1] In questo caso un difetto reticolare corrisponde ad una combinazione errata di due oggetti (ad esempio una connessione errata di due neuroni all'interno di una rete neurale artificiale).

Procedimento di utilizzo modifica

È scelta una temperatura iniziale arbitraria:
1. Si sonda il problema per individuarne le possibili soluzioni (da 50 a 100 soluzioni);
2. Per ogni possibile soluzione se ne calcola il costo;
3. Si prende il $\Delta E_{max}$ ;
4. A questo punto si prende una temperatura iniziale maggiore della variazione di energia ( $T_{iniziale}>\Delta E_{max}$ ) ma dello stesso ordine di grandezza;
Si abbassa la temperatura fino a raggiungere un valore prossimo allo 0;
In prossimità del minimo valore di T si trova un minimo (di energia) abbastanza forte;
Ripetendo questo ciclo, la possibilità di trovare la stessa soluzione tende a 0. Se si sono trovate due soluzioni uguali per due prove diverse dello stesso problema significa che molto probabilmente qualcosa non funziona.

La temperatura della rete è definita in modo che:

Se T è elevata: ci si può permettere di fare salti alti, e quando si trova un minimo si prova a proseguire per scoprire se si tratti solo di un minimo locale;
Se T è bassa: si possono ancora fare salti alti ma con minore probabilità, quindi si procede a passi più corti;
Riduzione veloce di T: implica il congelamento di alcune fluttuazioni termiche;
Riduzione molto lenta di T: può implicare il non raggiungimento della conclusione del calcolo e quindi il non trovare un minimo globale.