This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)
Tabu Search, like simulated annealing, is a neighbourhood search. You will
recall that this means we find the next possible state from the set of neighbourhood
states and then we decide if to move to that state.
Tabu search, like hill climbing considers the set of all possible neighbourhood
states and takes the best one. Unlike hill climbing it will take the best move
in the neighbourhood, even though it might be worse than the current move. And,
unlike simulated annealing, we are likely to move away from a good solution
in search of others.
Therefore, with a tabu search it is normal to remember the best move seen during the complete search and return that as the best solution. In fact, most searches will do this anyway as the benefits far outweigh the disadvantages.
The main principle behind tabu search is that it has some memory of the states that is has already investigated and it does not re-visit those states. It is like you searching for a bar in a town you have never been to before. If you recognised you had already been to a particular street you would not search that area again.
Not re-visiting previously visited states helps in two ways. It avoids the search getting into a loop by continually searching the same area without actually making any progress. In turn, this helps the search explore regions that it might not otherwise explore.
The moves that are not allowed to be re-visited are held in a data structure (usually a list) and these moves are called "tabu" (thus the name).
For those of you who are interested (Glover 1989 and Glover 1990) are two of the first tabu search references.
| Previous Page | Index Page | Next Page |
Last Updated : 25/01/2002