Ricerca locale e ricottura simulata: un commesso viaggiatore tra i capoluoghi di regione cechi

Il problema di ottimizzazione, il problema del commesso viaggiatore, l’hill climbing con l’intorno 2-opt, minimi locali e riavvii, la ricottura simulata, la temperatura e lo schema di raffreddamento — su un giro tra tredici capoluoghi di regione con un ottimo noto.

13 minuti Matěj Žalmánek 2026-10-15

Serie Basi di IA Parte 26 di 52

1. Mappa dell’intelligenza artificiale: che cos’è ciascuna cosa e come si incastra tutto
2. Breve storia dell’intelligenza artificiale: da Turing ai modelli linguistici
3. Dati, modello, addestramento, inferenza: i concetti di base su un unico esempio
4. Come leggere la notazione matematica: simboli, indici, sommatorie e quantificatori
5. Insiemi e relazioni: i mattoncini con cui si costruiscono le definizioni nell’IA
6. Funzioni e applicazioni: perché ogni modello di IA è una funzione
7. Logica e dimostrazioni: le regole con cui si ragiona nell’IA
8. Grafi e alberi: la struttura su cui poggiano la ricerca e le reti neurali
9. Algebra lineare per l’apprendimento automatico: vettori, matrici e perché l’IA soprattutto moltiplica
10. Derivate, gradiente e regola della catena: come un modello capisce in quale direzione imparare
11. Discesa del gradiente: come impara un modello
12. Che cos’è la probabilità: dal lancio di un dado agli assiomi di Kolmogorov
13. Probabilità condizionata e teorema di Bayes: come cambiare una stima quando scopri qualcosa di nuovo
14. Variabile aleatoria e funzione di ripartizione: una sola funzione che dice tutto sulla distribuzione
15. Funzione di densità e funzione di massa: perché una variabile continua ha probabilità zero in un punto
16. Valore atteso, varianza e covarianza: dove si trova una distribuzione, quanto è larga e che cosa è legato a che cosa
17. Panoramica delle distribuzioni di probabilità: Bernoulli, binomiale, Poisson, uniforme, normale ed esponenziale
18. Legge dei grandi numeri e teorema del limite centrale: perché le medie si comportano in modo così prevedibile
19. Statistica e stima dei parametri: massima verosimiglianza, MAP e intervalli di confidenza
20. Teoria dell’informazione: entropia, entropia incrociata e divergenza KL — da dove vengono le funzioni di perdita
21. Ricerca nello spazio degli stati: BFS, DFS, UCS e A* con animazioni
22. Giochi e avversari: minimax, potatura alfa-beta e Monte Carlo tree search
23. Soddisfacimento di vincoli: backtracking, propagazione dei vincoli e AC-3 su un sudoku e una mappa delle regioni ceche
24. Logica e sistemi basati sulla conoscenza: concatenazione in avanti e all’indietro, risoluzione e sistemi esperti
25. Pianificazione: STRIPS, il mondo dei blocchi, euristiche dal rilassamento e pianificazione negli agenti IA
26. Ricerca locale e ricottura simulata: un commesso viaggiatore tra i capoluoghi di regione cechi
27. Algoritmi genetici: popolazione, incrocio, mutazione e selezione su uno zaino per l’escursione
28. Strategie evolutive e programmazione genetica: dalla regola di un quinto alla legge di Keplero
29. Ottimizzazione con colonie di formiche: come una traccia di feromone trova un percorso breve
30. Ottimizzazione a sciame di particelle: inerzia, esperienza propria ed esperienza dello sciame
31. Neuroevoluzione: evoluzione dei pesi e della forma delle reti neurali e l’algoritmo NEAT
32. Insiemi fuzzy e funzioni di appartenenza: come scrivere «un po’ caldo»
33. Logica fuzzy e probabilità: perché «un po’ caldo» non significa «probabilmente caldo»
34. Logica fuzzy: t-norme, implicazioni e regole SE–ALLORA
35. Controllo fuzzy: Mamdani e Sugeno, dal ventilatore al pendolo inverso su un carrello
36. Clustering fuzzy: l’algoritmo fuzzy c-means e i punti tra i cluster
37. Sistemi neuro-fuzzy (ANFIS): regole fuzzy che imparano dai dati
38. Catene di Markov: matrice di transizione, distribuzione stazionaria e PageRank
39. Modelli di Markov nascosti: l’algoritmo di Viterbi e il casinò disonesto
40. Reti bayesiane: perché l’erba è bagnata e che cosa significa per l’irrigatore
41. Filtro di Kalman: come stimare da misure imprecise dove si trova un’auto e a che velocità va
42. Tipi di apprendimento automatico: supervisionato, non supervisionato, semi-supervisionato e altri
43. Prompt, contesto e RAG: come dare a un modello le informazioni giuste
44. Autoencoder variazionali (VAE): immagini nuove da uno spazio latente continuo
45. Reti generative avversarie (GAN): il falsario contro il detective
46. Modelli di diffusione: come il rumore puro diventa un’immagine
47. Processi decisionali di Markov: stati, azioni, ricompense ed equazioni di Bellman
48. Q-learning e DQN: imparare il valore delle azioni, dalla tabella alla rete neurale
49. Policy gradient e PPO: imparare direttamente la politica
50. Come funziona un agente IA: un modello linguistico in un ciclo con strumenti
51. Programmare con agenti IA: incarico, test e controllo
52. Valutazione e sicurezza dei sistemi di IA: come misurare e come sorvegliare

