Catalogue of Artificial Intelligence Techniques
Keywords: local, optimization, search, tabu
Author(s): Kyle Patullo
Tabu search is a mathematical optimization method which enhances the performance of a local search method. Unlike methods such as genetic algorithms and simulated annealing, tabu search requires the use of a memory structure during the exploration of a solution. It takes an intelligent approach to problem solving by incorporating adaptive memory and responsive exploration.
Tabu search uses the iterative process of a local search method to move from one solution to another within some search space. One of the essential ideas of tabu search is the use of a tabu list. In it's simplest form, the tabu list contains a list of solutions that have been visited recently (at least the previous few steps). The tabu search method excludes any solutions which are contained in this list and avoids re-exploration of some parts of the search space.
More advanced memory structures and attributes which improve the solution exclusion process can also be used. The method has been shown to be more effective than methods which use a semi-random process to reach their goal, in problems such as combinatorial optimization.
- Glover, F. and M. Laguna , Tabu Search, Kluwer Academic Publishers, Boston, 1997.