Tabu search
|
|
Tabu search is a mathematical optimization method, belonging to the class of local search techniques. Tabu search enhances the performance of a local search method by using memory structures. Tabu search is generally attributed to Fred Glover.
Tabu search uses a local or neighbourhood search procedure to iteratively move from a solution <math>x<math> to a solution <math>x'<math> in the neighbourhood of <math>x<math>, until some stopping criterion has been satisfied. To explore regions of the search space that would be left unexplored by the local search procedure and---by doing this---escape local optimality, tabu search modifies the neighbourhood structure of each solution as the search progresses. The solutions admitted to <math>N^*(x)<math>, the new neighbourhood, are determined through the use of special memory structures. The search now progresses by iteratively moving from a solution <math>x<math> to a solution <math>x'<math> in <math>N^*(x)<math>.
Perhaps the most important type of short-term memory to determine the solutions in <math>N^*(x)<math>, also the one that gives its name to tabu search, is the use of a tabu list. In its simplest form, a tabu list contains the solutions that have been visited in the recent past (less than <math>n<math> moves ago, where <math>n<math> is the tabu tenure). Solutions in the tabu list are excluded from <math>N^*(x)<math>. Other tabu list structures prohibit solutions that have certain attributes (e.g. traveling salesman problem (TSP) solutions that include certain arcs) or prevent certain moves (e.g. an arc that was added to a TSP tour cannot be removed in the next <math>n<math> moves). Selected attributes in solutions recently visited are labelled tabu-active. Solutions that contain tabu-active elements are tabu. This type of short-term memory is also called recency-based memory.
Tabu lists containing attributes are much more effective, although they raise a new problem. With forbidding an attribute as tabu, typically more than one solution is declared as tabu. Some of these solutions that must now be avoided might be of excellent quality and have not yet been visited. To overcome this problem, aspiration criteria are introduced which allow to override the tabu state of a solution and thus include it in the allowed set. A commonly used aspiration criterion is to allow solutions which are better than the currently best known solution.