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

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