Ricottura simulata

La ricottura simulata^[1] (dall'inglese simulated annealing^[2], SA) è una strategia utilizzata per risolvere problemi di ottimizzazione, che mira a trovare un minimo globale quando si è in presenza di più minimi locali. Specificamente, può essere considerato una tecnica metaeuristica per approssimare l’ottimizzazione globale in uno spazio di ricerca grande per un dato problema. In caso di un gran numero di ottimi locali, SA può trovare l'ottimo globale. Viene spesso usato quando lo spazio di ricerca è discreto (ad esempio nel problema del commesso viaggiatore, nel problema di soddisfacibilità booleana, nella predizione della struttura proteica). Dovendo risolvere problemi per i quali si abbia a disposizione un quantitativo prefissato di risorse computazionali, trovare un ottimo globale approssimato può essere più importante rispetto a cercarne uno esatto ma locale. In tali casi, SA può risultare preferibile ad algoritmi esatti quali la discesa del gradiente o il branch and bound.

I problemi risolti da SA sono generalmente formulati mediante una funzione obiettivo a più variabili, soggetta a diversi vincoli matematici. In pratica, il vincolo può essere penalizzato come parte della funzione obiettivo.

Il termine "ricottura" (o tempratura) è 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.^[3] 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

1. Scelta di 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 considera la variazione di energia ${\displaystyle \Delta E_{max}}$;
   4. A questo punto si può sceglie una temperatura iniziale maggiore di tale variazione, ${\displaystyle T_{iniziale}>\Delta E_{max}}$, ma dello stesso ordine di grandezza;
2. Si abbassa la temperatura fino a raggiungere un valore prossimo allo 0;
3. In prossimità del minimo valore di ${\displaystyle T}$ si trova un minimo (di energia) abbastanza forte;
4. 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:

1. Se ${\displaystyle 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;
2. Se ${\displaystyle T}$ è bassa: si possono ancora fare salti alti ma con minore probabilità, quindi si procede a passi più corti;
3. Riduzione veloce di ${\displaystyle T}$: implica il congelamento di alcune fluttuazioni termiche;
4. Riduzione molto lenta di ${\displaystyle T}$: può implicare il non raggiungimento della conclusione del calcolo e quindi il non trovare un minimo globale.