Skip to content
Torna ai risultati

Ricerca Tabù — Metaeuristica di Ricerca Locale

Introdotto da
Fred Glover
Anno
1989
Tipo
Local-search metaheuristic

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

Dimensione del carattere

A cosa serve?

La Ricerca Tabù è una metaeuristica di ricerca locale introdotta da Fred Glover nel 1989 che utilizza una lista tabù — una memoria a breve termine di soluzioni visitate di recente — per prevenire il ciclaggio e sfuggire agli ottimi locali.

Vietando esplicitamente le mosse che invertono decisioni recenti, l'algoritmo esplora lo spazio di ricerca più ampiamente e, attraverso strutture di memoria a lungo termine come i criteri di aspirazione, mira ad avvicinarsi all'ottimo globale anche in problemi combinatori di grandi dimensioni e complessi.

L’intuizione alla base del metodo

Immagina di navigare un paesaggio montuoso al buio, cercando di trovare la vetta più alta. Un semplice cercatore locale sale sempre in salita e si blocca sulla collina più vicina che raggiunge. La Ricerca Tabù porta con sé un taccuino di luoghi visitati di recente e si rifiuta di tornarci, anche se tornare indietro sembrerebbe allettante. Questa amnesia forzata sulle mosse recenti spinge la ricerca fuori dai vicoli ciechi e verso territori inesplorati, permettendole di scoprire infine un terreno molto più elevato di quanto una semplice ricerca locale potrebbe mai fare.

Storia

La Ricerca Tabù è stata introdotta da Fred Glover in un articolo fondamentale del 1989 sul ORSA Journal on Computing, dove è stata presentata come una strategia per guidare la ricerca locale sfruttando la memoria delle mosse passate. Le idee fondamentali sono state consolidate ed estese nella monografia di Glover e Laguna del 1997 pubblicata da Springer, che ha stabilito la lista tabù canonica a breve termine, i criteri di aspirazione e le strategie di diversificazione e intensificazione a lungo termine che rimangono centrali per il metodo oggi. Dalla sua introduzione, la Ricerca Tabù è stata ampiamente applicata nella ricerca operativa, nella pianificazione, nella logistica e nella progettazione combinatoria, e continua ad essere una metaeuristica di riferimento standard accanto al simulated annealing e agli algoritmi genetici.

Quando usarlo

La Ricerca Tabù è ben adatta a problemi di ottimizzazione combinatoria e discreta in cui lo spazio delle soluzioni è troppo vasto per metodi esatti e la struttura del problema consente la definizione di un vicinato significativo. Le applicazioni tipiche includono problemi di pianificazione, instradamento, assegnazione e sequenziamento. È particolarmente efficace quando il paesaggio di ricerca presenta molti ottimi locali che intrappolano metodi più semplici. Non richiede che la funzione obiettivo sia differenziabile o continua. La definizione del vicinato e la durata tabù devono essere adattate attentamente al problema specifico; un vicinato scelto male o una durata troppo breve o troppo lunga possono degradare significativamente le prestazioni. Sono necessarie almeno diverse centinaia — e idealmente più di mille — iterazioni affinché la ricerca esplori adeguatamente lo spazio.

Limiti e considerazioni

  • Le prestazioni sono sensibili alla definizione del vicinato e alla durata tabù; scelte errate possono intrappolare la ricerca o farla ciclare nonostante il meccanismo tabù.
  • Richiede un budget di iterazioni minimo — tipicamente più di 1.000 iterazioni — per esplorare sufficientemente il vicinato; con troppo poche iterazioni i risultati non sono migliori di una semplice ricerca locale.
  • La lista tabù memorizza attributi di mossa piuttosto che soluzioni complete, quindi il criterio di aspirazione è necessario per evitare di bloccare inavvertitamente mosse genuinamente buone.
  • A differenza dei risolutori esatti, la Ricerca Tabù non offre garanzie di ottimalità e la qualità del risultato può variare tra le esecuzioni se la soluzione iniziale o il vicinato sono stocastici.

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

