Tabu search
Da Wikipedia, l'enciclopedia libera.
Il Tabu Search è una tecnica meta-euristica utilizzata in numerosi problemi di ottimizzazione, tra cui problemi di scheduling e routing, problemi su grafi, programmazione intera, ecc.
Indice |
[modifica] Principi di funzionamento
Il Tabu Search rappresenta una evoluzione del classico "metodo di discesa", 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 del "vicinato" (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 e` spesso ben lontano, soprattutto in termini di qualita`, dalla soluzione ottima globale.
La tecnica del Tabu Search venne proposta da Fred Glover proprio per ovviare a questo problema. Innanzitutto, per poter sfuggire alla "trappola" dei minimi locali, il Tabu Search consente "mosse peggioranti". Tuttavia, cosi` 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 del 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 del Tabu Search è quindi il sistematico utilizzo della memoria, nel senso che, 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.
[modifica] Cenni storici
Nella sua forma attuale, il Tabu Search è stato proposto da Fred Glover. Le idee fondamentali erano state abbozzate qualche anno prima da P. Hansen. I numerosi esperimenti computazionali effettuati dimostrano che il 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, il Tabu Search è stato indicato dal Committee on the Next Decade of Operations Research come tecnica estremamente promettente per il trattamento futuro di applicazioni pratiche. Tuttora non è nota alcuna dimostrazione formale della sua convergenza. Recentemente sono stati studiati alcuni aspetti teorici del Tabu Search. In particolare, U. Faigle e W. Kern hanno proposto una versione probabilistica del Tabu Search che converge quasi sicuramente ad un ottimo globale.
[modifica] Riferimenti bibliografici
- 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.
