Ricottura Simulata

La ricottura simulata, proposta da Kirkpatrick Gelatt e Vecchi (1983) e indipendentemente da Cerny (1985), è una metaeuristica a singola soluzione che emula il lento raffreddamento dei metalli per formare strutture cristalline a bassa energia. L'algoritmo parte da una temperatura iniziale elevata T0 e valuta ogni mossa di vicinato tramite Δ = f(nuova) − f(corrente): le mosse migliorative (Δ < 0) sono sempre accettate, quelle peggiorative (Δ > 0) con probabilità Metropolis P = exp(−Δ / T). L'accettazione delle mosse peggiorative è il tratto distintivo che consente di sfuggire ai bacini di ottimo locale. La temperatura decresce secondo uno schema di raffreddamento: geometrico T_k+1 = αT_k con α ∈ [0.85, 0.99], logaritmico (Geman e Geman 1984, convergente in teoria ma lento) o adattivo. Schema di raffreddamento, temperatura iniziale (regola pratica: tasso di accettazione iniziale circa 80 per cento), numero di tentativi per temperatura e criterio di arresto sono i parametri critici. Rispetto agli algoritmi genetici mantiene una sola soluzione, non richiede popolazione e usa memoria minima. Applicazioni: layout VLSI, instradamento veicoli, scheduling, layout impianti. Su problemi combinatori compete strettamente con la tabu search. Riferimenti: Aarts e Korst (1989), Henderson Jacobson Johnson (2003).