Punti di forza

  • Sfugge agli ottimi locali tramite il meccanismo tabù senza richiedere informazioni sul gradiente.
  • Applicabile a problemi combinatori, misti e persino continui — non assume normalità o alcuna proprietà distributiva.
  • Incorpora memoria a più scale temporali (lista tabù a breve termine, diversificazione/intensificazione a lungo termine) consentendo un'esplorazione basata su principi dello spazio di ricerca.
  • Trova spesso soluzioni di alta qualità con budget computazionali relativamente modesti rispetto ai metodi esatti su istanze di grandi dimensioni.

Applicazioni

  • Pianificazione job-shop e flow-shop — ottimizzazione della sequenza delle operazioni per minimizzare il makespan o la tardività.
  • Routing dei veicoli — ricerca di percorsi di consegna efficienti soggetti a vincoli di capacità e finestre temporali.
  • Assegnazione e localizzazione di impianti — assegnazione di compiti a risorse o localizzazione di impianti per minimizzare i costi.
  • Colorazione di grafi, progettazione di reti e telecomunicazioni — risoluzione di problemi di ottimizzazione strutturale discreta.
  • Selezione di caratteristiche e ricerca di iperparametri — esplorazione di spazi di configurazione discreti nelle pipeline di machine learning.

Come funziona

Come funziona

1

La ricerca inizia da una soluzione candidata iniziale, che può essere costruita casualmente o con una euristica golosa. La lista tabù viene impostata come una coda vuota di lunghezza fissa e viene registrata la migliore soluzione trovata finora. La struttura del vicinato — la regola che definisce quali soluzioni sono a un passo dalla soluzione corrente — deve essere definita in modo significativo per il problema specifico.

2

Dalla soluzione corrente, vengono generate e valutate tutte le mosse nel vicinato definito rispetto alla funzione obiettivo. Ogni mossa corrisponde a una piccola perturbazione, come lo scambio di due elementi in una sequenza o l'inversione di una variabile binaria. Il vicinato deve essere sufficientemente ricco da consentire un'esplorazione significativa ma sufficientemente piccolo da essere trattabile all'interno di ogni iterazione.

3

Ogni mossa candidata viene testata rispetto alla lista tabù. Se la mossa — o l'attributo che la caratterizza — appare nella lista, viene classificata come tabù ed è vietata, a meno che non soddisfi un criterio di aspirazione: tipicamente, se la soluzione risultante fosse migliore della migliore soluzione trovata finora, lo stato tabù viene sovrascritto e la mossa è permessa. Questo meccanismo di aspirazione conferisce flessibilità all'algoritmo senza abbandonare la sua disciplina anti-ciclaggio.

4

Tra tutte le mosse non tabù (e qualsiasi mossa tabù che superi il criterio di aspirazione), viene selezionata ed eseguita la mossa con le migliori prestazioni, anche se peggiora il valore obiettivo. Questa volontà di accettare il peggioramento è ciò che consente all'algoritmo di sfuggire agli ottimi locali, che è il tratto distintivo della Ricerca Tabù rispetto al semplice hill climbing.

5

Dopo che la mossa è stata eseguita, la lista tabù viene aggiornata aggiungendo l'inverso della mossa appena effettuata (o il suo attributo caratterizzante), e la voce più vecchia viene rimossa se la lista è piena, mantenendo la sua lunghezza fissa — la durata tabù. Se la nuova soluzione è migliore della migliore soluzione registrata, la migliore soluzione viene aggiornata. Strutture opzionali di memoria a lungo termine possono tracciare la frequenza o la recenza delle soluzioni per guidare la diversificazione verso regioni meno visitate o l'intensificazione attorno a quelle promettenti.

6