Programma completo della serie 52 di 83 argomenti pubblicati

Il fabbro che vuole una lama robusta non lascia raffreddare di colpo il metallo rovente — lo raffredda lentamente. Così gli atomi hanno il tempo di trovare una disposizione regolare con l’energia più bassa. Se il metallo si raffreddasse tutto d’un tratto, gli atomi resterebbero congelati dove si trovavano e la lama sarebbe fragile. Nel 1983 alcuni fisici si accorsero che proprio questo affligge anche gli algoritmi che cercano la soluzione migliore: se vanno solo «in discesa», restano congelati nella prima conca. Così è nata la ricottura simulata (simulated annealing) — e con essa una delle idee più utili dell’ottimizzazione.

Con questa parte inizia il modulo sugli algoritmi ispirati alla natura. Segue la parte Ricerca nello spazio degli stati, dove l’hill climbing e la ricottura sono comparsi per la prima volta.

1. Il problema di ottimizzazione

Definizione — problema di ottimizzazione e intorno

È dato un insieme di soluzioni ammissibili S e una funzione obiettivo f : S → ℝ. Cerchiamo s* = argmin_{s ∈ S} f(s) — la soluzione con il valore più piccolo (per la massimizzazione al contrario).

Un intorno è una funzione N : S → 2^S che assegna a ogni soluzione l’insieme delle soluzioni «vicine», quelle che se ne ottengono con una piccola modifica. Una soluzione s è un minimo locale se f(s) ≤ f(s′) per ogni s′ ∈ N(s), e un minimo globale se ciò vale per ogni s′ ∈ S.

2. Il problema del commesso viaggiatore

Un commesso viaggiatore deve visitare tutti e tredici i capoluoghi di regione della Cechia, passare da ciascuno una volta e tornare da dove è partito. Quale giro gli fa percorrere meno chilometri? Le distanze le calcoliamo in linea d’aria.

Definizione — problema del commesso viaggiatore (TSP)

Sono date n città e le distanze d(i, j). Una soluzione è una permutazione ciclica π delle città; la sua lunghezza è f(π) = ∑_k=1ⁿ d(π_k, π_k+1), dove π_n+1 = π₁.

I giri distinti (senza contare dove e in quale verso cominciano) sono (n − 1)! / 2. La versione decisionale del problema è NP-completa.

numero di giri = n! / (n · 2) = (n − 1)! / 2

n!

tutti gli ordini in cui si possono elencare n città — tante sono le permutazioni; ogni giro però vi è contato più volte

n

un giro non ha inizio: Praha → Brno → … → Praha è lo stesso percorso di Brno → … → Praha → Brno. Ogni giro può cominciare in una qualsiasi delle n città, quindi n volte di meno

2

