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. In mathematics, the term optimization refers to the study of problems that have the form Given: a function f : A R from some set A to the real numbers Sought: an element x0 in A such that f(x0) ≤ f(x) for all x in A (minimization) or such that... Local search is a metaheuristic for solving computationally hard optimization problems. ...

Tabu search uses a local or neighbourhood search procedure to iteratively move from a solution x to a solution x' in the neighbourhood of x, 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 N ^* (x), the new neighbourhood, are determined through the use of special memory structures. The search now progresses by iteratively moving from a solution x to a solution x' in N ^* (x). Local optimum is a term in applied mathematics and computer science. ...

Perhaps the most important type of short-term memory to determine the solutions in N ^* (x), 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 n moves ago, where n is the tabu tenure). Solutions in the tabu list are excluded from N ^* (x). 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 n 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. The traveling salesman problem (TSP), is a problem in discrete or combinatorial optimization. ...

Tabu lists containing attributes are much more effective, although they raise a new problem. When a single attribute is forbidden as tabu, typically more than one solution ends up being tabu. Some of these solutions that must now be avoided might be of excellent quality and might not have been visited. To overcome this problem, aspiration criteria are introduced which allow overriding the tabu state of a solution to include it in the allowed set. A commonly used aspiration criterion is to allow solutions which are better than the currently best known solution.

Related methods

Simulated annealing is a related global optimization technique which traverses the search space by generating neighbouring solutions of the current solution. A superior neighbour is always accepted. An inferior neighbour is accepted probabilistically based on the difference in quality and a temperature parameter. The temperature parameter is modified as the algorithm progresses to alter the nature of the search. Simulated annealing (SA) is a generic probabilistic meta-algorithm for the global optimization problem, namely locating a good approximation to the global optimum of a given function in a large search space. ...

Genetic algorithms maintain a pool of solutions rather than just one. The process of finding superior solutions mimics that of evolution, with solutions being combined or mutated to alter the pool of solutions, with solutions of inferior quality being discarded. A genetic algorithm (GA) is an algorithm used to find approximate solutions to difficult-to-solve problems through application of the principles of evolutionary biology to computer science. ...

Ant colony optimization uses many artificial ants (or agents) that incrementally build solutions. Artificial ants deposit artificial pheromones (to this ant-inspired behavior is due their name) that are used by later ants to guide their search. Ant colony optimization is particularly useful for problems where no global or up-to-date perspective can be obtained, and thus the other methods cannot be applied. The ant colony optimization algorithm (ACO), introduced by Moyson and Manderick [MoMa88] and widely developped by Marco Dorigo [CMD91,Dor92,DoSt04], is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. ...

Particle swarm optimization maintains a population of solutions rather than a single solution. This algorithm is based on simplified model of social behavior. Here each particle can be thought of as a state of mind. This model simulates how our beliefs and attitudes are influenced by other humans: evaluation, comparison and imitation. Every particle improves its fitness using its experience and its companions' experience, and particles finally reach a, possibly local, optimum. Particle swarm optimization (PSO) is a form of swarm intelligence. ...

The Cross-entropy method generates candidates solutions via a parameterized probability distribution. The parameters are updated via cross-entropy minimization, so as to generate better samples in the next iteration. The cross-entropy (CE) method attributed to Reuven Rubinstein is a general Monte Carlo approach to combinatorial and continuous multi-extremal optimization and importance sampling. ...

Basics: Short term memory -recency based tabu list

Long term memory -frequency based tabu list

-Aspiration criteria

Is basically a single solution, deterministic neighborhood search Technique that uses memory (a “tabu list”) to prohibit certain moves, even if they are improving. This makes tabu search a global optimizer rather than a local optimizer.

Bibliography

• 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.