Il perché, il cosa e il boh? del Simulated Annealing

In questo articolo introdurremo una classe di problemi piuttosto complessi (l'ottimizzazione di funzioni discrete) e una bella soluzione per affrontarli (il simulated annealing). Entriamo nel merito.

Un giorno ho visto un fisico (capelli strani, maglione buffo, incapacità di scrivere le lettere greche) che stava davanti a una ciotola di zolfo bollente. Ha quindi proceduto a raffreddarla con del ghiaccio, ottenendo così un brodo freddo e imbevibile. Poi è stata raffreddata un'altra ciotola (ci è voluto più tempo, così abbiamo chiacchierato: sono creature simpatiche, a differenza dei matematici). La seconda ciotola è finita in cristalli e il fisico insisteva che la struttura cristallina (reticolo, dice lui) trattiene più energia nella sua struttura ordinata: la sua tesi era che in questo modo aveva ottimizzato (massimizzato) l'energia dell'intero sistema. Ha chiamato il processo di minimizzazione Annealing.

Diventiamo tecnici: il simulated annealing è un processo stocastico (statistica + tempo). Il processo stesso è strutturato in modo da conservare una memoria limitata dei passi precedenti, sotto forma di probabilità: la probabilità di un risultato al passo t è influenzata dalle realizzazioni dei passi precedenti.

Prob{S(t)=s | S(t-1)=s’}

Quando questa memoria è limitata al solo passo precedente, si parla di Catene di Markov. Dati s e s' potremmo costruire una matrice A (una matrice stocastica, con valori >=0 e con somma di ogni riga =1). Queste premesse portano a molte pagine di calcoli (Chapman-Kolmogorov, Lipschitz, e anche catene ergodiche) che in questo articolo verranno saltate. Semplifichiamo con un esempio: le griglie del sudoku. Un momento, il sudoku va ancora di moda? Sì:

Descriviamo una griglia di sudoku come un vettore discreto in un iperspazio discreto a 81 dimensioni (81 essendo 9*9). Procediamo poi a definire una funzione su questi vettori: il numero di celle non valide, in base alle regole del sudoku. Ora, se fosse una funzione continua, il compito di ottimizzazione (trovare un minimo, in questo caso) sarebbe stato svolto tramite la derivata, ma con le funzioni discrete parlare di derivate semplicemente non ha senso. State pensando di controllare tutte le soluzioni possibili? 81 dimensioni per 9 posizioni per dimensione portano a 9^81=1*10^77 possibilità, che è un po' troppo. Il simulated annealing invece si esegue come un processo casuale: a ogni passo perturba una singola componente casuale del vettore (una delle celle della griglia del sudoku). Questo genera un nuovo vettore verso cui l'algoritmo può spostarsi con una certa probabilità. La probabilità di spostarsi da un vettore a un altro è esattamente la nostra matrice stocastica, ed è definita come segue. Dato uno stato di partenza i, uno stato di arrivo j ed essendo f(x) la funzione da minimizzare, la probabilità di spostarsi da i a j è data da:

Pij = min {1 , exp(-beta*(f(j)-f(i)))}

Questa probabilità è sempre uno quando il nuovo stato è migliore del precedente (cioè meno errori nella griglia del sudoku), mentre è una probabilità maggiore di zero quando il nuovo stato è peggiore, con probabilità più basse per pendenze maggiori della funzione da ottimizzare. Quanto a beta, rappresenta la temperatura del sistema: temperature alte generano movimenti rapidi nell'iperspazio, temperature basse servono per piccoli passi di aggiustamento. Questo è cruciale per qualsiasi euristica di ottimizzazione discreta, a causa del rischio di rimanere bloccati in un minimo locale (un bacino locale) e di perdere la soluzione migliore globale. Quindi il nostro simulated annealing dovrebbe muoversi velocemente all'inizio, per poi rallentare verso la fine.

Ma questo porterà a una soluzione?

Senza entrare troppo nel tecnico, una soluzione può sempre essere trovata (a tempo infinito) quando la matrice stocastica è tale che la probabilità di spostarsi da uno stato i a uno stato j è diversa da zero (questo non implica che la matrice non abbia celle a zero, una sequenza i->k->j è perfettamente accettabile).

Basta con le parole e passiamo ai fatti: usiamo questa griglia (tra virgolette) difficile presa da http://sudokublog.typepad.com/sudokublog/2005/08/page/2/

E il risultato, dopo appena 1482358 iterazioni, è...