Tabu search
Local search methods have a tendency to become stuck in suboptimal regions or on plateaus where many solutions are equally fit.
In addition, prohibitions (hence the term tabu) 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.
[2] 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" (forbidden) so that the algorithm does not consider that possibility repeatedly.
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 [5] Tabu search uses a local or neighborhood search procedure to iteratively move from one potential solution
Tabu search has several similarities with simulated annealing, as both involve possible downhill moves.
In fact, simulated annealing could be viewed as a special form of TS, whereby we use "graduated tenure", that is, a move becomes tabu with a specified probability.
In its simplest form, a tabu list is a short-term set of the solutions that have been visited in the recent past (less than
In short-term memory, selected attributes in solutions recently visited are labelled "tabu-active."
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.
The following pseudocode presents a simplified version of the tabu search algorithm as described above.
The term "fitness" refers to an evaluation of the candidate solution, as embodied in an objective function for mathematical optimization.
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 traveling salesman problem (TSP) is sometimes used to show the functionality of tabu search.
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 efficiently [10] On the other hand, a simple tabu search can be used to find a satisficing solution for the traveling salesman problem (that is, a solution that satisfies an adequacy criterion, although not with the high quality obtained by exploiting the graph structure).
The search starts with an initial solution, which can be generated randomly or according to some sort of nearest neighbor algorithm.