L'algoritmo continua a iterare fino a quando non viene soddisfatto un criterio di arresto: un numero massimo di iterazioni, un valore obiettivo target o un conteggio fisso di iterazioni senza miglioramenti. La migliore soluzione trovata durante l'intera ricerca viene restituita come risultato. La scelta di un budget di iterazioni adeguato è fondamentale: troppo poche iterazioni impediscono un'esplorazione sufficiente del vicinato.

Errori comuni

  • Impostare la durata tabù troppo breve consente il ripetersi del ciclaggio, vanificando lo scopo del meccanismo tabù; la durata dovrebbe essere calibrata in base alla dimensione del problema.
  • Impostare la durata troppo lunga sovra-restringe la ricerca e impedisce all'algoritmo di rivisitare regioni che potrebbero contenere miglioramenti.
  • Eseguire meno di circa 1.000 iterazioni significa che la ricerca non ha esplorato abbastanza del vicinato — se il calcolo è limitato, ripiegare sul simulated annealing che può produrre risultati utili più velocemente con meno iterazioni.
  • Utilizzare un vicinato troppo ristretto (ad esempio, solo mosse di singolo scambio su una struttura complessa) porta a una ricerca superficiale; assicurarsi che il vicinato sia sufficientemente ricco da connettere tutte le regioni promettenti dello spazio delle soluzioni.
  • Ignorare il criterio di aspirazione può bloccare permanentemente le mosse verso l'ottimo globale se quella mossa dovesse essere tabù; implementare sempre almeno la sovrascrittura standard della migliore soluzione.

Domande frequenti

In cosa differisce la Ricerca Tabù dal simulated annealing?

Entrambi i metodi accettano mosse peggiorative per sfuggire agli ottimi locali, ma differiscono nel meccanismo. Il simulated annealing accetta mosse peggiori probabilisticamente, guidato da un parametro di temperatura di raffreddamento. La Ricerca Tabù accetta la migliore mossa non tabù disponibile deterministicamente, guidata dalla memoria esplicita delle mosse recenti. La Ricerca Tabù è generalmente più efficace su problemi combinatori strutturati; il simulated annealing può essere più facile da calibrare su problemi con paesaggi continui o quasi continui ed è preferibile quando il budget di iterazioni è piccolo (inferiore a circa 1.000 iterazioni).

Quanto dovrebbe essere lunga la lista tabù?

La durata tabù — il numero di iterazioni per cui una mossa rimane proibita — dipende dal problema. Un punto di partenza comunemente citato è una durata proporzionale alla radice quadrata della dimensione del problema, ma questa dovrebbe essere calibrata empiricamente. Una durata troppo breve consente il ciclaggio; una durata troppo lunga sovra-restringe la ricerca. Strategie di durata adattive o randomizzate possono ridurre la sensibilità a questa scelta.

La Ricerca Tabù garantisce di trovare l'ottimo globale?

No. La Ricerca Tabù è una metaeuristica e non fornisce garanzie di ottimalità. Mira a trovare soluzioni di alta qualità in modo efficiente, ma il risultato dipende dalla struttura del vicinato, dalla durata, dal numero di iterazioni e dalla soluzione iniziale. Per una garanzia di ottimalità, è necessario un metodo esatto come la programmazione intera, sebbene i metodi esatti possano essere computazionalmente infattibili per istanze di grandi dimensioni.

Cos'è un criterio di aspirazione e perché è necessario?

Un criterio di aspirazione è una regola che sovrascrive lo stato tabù di una mossa in condizioni speciali. Il criterio più comune è: se l'esecuzione di una mossa tabù producesse una soluzione migliore della migliore soluzione trovata finora, la restrizione tabù viene revocata e la mossa è permessa. Senza questa sovrascrittura, il meccanismo tabù potrebbe bloccare permanentemente il percorso verso l'ottimo globale se quel percorso passasse attraverso una mossa visitata di recente.

Metodi correlati

Fonti

  1. Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    Apri il riferimento della pubblicazione
    Copiato.
  2. Glover, F. & Laguna, M. (1997). Tabu Search. Springer.

    ISBN: 9780792349907
    Copiato.