la distanza all’andata è uguale a quella al ritorno, quindi un giro percorso al contrario è lo stesso percorso con la stessa lunghezza

Esempio — la distanza in linea d’aria da Praha a Brno

Le città sono date da latitudine φ e longitudine λ in gradi. Sul territorio della Cechia basta una proiezione piana approssimata: un grado di latitudine misura 110,57 km, un grado di longitudine 111,32 · cos φ₀ km, dove φ₀ = 49,8° è il centro del Paese (i meridiani convergono verso il polo). Allora

d(i, j) = √( (71,85 · Δλ)² + (110,57 · Δφ)² ).

Praha (50,08° N, 14,42° E), Brno (49,20°, 16,61°)

Δλ = 2,19° → 71,85 · 2,19 = 157,35 km verso est

Δφ = −0,88° → 110,57 · 0,88 = 97,30 km verso sud

d = √(157,35² + 97,30²) = √(24 759 + 9 467) = √34 226 ≈ 185,0 km

Rispetto al calcolo esatto sulla sfera, l’errore per distanze di questo tipo è intorno all’1 %; per confrontare i giri non importa.

Tredici città sono ancora abbastanza poche da poter calcolare l’ottimo esattamente — con la programmazione dinamica di Held e Karp sui sottoinsiemi di città, che richiede 2ⁿ · n² passi invece di (n − 1)!. Il giro più corto misura 1 060,4 km. Grazie a questo, per ogni algoritmo successivo vedremo esattamente quanto si è avvicinato all’ottimo:

Algoritmo — programmazione dinamica di Held e Karp (1962)

Numeriamo le città 0, …, n − 1 e partiamo dalla città 0. Per ogni insieme di città M ∋ 0 e ogni città j ∈ M indichiamo con D(M, j) la lunghezza del percorso più corto che parte da 0, passa esattamente per le città di M e termina in j. Allora

D({0}, 0) = 0,   D(M, j) = min_{k ∈ M ∖ {j}} [ D(M ∖ {j}, k) + d(k, j) ],

e la lunghezza del giro ottimo è min_{j ≠ 0} [ D(tutte le città, j) + d(j, 0) ]. I valori di D sono al massimo 2ⁿ · n e ciascuno è il minimo di al massimo n numeri.

n = 13:   2¹³ · 13² = 8 192 · 169 = 1 384 448 passi

provare tutti gli ordini da una partenza fissa: 12! = 479 001 600 — circa 346 volte di più

3. L’hill climbing e l’intorno 2-opt

Definizione — mossa 2-opt

Una mossa 2-opt toglie dal giro due archi non adiacenti (a, b) ed (e, f) e li sostituisce con gli archi (a, e) e (b, f) — cioè inverte l’ordine delle città tra b ed e. La lunghezza cambia di Δ = d(a, e) + d(b, f) − d(a, b) − d(e, f). L’intorno di un giro su n città conta (n − 1)(n − 2) / 2 mosse.

Δ = d(a, e) + d(b, f) − (d(a, b) + d(e, f))

Δ

di quanto si allunga il giro; un Δ negativo significa un accorciamento. In base al segno decidono sia l’hill climbing sia la ricottura, per questo ci serve calcolarlo a buon mercato

d(a, e) + d(b, f)

i due nuovi archi con cui ricolleghiamo le estremità tagliate — si sommano, perché allungano il giro

d(a, b) + d(e, f)

i due archi che abbiamo tagliato — si sottraggono, perché spariscono dal giro. Il tratto tra b ed e lo percorriamo solo al contrario e le distanze sono simmetriche, quindi la sua lunghezza non cambia e nella formula non compare

Algoritmo — hill climbing (discesa più ripida)

Parti da una soluzione casuale s. Ripeti: trova s′ ∈ N(s) con la f(s′) più piccola; se f(s′) < f(s), passa a s′, altrimenti fermati — s è un minimo locale.

def delta(c, i, j):                    # mossa 2-opt: inverti c[i..j]
    a, b = c[i - 1], c[i]
    e, f = c[j], c[(j + 1) % len(c)]
    return d(a, e) + d(b, f) - d(a, b) - d(e, f)

