Tabu search
Encyclopedia
Tabu search is a mathematical optimization
method, belonging to the class of trajectory based techniques. Tabu search enhances the performance of a local search
method by using memory structures that describe the visited solutions: once a potential solution has been determined, it is marked as "taboo
" ("tabu" being a different spelling of the same word) so that the algorithm
does not visit that possibility repeatedly. Tabu search is attributed to Fred W. Glover
.
algorithm that can be used for solving combinatorial optimization
problems, such as the traveling salesman problem (TSP). Tabu search uses a local or neighborhood
search procedure to iteratively move from a solution
to a solution 
in the neighborhood of 
, until some stopping criterion has been satisfied. To explore regions of the search space
that would be left unexplored by the local search procedure (see local optimality), tabu search modifies the neighborhood structure of each solution as the search progresses. The solutions admitted to
, the new neighborhood, are determined through the use of memory structures. The search then progresses by iteratively moving from a solution 
to a solution 
in 
.
Perhaps the most important type of memory structure used to determine the solutions admitted to
is the tabu list. In its simplest form, a tabu list is a short-term memory which contains the solutions that have been visited in the recent past (less than 
iterations ago, where 
is the number of previous solutions to be stored (
is also called the tabu tenure)). Tabu search excludes solutions in the tabu list from 
. A variation of a tabu list prohibits solutions that have certain attributes (e.g., solutions to the traveling salesman problem (TSP) which include undesirable arcs) or prevent certain moves (e.g. an arc that was added to a TSP tour cannot be removed in the next 
moves). Selected attributes in solutions recently visited are labeled "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 can be more effective for some domains, although they raise a new problem. When a single attribute is marked as tabu, this typically results in more than one solution being tabu. Some of these solutions that must now be avoided could be of excellent quality and might not have been visited. To mitigate this problem, "aspiration criteria" are introduced: these override a solution's tabu state, thereby including the otherwise-excluded solution in the allowed set. A commonly used aspiration criterion is to allow solutions which are better than the currently-known best solution.
, heuristic-based approximation methods are useful for approaching optimality.
Tabu search can be used to find a satisficing
solution for the TSP. First, tabu search starts with an initial solution, which can be generated according to the nearest neighbor algorithm. To create new solutions, the order that two cities are visited is swapped. The distance for the total travel between all the cities is used to judge how good one solution is over another. To prevent cycles and to get out of local optima, a solution is added to the tabu list if it is accepted into
, the solution neighborhood. New solutions continue to be created until some stopping criteria, such as an arbitrary number of iterations, is met. Once tabu search stops, the best solution is the solution with the shortest distance for the total travel between all cities.
Other local search methods include:
Other metaheuristic
methods include:
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
method, belonging to the class of trajectory based techniques. Tabu search enhances the performance of a local search
Local search (optimization)
In computer science, local search is a metaheuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions...
method by using memory structures that describe the visited solutions: once a potential solution has been determined, it is marked as "taboo
Taboo
A taboo is a strong social prohibition relating to any area of human activity or social custom that is sacred and or forbidden based on moral judgment, religious beliefs and or scientific consensus. Breaking the taboo is usually considered objectionable or abhorrent by society...
" ("tabu" being a different spelling of the same word) so that the algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
does not visit that possibility repeatedly. Tabu search is attributed to Fred W. Glover
Fred W. Glover
Fred W. Glover is a professor of computer science at the University of Colorado, and the Chief Technology Officer at OptTek. He is best known as the inventor of the tabu search method, and coined the term "metaheuristic".. Fred Glover was born on March 8, 1937 in Kansas City,...
.
Basic details
Tabu search is a metaheuristicMetaheuristic
In computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Metaheuristics make few or no assumptions about the problem being optimized and can search very large spaces...
algorithm that can be used for solving combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
problems, such as the traveling salesman problem (TSP). Tabu search uses a local or neighborhood
Local search (optimization)
In computer science, local search is a metaheuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions...
search procedure to iteratively move from a solution
to a solution in the neighborhood of , until some stopping criterion has been satisfied. To explore regions of the search spaceSearch space
Search space may refer to one of the following.*In optimization, the domain of the function to be optimized*In search algorithms of computer science, the set of all possible solutions...
that would be left unexplored by the local search procedure (see local optimality), tabu search modifies the neighborhood structure of each solution as the search progresses. The solutions admitted to
, the new neighborhood, are determined through the use of memory structures. The search then progresses by iteratively moving from a solution to a solution in .Perhaps the most important type of memory structure used to determine the solutions admitted to
is the tabu list. In its simplest form, a tabu list is a short-term memory which contains the solutions that have been visited in the recent past (less than iterations ago, where is the number of previous solutions to be stored ( is also called the tabu tenure)). Tabu search excludes solutions in the tabu list from . A variation of a tabu list prohibits solutions that have certain attributes (e.g., solutions to the traveling salesman problem (TSP) which include undesirable arcs) or prevent certain moves (e.g. an arc that was added to a TSP tour cannot be removed in the next moves). Selected attributes in solutions recently visited are labeled "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 can be more effective for some domains, although they raise a new problem. When a single attribute is marked as tabu, this typically results in more than one solution being tabu. Some of these solutions that must now be avoided could be of excellent quality and might not have been visited. To mitigate this problem, "aspiration criteria" are introduced: these override a solution's tabu state, thereby including the otherwise-excluded solution in the allowed set. A commonly used aspiration criterion is to allow solutions which are better than the currently-known best solution.
Example: Traveling salesman problem
The traveling salesman problem (TSP) is often used to show the functionality of tabu search. The TSP involves finding an ordering of travel between cities, such that the distance traveled is minimized. For example, if city A and city B are next to each other, while city C is further away, the total distance traveled will be shorter if cities A and B are visited one after the other, before visiting city C. Since finding an optimal order of visiting cities in the TSP is NP-hardNP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
, heuristic-based approximation methods are useful for approaching optimality.
Tabu search can be used to find a satisficing
Satisficing
Satisficing, a portmanteau "combining satisfy with suffice", is a decision-making strategy that attempts to meet criteria for adequacy, rather than to identify an optimal solution...
solution for the TSP. First, tabu search starts with an initial solution, which can be generated according to the nearest neighbor algorithm. To create new solutions, the order that two cities are visited is swapped. The distance for the total travel between all the cities is used to judge how good one solution is over another. To prevent cycles and to get out of local optima, a solution is added to the tabu list if it is accepted into
, the solution neighborhood. New solutions continue to be created until some stopping criteria, such as an arbitrary number of iterations, is met. Once tabu search stops, the best solution is the solution with the shortest distance for the total travel between all cities.Related methods
Tabu search is a sub-field of:- Local searchLocal search (optimization)In computer science, local search is a metaheuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions...
- MetaheuristicMetaheuristicIn computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Metaheuristics make few or no assumptions about the problem being optimized and can search very large spaces...
s- Stochastic optimizationStochastic optimizationStochastic optimization methods are optimization methods that generate and use random variables. For stochastic problems, the random variables appear in the formulation of the optimization problem itself, which involve random objective functions or random constraints, for example. Stochastic...
- OptimizationOptimization (mathematics)In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
- Optimization
- Stochastic optimization
- Metaheuristic
Other local search methods include:
- Reactive search optimizationReactive search optimizationReactive search optimization defines local-search heuristics based on machine learning, a family of optimization algorithms based on the local search techniques...
- Hill climbingHill climbingIn computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by incrementally changing a single element of the solution...
- Guided Local SearchGuided Local SearchGuided Local Search is a metaheuristic search method. A meta-heuristic method is a method that sits on top of a local search algorithm to change its behaviour....
- GRASP, or greedy randomized adaptive search procedureGreedy randomized adaptive search procedureThe greedy randomized adaptive search procedure is a metaheuristic algorithm commonly applied to combinatorial optimization problems. GRASP typically consists of iterations made up from successive constructions of a greedy randomized solution and subsequent iterative improvements of it through a...
Other metaheuristic
Metaheuristic
In computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Metaheuristics make few or no assumptions about the problem being optimized and can search very large spaces...
methods include:
- Simulated annealingSimulated annealingSimulated annealing is a generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete...
- Evolutionary computing