Skip to content
Torna ai risultati

Raffreddamento Similato — Ottimizzazione Probabilistica

Anno
1983
Tipo
Probabilistic metaheuristic / local search

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

Il raffreddamento similato è una meta-euristica probabilistica di ricerca locale introdotta da Kirkpatrick, Gelatt e Vecchi nel 1983.

Modella il processo fisico di ricottura (annealing) in metallurgia — dove un materiale viene riscaldato e poi lentamente raffreddato per raggiungere uno stato cristallino a bassa energia — e usa questa analogia per sfuggire ai minimi locali in problemi di ottimizzazione combinatoria e continua.

L’intuizione alla base del metodo

Immaginate di cercare di trovare il punto più basso in un paesaggio collinare mentre siete bendati. Una ricerca puramente golosa (greedy) avanza sempre in discesa e si blocca nella prima valle che trova — che potrebbe non essere la più profonda. Il raffreddamento similato introduce una casualità controllata: all'inizio, quando la 'temperatura' è alta, l'algoritmo è disposto a salire occasionalmente, accettando per caso una soluzione peggiore. Man mano che la temperatura diminuisce secondo un programma di raffreddamento, l'algoritmo diventa sempre più selettivo, convergendo verso una soluzione. Questa disponibilità ad accettare mosse peggiori ad alta temperatura è ciò che permette al metodo di sfuggire ai minimi locali superficiali e di esplorare il paesaggio più a fondo.

Storia

Il raffreddamento similato è stato introdotto da Kirkpatrick, Gelatt e Vecchi nel loro articolo fondamentale del 1983 su Science, che trasse un'analogia esplicita tra il ricottura termodinamica dei solidi e l'ottimizzazione combinatoria. La stessa idea fu proposta indipendentemente da Cerny (1985) nel contesto del problema del commesso viaggiatore. van Laarhoven e Aarts (1987) fornirono il primo trattamento teorico rigoroso, dimostrando le proprietà di convergenza sotto vari programmi di raffreddamento. Da allora il metodo è diventato una delle meta-euristiche più studiate e applicate, utilizzata nella progettazione ingegneristica, nella ricerca operativa, nel layout VLSI e nell'ottimizzazione degli iperparametri del machine learning.

Quando usarlo

Il raffreddamento similato è applicabile a qualsiasi problema in cui si possa definire una struttura di vicinato nello spazio delle soluzioni, indipendentemente dal fatto che la funzione obiettivo sia differenziabile, convessa, o persino esprimibile analiticamente. È particolarmente adatto a problemi combinatori (pianificazione, routing, problemi su grafi) e all'ottimizzazione continua a scatola nera (black-box). Non sono richiesti dati di addestramento né assunzioni di normalità. Il programma di raffreddamento e la struttura del vicinato devono essere calibrati sul problema; eseguire meno di circa 1 000 iterazioni rischia la convergenza prematura a un minimo locale, nel qual caso dovrebbe essere preferita una ricerca locale deterministica più semplice.

Limiti e considerazioni

  • La qualità della soluzione è sensibile al programma di raffreddamento; un programma scadente può produrre risultati non migliori della ricerca casuale.
  • La struttura del vicinato deve essere progettata per ogni classe di problema, il che richiede competenza di dominio.
  • La convergenza all'ottimo globale richiede in pratica un raffreddamento estremamente lento, rendendo il tempo di esecuzione lungo per garanzie di alta qualità.
  • Non sfrutta informazioni sul gradiente o sulla struttura, quindi i metodi basati sul gradiente lo superano su problemi lisci e differenziabili.

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Può sfuggire ai minimi locali attraverso l'accettazione probabilistica di soluzioni peggiori, a differenza del puro hill-climbing.
  • Applicabile a quasi ogni tipo di problema — combinatorio, continuo, misto — purché sia definita una struttura di vicinato.
  • Non richiede informazioni sul gradiente ed è indifferente alla struttura matematica della funzione obiettivo.
  • Ha una garanzia teorica di convergenza all'ottimo globale sotto un raffreddamento sufficientemente lento (Hajek 1988).
  • Pochi iperparametri: temperatura iniziale, tasso di raffreddamento e struttura del vicinato.

Applicazioni

  • Problemi di pianificazione e orari combinatori in cui lo spazio delle soluzioni è troppo grande per una ricerca esaustiva.
  • Problemi del commesso viaggiatore e di routing dei veicoli nella logistica e nella ricerca operativa.
  • Layout di circuiti VLSI e floor-planning di chip nell'ingegneria elettrica.
  • Piegamento delle proteine e problemi di conformazione molecolare in biologia computazionale.
  • Ottimizzazione degli iperparametri per modelli di machine learning quando le informazioni sul gradiente non sono disponibili.
  • Problemi di allocazione e assegnazione di risorse in ingegneria e scienze gestionali.

Come funziona

Come funziona

1

L'algoritmo inizia con una soluzione iniziale — un punto ammissibile qualsiasi nello spazio di ricerca — e una temperatura iniziale alta. La soluzione iniziale può essere casuale o specifica del problema; la temperatura iniziale è tipicamente impostata abbastanza alta da accettare quasi ogni soluzione vicina all'inizio.

2