def horolezec(c):
    n = len(c)
    while True:
        tahy = [(i, j) for i in range(1, n - 1) for j in range(i + 1, n)]
        i, j = min(tahy, key=lambda t: delta(c, *t))   # discesa più ripida
        if delta(c, i, j) >= 0:                        # nulla accorcia il giro
            return c                                    # minimo locale
        c = c[:i] + c[i:j + 1][::-1] + c[j + 1:]

La prima città la lasciamo al suo posto (i ≥ 1) — il giro non ha inizio, quindi spostarla non porterebbe nulla di nuovo. Per n = 13 le coppie 1 ≤ i < j ≤ 12 danno esattamente 12 · 11 / 2 = 66 mosse.

Da un giro casuale lungo 2 402 km l’hill climbing arriva in 8 passi a 1 065,8 km — e lì si ferma. All’ottimo mancano solo 5 km, ma nessuna singola mossa 2-opt accorcia più il giro. L’hill climbing è in un minimo locale e non lo sa:

4. Dove si blocca l’hill climbing

Su cento partenze casuali, l’hill climbing è finito nell’ottimo 61 volte. Negli altri 39 casi si è bloccato altrove, nel peggiore a 1 162,6 km — cento chilometri più in là. Le trappole sono tre:

• Minimo locale — una conca da cui ogni passo porta in salita.
• Plateau — tutti i vicini sono ugualmente buoni, quindi l’hill climbing non sa dove andare.
• Cresta — una buona direzione esiste, ma non segue nessuna singola mossa; ci si arriva solo passando per soluzioni peggiori.

Esempio — perché l’hill climbing non esce da 1 065,8 km

L’hill climbing dalla prima partenza è finito sul giro Zlín → Ostrava → Olomouc → Pardubice → Hradec Králové → Liberec → Ústí nad Labem → Karlovy Vary → Plzeň → Praha → České Budějovice → Jihlava → Brno → Zlín. Calcoliamo il Δ di tutte le 66 mosse 2-opt: una di esse (l’inversione di tutto tranne la prima città) dà lo stesso giro nel verso opposto e Δ = 0, tutte le altre allungano il giro. La meno costosa inverte la coppia Pardubice – Hradec Králové:

a = Olomouc, b = Pardubice, e = Hradec Králové, f = Liberec

Δ = d(a, e) + d(b, f) − d(a, b) − d(e, f)

  = 122,9 + 95,9 − 116,8 − 83,0 = +19,0 km

Ogni singola mossa allunga quindi il giro di almeno 19,0 km — eppure l’ottimo è più corto di appena 5,4 km. La strada per arrivarci passa per giri peggiori, e quelli l’hill climbing non li accetta mai.

Il rimedio più semplice è il riavvio casuale: far ripartire l’hill climbing da un altro punto e tenere il risultato migliore. Se una partenza riesce con probabilità 0,61, allora su cinque partenze almeno una riesce con probabilità 1 − 0,39⁵ ≈ 99 %. Per un problema piccolo basta. In uno grande le conche sono milioni e servirebbero troppi riavvii.

P_r = 1 − (1 − p)^r

P_r

la probabilità che almeno una delle r partenze trovi l’ottimo — la calcoliamo tramite il complementare, perché «almeno una» ha molte forme, mentre «nessuna» una sola

1 − p

la probabilità che una partenza fallisca (da noi 0,39 su cento tentativi)

r

il numero di partenze all’esponente: le partenze sono indipendenti (ognuna ha un seme casuale diverso), quindi le probabilità di fallimento si moltiplicano

5. La ricottura simulata

Algoritmo — ricottura simulata

Parti da una soluzione casuale s con temperatura iniziale T₀. A ogni iterazione:

1. scegli un vicino casuale s′ ∈ N(s) e calcola Δ = f(s′) − f(s);
2. se Δ ≤ 0, passa a s′; altrimenti passaci con probabilità e^−Δ/T (criterio di Metropolis);
3. abbassa la temperatura secondo lo schema di raffreddamento, per esempio T ← α · T con 0 < α < 1.

Restituisci la soluzione migliore che hai visto lungo il cammino.

P(accettare) = min(1, e^{−Δ / T})

P(accettare)

