Editing Tabu search (section)

{{Short description|Local search algorithm}}'''Tabu search''' (TS) is a [[metaheuristic]] search method employing [[Local search (optimization)|local search]] methods used for [[optimization (mathematics)|mathematical optimization]]. It was created by [[Fred W. Glover]] in 1986<ref name="glover86">{{cite journal | author = Fred Glover | year = 1986 | title = Future Paths for Integer Programming and Links to Artificial Intelligence | journal = Computers and Operations Research  | volume = 13 | issue = 5 | pages = 533–549 | doi=10.1016/0305-0548(86)90048-1 }}
</ref> and formalized in 1989.<ref name="glover89">{{cite journal|author=Fred Glover|year=1989|title=Tabu Search – Part 1|journal=ORSA Journal on Computing|volume=1|issue=2|pages=190–206|doi=10.1287/ijoc.1.3.190}}
</ref><ref name="glover90">{{cite journal|author=Fred Glover|year=1990|title=Tabu Search – Part 2|journal=ORSA Journal on Computing|volume=2|issue=1|pages=4–32|doi=10.1287/ijoc.2.1.4}}
</ref> 

Local (neighborhood) searches take a potential solution to a problem and check its immediate neighbors (that is, solutions that are similar except for very few minor details) 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 (like when the search is stuck at a strict [[local minimum]]). 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.<ref name="glover89"/> 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 "[[taboo|tabu]]" (forbidden) so that the [[algorithm]] does not consider that possibility repeatedly.