tabu search
In plain wordsA search method that improves an answer by small changes while keeping a short memory of recent moves and forbidding their reversal for a while, so it does not circle back to the same dead ends.
A metaheuristicmetaheuristic, n.: A general-purpose strategy for finding good answers to hard problems, such as imitating evolution or cooling metal, that can be adapted to many different problems instead of being designed for just one. that equips local searchlocal search, n.: A family of problem-solving methods that start with some complete answer, however poor, and keep improving it by small changes, instead of building an answer piece by piece from scratch. with a memory of its recent history, steering it away from moves and solutions it has just tried. At each step it moves to the best admissible neighbor of the current solution, even if that neighbor is worse, which lets it climb out of local optima; to prevent cycling, recently made moves or recently visited solution attributes are declared tabu (forbidden) for a number of iterations, recorded in a short-term tabu list. Aspiration criteria lift the ban when a tabu move would yield the best solution found so far, and longer-term memory supports intensification (searching near good solutions) and diversification (pushing the search into unexplored regions). Tabu search has been especially successful on scheduling, vehicle routing, graph coloring and other problems in operations research.
Origin
Introduced by Fred Glover in a 1986 paper in Computers and Operations Research, the same paper in which he coined the word 'metaheuristic'. Pierre Hansen independently proposed a similar 'steepest ascent, mildest descent' method around the same time.
Related
- local searchlocal search, n.: A family of problem-solving methods that start with some complete answer, however poor, and keep improving it by small changes, instead of building an answer piece by piece from scratch.
- metaheuristicmetaheuristic, n.: A general-purpose strategy for finding good answers to hard problems, such as imitating evolution or cooling metal, that can be adapted to many different problems instead of being designed for just one.
- hill climbinghill climbing, n.: A simple search method that keeps making whichever small change improves things, like climbing in fog by always stepping uphill — which can leave it stuck on a small hill instead of the highest peak.
- simulated annealingsimulated annealing, n.: An optimization method inspired by slowly cooling metal: early on it sometimes accepts worse solutions, to escape dead ends, and becomes pickier as a 'temperature' setting gradually drops.
- constraint satisfaction problemconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes.
Sources
- Glover, F. (1986). Future Paths for Integer Programming and Links to Artificial Intelligence. Computers & Operations Research 13(5), 533–549.
Mentioned in
hill climbinghill climbing, n.: A simple search method that keeps making whichever small change improves things, like climbing in fog by always stepping uphill — which can leave it stuck on a small hill instead of the highest peak., simulated annealingsimulated annealing, n.: An optimization method inspired by slowly cooling metal: early on it sometimes accepts worse solutions, to escape dead ends, and becomes pickier as a 'temperature' setting gradually drops., local searchlocal search, n.: A family of problem-solving methods that start with some complete answer, however poor, and keep improving it by small changes, instead of building an answer piece by piece from scratch., metaheuristicmetaheuristic, n.: A general-purpose strategy for finding good answers to hard problems, such as imitating evolution or cooling metal, that can be adapted to many different problems instead of being designed for just one.