Tabu search

La Tabu Search (o ricerca tabù) è una tecnica meta-euristica utilizzata per la soluzione di numerosi problemi di ottimizzazione, tra cui problemi di scheduling e routing, problemi su grafi e programmazione intera.

Principi di funzionamento

La Tabu Search rappresenta un'evoluzione del classico "metodo di discesa" (i.e. "steepest descent" o della massima pendenza, anche noto come metodo del gradiente) ossia, utilizzato per trovare il minimo di una funzione reale f su un insieme S (spazio delle soluzioni). Tale metodologia classica consiste nel partire da una soluzione iniziale ed eseguire una serie di "mosse" che portano ad una nuova soluzione all'interno dell'intorno (o insieme di adiacenza) della soluzione corrente, nella quale la funzione obiettivo f assume un valore minore del valore attuale. Il difetto del metodo di discesa sta nel fatto che, se nell'insieme di adiacenza non esistono soluzioni "migliori" di quella corrente, la ricerca si arresta. La soluzione ottima individuata dal metodo di discesa risulta quindi associata ad un minimo locale dello spazio delle soluzioni, il quale è spesso ben lontano, soprattutto in termini di qualità, dalla soluzione ottima globale.

La tecnica della Tabu Search venne proposta da Fred Glover come modo per continuare la ricerca oltre i minimi locali. Innanzitutto, per poter sfuggire alla "trappola" dei minimi locali, la Tabu Search consente "mosse peggioranti". Tuttavia, così facendo, si rischia di ricadere subito dopo nel minimo locale, a meno che non si impediscano in qualche modo le mosse recentemente eseguite. Il concetto fondamentale della Tabu Search consiste allora nel rendere "proibite" o, appunto, "tabu", le ultime mosse eseguite nel cammino di ricerca, in modo che l'algoritmo non possa tornare sui suoi passi e ricadere nel minimo locale. Caratteristica basilare della Tabu Search è quindi l'uso sistematico della memoria: per aumentare l'efficacia del processo di ricerca, viene tenuta traccia non solo delle informazioni locali (come il valore corrente della funzione obiettivo), ma anche di alcune informazioni relative all'itinerario percorso. Tali informazioni vengono impiegate per guidare la mossa dalla soluzione corrente alla soluzione successiva, da scegliersi all'interno dell'insieme di adiacenza.

Storia

Nella sua forma attuale, la Tabu Search è stata proposta da Fred W. Glover. Idee simili erano state abbozzate in contemporanea anche da P. Hansen, mentre il concetto fondamentale di usare proibizioni per incoraggiare una diversificazione della ricerca appare in vari lavori precedenti, ad esempio nell'algoritmo di Kernighan–Lin per il partizionamento dei grafi.

I numerosi esperimenti computazionali effettuati dimostrano che la Tabu Search è ormai una tecnica di ottimizzazione affermata, che può competere con quasi tutti i metodi noti, e che grazie alla sua flessibilità, può battere molte delle procedure classiche di ottimizzazione. Insieme al simulated annealing e agli algoritmi genetici, la Tabu Search è stata indicata dal Committee on the Next Decade of Operations Research come tecnica estremamente promettente per il trattamento futuro di applicazioni pratiche. La dimostrazione formale della convergenza asintotica nella Tabu Search può essere ottenuta tramite modifiche stocastiche. Recentemente U. Faigle e W. Kern hanno proposto una versione probabilistica della Tabu Search che converge quasi sicuramente ad un ottimo globale. Tali risultati teorici, sebbene interessanti, sono piuttosto irrilevanti per le applicazioni pratiche. L'obiettivo della Tabu Search, come di altre tecniche euristiche, è di trovare rapidamente soluzioni buone per problemi che spesso non permettono di determinare soluzioni ottimali in tempi ragionevoli (ad esempio problemi NP-ardui).

Bibliografia

• Glover, F. and M. Laguna. (1997). Tabu Search. Kluwer, Norwell, MA.
• Glover, F. "Tabu Search — Part I", ORSA Journal on Computing 1989 1: 3, 190-206.
• Glover, F. "Tabu Search — Part II", ORSA Journal on Computing 1990 2: 1, 4-32.
• Cvijovic, D.; Klinowski, J. "Taboo search - an approach to the multiple minima problem". Science 1995 267, 664-666.
• Greco Francesca; A HYBRID GREEDY RANDOMIZED ADAPTIVE SEARCH HEURISTIC TO SOLVE THE DIAL-A-RIDE PROBLEM. , Research Gate, 2008.

Collegamenti esterni

• (EN) An Introduction to Tabu Search, su ifi.uio.no.
• (EN) The Reactive Search Website, su reactive-search.org. URL consultato il 10 agosto 2006 (archiviato dall'url originale il 2 giugno 2010).
• (EN) LION Conference on Learning and Intelligent Optimization techniques, su intelligent-optimization.org. URL consultato il 22 dicembre 2010 (archiviato dall'url originale l'8 novembre 2010).
• (EN) The Reactive Search Company website - A software company that implements these techniques, su reactive-search.com. URL consultato il 10 gennaio 2010 (archiviato dall'url originale il 3 settembre 2011).
• (EN) Roberto Battiti, Mauro Brunato and Franco Mascia Reactive Search and Intelligent Optimization, su reactive-search.org. URL consultato il 22 dicembre 2010 (archiviato dall'url originale il 16 marzo 2012).