Tabu search
Tabu search, created by Fred W. Glover in 1986 and formalized in 1989, is a metaheuristic search method employing local search methods used for mathematical optimization.
Local searches take a potential solution to a problem and check its immediate neighbors in the hope of finding an improved solution. Local search methods have a tendency to become stuck in suboptimal regions or on plateaus where many solutions are equally fit.
Tabu search enhances the performance of local search by relaxing its basic rule. First, at each step worsening moves can be accepted if no improving move is available. In addition, prohibitions are introduced to discourage the search from coming back to previously-visited solutions.
The implementation of tabu search uses memory structures that describe the visited solutions or user-provided sets of rules. If a potential solution has been previously visited within a certain short-term period or if it has violated a rule, it is marked as "tabu" so that the algorithm does not consider that possibility repeatedly.
Background
The word tabu comes from the Tongan word to indicate things that cannot be touched because they are sacred.Tabu search is a metaheuristic algorithm that can be used for solving combinatorial optimization problems.
Current applications of TS span the areas of resource planning, telecommunications, VLSI design, financial analysis, scheduling, space planning, energy distribution, molecular engineering, logistics, pattern classification, flexible manufacturing, waste management, mineral exploration, biomedical analysis, environmental conservation and scores of others. In recent years, journals in a wide variety of fields have published tutorial articles and computational studies documenting successes by tabu search in extending the frontier of problems that can be handled effectively — yielding solutions whose quality often significantly surpasses that obtained by methods previously applied. A comprehensive list of applications, including summary descriptions of gains achieved from practical implementations, can be found in Recent TS developments and applications can also be found in .
Basic description
Tabu search uses a local or neighborhood search procedure to iteratively move from one potential solution to an improved solution in the neighborhood of, until some stopping criterion has been satisfied. Local search procedures often become stuck in poor-scoring areas or areas where scores plateau. In order to avoid these pitfalls and explore regions of the search space that would be left unexplored by other local search procedures, tabu search carefully explores the neighborhood of each solution as the search progresses. The solutions admitted to the new neighborhood,, are determined through the use of memory structures. Using these memory structures, the search progresses by iteratively moving from the current solution to an improved solution in.Tabu Search has several similarities with Simulated annealing, as both involve possible down hills moves. In fact, Simulated annealing could be viewed as a special form of TS, where by we use "graduated tenure", that is, a move becomes tabu with a specified probability.
These memory structures form what is known as the tabu list, a set of rules and banned solutions used to filter which solutions will be admitted to the neighborhood to be explored by the search. In its simplest form, a tabu list is a short-term set of the solutions that have been visited in the recent past. More commonly, a tabu list consists of solutions that have changed by the process of moving from one solution to another. It is convenient, for ease of description, to understand a “solution” to be coded and represented by such attributes.
Types of memory
The memory structures used in tabu search can roughly be divided into three categories:- Short-term: The list of solutions recently considered. If a potential solution appears on the tabu list, it cannot be revisited until it reaches an expiration point.
- Intermediate-term: Intensification rules intended to bias the search towards promising areas of the search space.
- Long-term: Diversification rules that drive the search into new regions.
Short-term memory alone may be enough to achieve solutions superior to those found by conventional local search methods, but intermediate and long-term structures are often necessary for solving harder problems. Tabu search is often benchmarked against other metaheuristic methods — such as Simulated annealing, genetic algorithms, Ant colony optimization algorithms, Reactive search optimization, Guided Local Search, or greedy randomized adaptive search. In addition, tabu search is sometimes combined with other metaheuristics to create hybrid methods. The most common tabu search hybrid arises by joining TS with Scatter Search, a class of population-based procedures which has roots in common with tabu search, and is often employed in solving large non-linear optimization problems.
Pseudocode
The following pseudocode presents a simplified version of the tabu search algorithm as described above. This implementation has a rudimentary short-term memory, but contains no intermediate or long-term memory structures. The term "fitness" refers to an evaluation of the candidate solution, as embodied in an objective function for mathematical optimization.sBest ← s0
bestCandidate ← s0
tabuList ←
tabuList.push
while )
sNeighborhood ← getNeighbors
bestCandidate ← sNeighborhood
for
if > fitness) )
bestCandidate ← sCandidate
end
end
if > fitness)
sBest ← bestCandidate
end
tabuList.push
if
tabuList.removeFirst
end
end
return sBest
Lines 1-4 represent some initial setup, respectively creating an initial solution, setting that initial solution as the best seen to date, and initializing a tabu list with this initial solution. In this example, the tabu list is simply a short term memory structure that will contain a record of the elements of the states visited.
The core algorithmic loop starts in line 5. This loop will continue searching for an optimal solution until a user-specified stopping condition is met. The neighboring solutions are checked for tabu elements in line 8. Additionally, the algorithm keeps track of the best solution in the neighbourhood, that is not tabu.
The fitness function is generally a mathematical function, which returns a score or the aspiration criteria are satisfied — for example, an aspiration criterion could be considered as a new search space is found). If the best local candidate has a higher fitness value than the current best, it is set as the new best. The local best candidate is always added to the tabu list and if the tabu list is full, some elements will be allowed to expire. Generally, elements expire from the list in the same order they are added. The procedure will select the best local candidate in order to escape the local optimal.
This process continues until the user specified stopping criterion is met, at which point, the best solution seen during the search process is returned.
Example: the traveling salesman problem
The traveling salesman problem is sometimes used to show the functionality of tabu search. This problem poses a straightforward question — given a list of cities, what is the shortest route that visits every city? For example, if city A and city B are next to each other, while city C is farther 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 solution is NP-hard, heuristic-based approximation methods are useful for devising close-to-optimal solutions. To obtain good TSP solutions, it is essential to exploit the graph structure. The value of exploiting problem structure is a recurring theme in metaheuristic methods, and tabu search is well-suited to this. A class of strategies associated with tabu search called ejection chain methods has made it possible to obtain high-quality TSP solutions efficientlyOn the other hand, a simple tabu search can be used to find a satisficing solution for the traveling salesman problem. The search starts with an initial solution, which can be generated randomly or according to some sort of nearest neighbor algorithm. To create new solutions, the order that two cities are visited in a potential solution is swapped. The total traveling distance between all the cities is used to judge how ideal one solution is compared to another. To prevent cycles – i.e., repeatedly visiting a particular set of solutions – and to avoid becoming stuck in local optima, a solution is added to the tabu list if it is accepted into the solution neighborhood,.
New solutions are created until some stopping criterion, such as an arbitrary number of iterations, is met. Once the simple tabu search stops, it returns the best solution found during its execution.