Artificial Intelligence/Search/Heuristic search/Tabu Search

Tabu Search

Tabu was first conceived of by Fred Glover while observing his graduate classmates trying to emulate problem solving on computers in the early 1960s (Glover 1998). During this time he noticed that his colleagues did not use formal logic for problem solving themselves but would instead whittle down the problem space by avoiding previously tried steps if they proved unpromising (Glover 1998). The name Tabu comes from the word taboo which adequately describes the above phenomena. Tabu is a heuristic search algorithm used to solve combinatorial optimization problems, where a set of discrete feasible solutions is the problem space and the goal is to find the best possible solution (Glover 1989). In other words, it is a metaheuristic that aids local search heuristics to reach optimal performance while searching for a solution. One of Tabu’s uniquenesses is attributed to its flexible memory system, as opposed to other search methods that have a fixed or no memory system (Glover 1990). It also utilizes a strategy of constraining and freeing the search (i.e. the tabu component).

How it works: Tabu restrictions are employed to prevent the search from getting stuck in locally optimal solutions (Glover 1990). These constraints are set-up so that Tabu will not make repetitious moves. For instance, if two moves located near each other are considered ‘best’, then the search may bounce between the two indefinitely (Glover 1990). These repetitious moves, therefore, are marked as ‘tabu’ and will not be returned to while in the surrounding search space (Glover 1990). The ultimate goal of tabu restrictions then is to break out of local search space while maintaining the possibility of finding an optimal solution (Glover 1990). To do this, aspiration criteria are employed to counterbalance the effect of tabu restrictions and allow the search to extend into a greater search field (Glover 1990). Solutions that are marked ‘tabu’ can have their ‘tabu’ status removed after search has left the previously troublesome local optimum. This way, those solutions will still be considered as a possibility for finding the global optimal solution (Glover 1990).

Illustration: The following shows the general Tabu process in a flowchart.

References

Glover, Fred. (1990). Tabu search: A tutorial, Special Issue on the Practice of Mathematical Programming, Interfaces, 20, 74-94.

Glover, Fred. (1998). Tabu search – Wellsprings and challenges. European Journal of Operational Research, 106, 221-225.

Glover, Fred. (1989). Tabu search – Part I. ORSA Journal on Computing, 1, 190-206.