Viene generata una soluzione vicina applicando una piccola modifica casuale (una 'mossa') alla soluzione corrente. La struttura del vicinato deve essere adattata al problema: per un problema di pianificazione una mossa potrebbe scambiare due attività; per una funzione continua potrebbe aggiungere una piccola perturbazione casuale al vettore dei parametri corrente.

3

Viene calcolata la differenza nel valore obiettivo tra la nuova soluzione e quella corrente. Se la nuova soluzione è migliore, viene sempre accettata. Se è peggiore, viene accettata con una probabilità che decade con l'entità del peggioramento e la temperatura corrente — tipicamente exp(−ΔE / T). Questa accettazione probabilistica è il meccanismo centrale che previene la convergenza prematura.

4

Dopo ogni iterazione (o dopo un numero fisso di mosse alla stessa temperatura), la temperatura viene ridotta secondo un programma di raffreddamento — comunemente un programma geometrico T ← α·T dove α è leggermente inferiore a 1. La scelta del programma di raffreddamento influisce fortemente sulla qualità della soluzione: raffreddare troppo velocemente intrappola la ricerca in un minimo locale; raffreddare troppo lentamente spreca tempo computazionale.

5

L'algoritmo si ferma quando la temperatura scende al di sotto di una soglia minima, viene raggiunto un numero massimo di iterazioni, o la soluzione non è migliorata per un numero specificato di passi. Viene restituita come risultato la migliore soluzione incontrata durante l'intera esecuzione — non solo lo stato finale.

Errori comuni

  • Eseguire troppo poche iterazioni (circa meno di 1 000) impedisce al programma di raffreddamento di funzionare correttamente e lascia la ricerca intrappolata in un minimo locale — preferire la ricerca tabù o una ricerca locale deterministica se il tempo di esecuzione è severamente limitato.
  • Impostare la temperatura iniziale troppo bassa significa che l'algoritmo si comporta immediatamente come un hill-climbing goloso e perde la sua capacità di sfuggire ai minimi locali.
  • Impostare il tasso di raffreddamento troppo aggressivamente (ad esempio, α inferiore a 0.9) causa convergenza prematura; verificare la qualità della soluzione finale riavviando da più soluzioni iniziali.
  • Applicare una mossa di vicinato progettata per un tipo di problema a un problema diverso può rendere le mosse inammissibili o prive di significato — verificare sempre che ogni vicino generato sia una soluzione valida.
  • Riportare solo lo stato finale anziché la migliore soluzione mai vista durante l'esecuzione può far perdere l'ottimo vero trovato in uno stadio intermedio.

Domande frequenti

Come scelgo il programma di raffreddamento?

Il programma geometrico T ← α·T con α tra 0.90 e 0.99 è il punto di partenza più comune. Un approccio pratico è impostare la temperatura iniziale abbastanza alta da accettare circa l'80% delle mosse all'inizio, poi ridurla finché meno dell'1% delle mosse in salita non vengono accettate. Se la qualità della soluzione finale è scarsa, rallentare il tasso di raffreddamento (aumentare α); se il tempo di esecuzione è troppo lungo, accelerarlo. Eseguire sempre l'algoritmo più volte da diverse soluzioni iniziali per valutarne la robustezza.

In che modo il raffreddamento similato differisce dagli algoritmi genetici o dall'ottimizzazione per sciami di particelle?

Il raffreddamento similato mantiene una singola soluzione ed esplora il vicinato attraverso perturbazioni casuali, accettando peggiori soluzioni probabilisticamente. Gli algoritmi genetici e l'ottimizzazione per sciami di particelle mantengono una popolazione di soluzioni e utilizzano crossover, mutazione o movimento dello sciame per far evolvere la popolazione. Il raffreddamento similato è generalmente più semplice da implementare per problemi con una struttura di vicinato naturale, mentre i metodi basati sulla popolazione possono essere più efficaci per problemi continui ad alta dimensionalità.

È garantito l'ottimo globale?

Teoricamente sì, a condizione che la temperatura diminuisca sufficientemente lentamente (raffreddamento logaritmico). In pratica, un tale raffreddamento è computazionalmente infattibile, quindi l'algoritmo trova una soluzione quasi ottimale. La qualità del risultato migliora con un raffreddamento più lento e più iterazioni, ma non vi è alcuna garanzia in tempo finito. Eseguire riavvii multipli e mantenere la migliore soluzione trovata è un modo pratico per aumentare la fiducia.

Quando dovrei preferire la ricerca tabù o un algoritmo genetico invece?

Scegliere la ricerca tabù quando si necessita di una ricerca deterministica guidata dalla memoria che eviti di rivisitare soluzioni recenti e possa sfruttare efficientemente la struttura del problema in un tempo di esecuzione più breve. Scegliere un algoritmo genetico o un'ottimizzazione per sciami di particelle quando il problema è ad alta dimensionalità e continuo, o quando è necessaria una popolazione di soluzioni diverse per mappare il paesaggio dell'ottimo. Il raffreddamento similato è una forte opzione predefinita per problemi combinatori con una chiara struttura di vicinato e quando la semplicità di implementazione è importante.

Metodi correlati

Fonti

  1. Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.

    Apri il riferimento DOI
    Copiato.
  2. van Laarhoven, P.J.M. & Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications. Springer.

    ISBN: 9789027725431
    Copiato.