con quale probabilità passiamo al vicino proposto; nel programma estraiamo u in modo uniforme da [0, 1) e accettiamo la mossa se u < P

min(1, …)

per un miglioramento (Δ ≤ 0) l’esponenziale è ≥ 1 e la probabilità non può superare 1 — un passo migliore si accetta quindi sempre, come nell’hill climbing

Δ

di quanto è peggiore il vicino, in km. Sta all’esponente con il segno meno, quindi ogni chilometro di peggioramento in più moltiplica la probabilità per lo stesso numero minore di 1 — i grandi peggioramenti sono esponenzialmente più rari dei piccoli

T

la temperatura, nelle stesse unità di Δ (km). Divide Δ e così ne fissa la scala: un peggioramento di T km passa con probabilità 1/e ≈ 0,37 a qualunque temperatura. Una T alta rende «piccoli» i grandi peggioramenti, T → 0 li vieta tutti

La regola per accettare un passo peggiore viene dalla fisica: nel 1953 Nicholas Metropolis e i suoi colleghi la usarono per simulare atomi in equilibrio termico, dove la probabilità di uno stato con energia E è proporzionale a e^−E/kT. Per l’ottimizzazione la adattarono nel 1983, indipendentemente, Kirkpatrick, Gelatt e Vecchi dell’IBM — e due anni dopo, anche lui in modo indipendente, il fisico slovacco Vladimír Černý, proprio sul problema del commesso viaggiatore.

import math, random

def zihani(c, T0=200, Tk=0.5, K=10_000):
    alfa = (Tk / T0) ** (1 / K)          # raffreddamento geometrico
    T, delka = T0, delka_okruhu(c)
    nej, nej_delka = c, delka
    for k in range(K):
        i, j = sorted(random.randint(1, len(c) - 1) for _ in range(2))
        if i != j:                          # i = j: nessuna mossa
            D = delta(c, i, j)
            if D <= 0 or random.random() < math.exp(-D / T):
                c = c[:i] + c[i:j + 1][::-1] + c[j + 1:]
                delka += D
                if delka < nej_delka:
                    nej, nej_delka = c, delka
        T *= alfa
    return nej

Ecco come va davvero: le prime sei iterazioni della nostra esecuzione e sei iterazioni dalla sua metà. p è la probabilità di accettazione min(1, e^−Δ/T), u il numero estratto; una mossa peggiorativa passa se u < p.

All’inizio, con T ≈ 200, passa anche una mossa che allunga il giro di 146,6 km — la probabilità è 0,48 ed è uscito u = 0,14. A metà dell’esecuzione T = 10 e il giro è già nell’ottimo; le mosse che lo allungherebbero di 70 chilometri o più hanno una probabilità sotto l’uno per mille e vengono tutte rifiutate. A volte i due numeri casuali cadono nello stesso punto (i = j) e l’iterazione non propone nulla — in tutta l’esecuzione è successo 824 volte.

Teorema — distribuzione di Boltzmann (formulazione odierna)

Se teniamo fissa la temperatura T e proponiamo i vicini in modo simmetrico (il vicino s′ viene proposto da s con la stessa probabilità con cui s viene proposto da s′ — per il 2-opt vale, perché la stessa mossa (i, j) riporta anche indietro), allora il processo di Metropolis è una catena di Markov la cui distribuzione stazionaria è

π_T(s) = e^−f(s)/T / Z(T)

π_T(s)

quanto spesso, dopo un lungo vagare alla temperatura T, ci troviamo nella soluzione s

e^−f(s)/T

il peso della soluzione: più è corto il giro f(s), più è grande. È esattamente il peso che il criterio di Metropolis bilancia — il rapporto tra i pesi di due vicini è e^−Δ/T

Z(T)

la somma dei pesi su tutte le soluzioni; dividiamo per essa perché le probabilità sommino a 1

Dimostrazione (condizione di bilancio dettagliato): per due vicini con f(s′) = f(s) + Δ, Δ > 0, il flusso da s a s′ è proporzionale a π(s) · e^−Δ/T e il flusso inverso a π(s′) · 1. Per π = π_T entrambe le espressioni valgono e^−f(s′)/T / Z, i flussi si pareggiano e la distribuzione non cambia più.

