Editing Tabu search (section)

==Basic description==

Tabu search uses a [[local search (optimization)|local or neighborhood]] search procedure to iteratively move from one potential solution <math>x</math> to an improved solution <math>x'</math> in the neighborhood of <math>x</math>, until some stopping criterion has been satisfied (generally, an attempt limit or a score threshold). 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 [[Energy function|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, <math>N^*(x)</math>, are determined through the use of memory structures. Using these memory structures, the search progresses by iteratively moving from the current solution <math>x</math> to an improved solution <math>x'</math> in <math>N^*(x)</math>. 

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.

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 <math>N^*(x)</math> 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 (less than <math>n</math> iterations ago, where <math>n</math>  is the number of previous solutions to be stored —  is also called the tabu tenure). 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.