ottimo (1 060,4 km) contro la trappola dell’hill climbing (1 065,8 km): rapporto delle frequenze e^5,38/T

T = 100: 1,06   T = 10: 1,71   T = 1: 217   T = 0,5: 47 089

6. Temperatura e schema di raffreddamento

Che probabilità ha un passo che allunga il giro di 20 km? Dipende dalla temperatura:

A 200 passa quasi ogni passo peggiorativo, a 0,5 nessuno — in quel momento la ricottura si comporta come l’hill climbing. Lo schema di raffreddamento stabilisce per quanto tempo l’algoritmo «vaga» e per quanto «scende». La via d’uscita più economica dalla trappola dell’hill climbing (+19,0 km, vedi sopra) a T = 50 passerebbe con probabilità 0,68, a T = 10 con 0,15 e a T = 2 praticamente mai.

T_k = T₀ · α^k,   α = (T_K / T₀)^1/K

T_k

la temperatura all’iterazione k-esima — stabilisce quanto grandi peggioramenti si accettano ancora in quel momento

T₀

la temperatura iniziale; si sceglie in modo che all’inizio passi la maggior parte dei peggioramenti — da noi 200 km, più di una tipica mossa 2-opt su un giro casuale

α

il coefficiente di raffreddamento, appena sotto 1; lo calcoliamo dalla temperatura finale T_K e dal numero di iterazioni K, perché l’esecuzione finisca esattamente dove vogliamo

k

il numero dell’iterazione all’esponente: ogni iterazione moltiplica la temperatura per lo stesso numero, quindi nello stesso numero di iterazioni la temperatura scende sempre dello stesso rapporto — da 200 a 100 ci vuole quanto da 1 a 0,5

Teorema — convergenza della ricottura

Se la temperatura scende abbastanza lentamente, in modo logaritmico: T_k = c / ln(k + 1) con una costante c abbastanza grande, allora la probabilità che la ricottura termini in un minimo globale tende a uno al crescere del numero di iterazioni (Hajek, 1988).

«Abbastanza grande» significa esattamente c ≥ d*, dove d* è la profondità del minimo locale non globale più profondo: di quanto, come minimo, deve salire un percorso che ne parte prima di arrivare a una soluzione migliore.

se bastasse c = 20 km, la temperatura 0,5 l’avremmo solo quando ln(k + 1) = 20 / 0,5 = 40,

cioè dopo k ≈ e⁴⁰ ≈ 2,4 · 10¹⁷ iterazioni — circa un miliardo di volte più di tutti i 239 500 800 giri

7. La ricottura sui capoluoghi di regione

Lanciamo la ricottura sullo stesso problema: 10 000 iterazioni, la temperatura scende in modo geometrico da 200 a 0,5. La mappa mostra com’era il giro all’inizio e dopo 1 000, 3 000, 5 000 e 10 000 iterazioni:

Dopo mille iterazioni il giro è ancora caotico (1 985 km) — a temperatura alta la ricottura accetta quasi tutto. Dopo tremila ha già una forma (1 159 km) e dopo cinquemila è nell’ottimo, 1 060,4 km. Delle 1 498 mosse accettate, 695 erano peggiorative; l’hill climbing non ne avrebbe fatta nemmeno una. Il grafico mostra come la lunghezza del giro salta su e giù finché la temperatura non scende:

Il passaggio dal vagare allo scendere si vede anche nel numero di mosse accettate in ciascun migliaio di iterazioni: 597, 411, 232, 104, 35, 35, 26, 21, 26, 11. Nel primo migliaio, quando T è tra 200 e 110, si accetta più della metà delle proposte. Dal quinto migliaio (T sotto 20) ormai solo decine; di queste, le peggiorative sono state 37, di cui 26 piccole, sotto i 3 km.

E non è il caso fortunato di un’esecuzione: su cento esecuzioni con semi diversi, 98 sono finite nell’ottimo e le altre due a meno di 3 km di distanza. Rispetto al 61 % dell’hill climbing da una sola partenza è una grande differenza.

8. Quando conviene la ricottura

A essere onesti: la ricottura ha fatto 10 000 iterazioni, l’hill climbing da una sola partenza solo circa seicento valutazioni. Su un problema piccolo, l’hill climbing con riavvii allo stesso costo andrebbe altrettanto bene. La differenza emerge su un problema più grande. Prendiamo 60 città disposte a caso e diamo a entrambi gli algoritmi lo stesso budget — 200 000 mosse 2-opt valutate:

L’hill climbing è rientrato nel budget solo due volte: con 60 città l’intorno conta 1 711 mosse e la discesa più ripida le esamina tutte a ogni passo. La ricottura prova una mossa casuale alla volta e distribuisce lo stesso budget sull’esplorazione di tutto il paesaggio. Ognuna delle sue tre esecuzioni è finita meglio dell’hill climbing.

9. La ricottura nell’intelligenza artificiale e altrove

• Progettazione di chip e orari. Il posizionamento dei componenti su un chip è stato uno dei primi grandi impieghi della ricottura negli anni Ottanta; ancora oggi si usa per orari, percorsi di veicoli o la disposizione di un magazzino.
• Addestramento delle reti neurali. La discesa stocastica del gradiente calcola il gradiente su un piccolo lotto di dati, e così ogni passo è un po’ casuale — come la ricottura, può scivolare fuori da una conca poco profonda. Gli schemi del tasso di apprendimento che lo abbassano gradualmente si chiamano addirittura cosine annealing.
• La temperatura dei modelli linguistici. Quando un modello linguistico sceglie la parola successiva, divide i punteggi delle parole per la temperatura T e con la funzione softmax li trasforma in probabilità proporzionali a e^z/T — la stessa formula di Boltzmann. Una temperatura alta significa un testo più fantasioso e rischioso, una bassa uno più prudente e prevedibile.
• Ricottura quantistica. Computer specializzati (per esempio D-Wave) cercano il minimo dell’energia in modo fisico, sfruttando fenomeni quantistici. Se e quando siano più veloci degli algoritmi classici è ancora oggetto di ricerca.

Esempio — la temperatura nella scelta della parola successiva

Il modello assegna a tre candidati per la parola successiva i punteggi z = (2, 1, 0). La probabilità della parola i-esima è p_i = e^z_i/T / ∑_j e^z_j/T — la distribuzione di Boltzmann della sezione sulla ricottura, solo con «energia» −z.

T = 1:   (e², e¹, e⁰) = (7,39; 2,72; 1), somma 11,11 → 0,665; 0,245; 0,090

T = 0,5:   (e⁴, e², 1) = (54,6; 7,39; 1), somma 62,99 → 0,867; 0,117; 0,016

T = 2:   (e¹, e^0,5, 1) = (2,72; 1,65; 1), somma 5,37 → 0,506; 0,307; 0,186

Una temperatura più bassa sposta la probabilità verso il candidato migliore (per T → 0 è sempre lui), una più alta la distribuisce anche sulle parole meno probabili — proprio come la ricottura a temperatura alta accetta anche giri peggiori.

10. Riepilogo

• Un problema di ottimizzazione cerca la soluzione con il valore migliore della funzione obiettivo; la ricerca locale si muove nell’intorno della soluzione attuale.
• L’hill climbing va sempre verso il vicino migliore e si blocca in un minimo locale — sui capoluoghi di regione in 39 partenze su 100. I riavvii casuali aiutano nei problemi piccoli.
• La ricottura simulata accetta anche passi peggiori con probabilità e^−Δ/T; con il calare della temperatura passa dall’esplorazione alla discesa.
• Sui capoluoghi di regione ha trovato l’ottimo in 98 esecuzioni su 100; su un problema più grande ha battuto l’hill climbing con lo stesso budget.
• La stessa formula di Boltzmann vive nella temperatura dei modelli linguistici, e l’idea del raffreddamento negli schemi di apprendimento delle reti neurali.

Vuoi metterci le mani? Fai scrivere a un agente IA una ricottura per il tuo giro — magari tra i posti dove vuoi andare in vacanza — e prova che cosa succede con un raffreddamento troppo rapido.

La vedi diversamente? Scrivi a support@coden-app.com.