Does tabu search always improve at each step?

No. It may accept deterioration to explore beyond a local optimum.

The duration of a temporary restriction, measured according to the implementation's policy, often in iterations.

Can a tabu move still be selected?

Yes, if an applicable aspiration criterion overrides the restriction.

AI Glossary / Graphs and symbolic AI / Intermediate

Tabu search

Definition

Tabu search is an optimization method that guides local search using memory of earlier moves or solution features. It temporarily restricts selected moves, called tabu moves, to discourage unproductive repetition and help explore beyond a local optimum. It can deliberately accept a worse current solution while retaining the best solution found. The method is a flexible metaheuristic, not a guarantee of global optimality.

What it means

A local search changes one candidate solution into a nearby one. If it accepts only improvements, it may stop where every immediate neighbor is worse, even though a much better solution exists elsewhere. Simply allowing worse moves can create another problem: repeatedly moving back and forth between the same candidates.

Tabu search uses remembered information to influence which moves are admissible. The memory often records move attributes rather than complete solutions. A restriction lasts for a specified tenure or follows an adaptive policy. The current candidate, the best candidate seen, and the memory are separate parts of the search state.

How it works

Choose an initial solution, an objective, and a neighborhood of allowed changes. Evaluate candidate moves and select a suitable admissible one, often the best available even if it worsens the current objective.

After moving, update tabu information so that selected reversals or repeated attributes are temporarily restricted. An aspiration criterion can override a restriction when a move is especially valuable, such as improving the best objective found so far. Specify how ties, empty admissible neighborhoods, and stopping conditions are handled.

Longer-term memory can support intensification around promising features or diversification toward less explored regions. These are design choices rather than one universal recipe. The neighborhood and evaluation cost often matter as much as tenure. Maintain the best feasible solution separately, because the final current position may be worse than an earlier discovery.

Three practical examples

1. Scheduling: swap jobs or move a job to another allowed position, while temporarily discouraging reversals that recreate recently explored schedules.

2. Routing: modify a route through defined exchanges and remember selected removed or added connections to guide further exploration.

3. Graph coloring: change vertex colors to reduce conflicts while using memory to avoid immediately undoing selected changes. The exact penalty and feasibility policy must be stated.

Think of it this way

Think of exploring a maze with notes about recently used turns. You may walk temporarily away from the apparent destination to escape a dead end, while the notes discourage immediately retracing the same unhelpful route.

The analogy is limited because tabu search uses a numerical objective and precisely defined move attributes. It does not simply ban every place visited, and its memory policy may allow a previously visited solution to become useful in a different search context.

Worked example

Consider four candidate solutions with objective values to minimize: A costs 10, B costs 12, C costs 8, and D costs 6. The allowed undirected neighbor links are exactly A - B, B - C, and C - D, forming the chain A - B - C - D. Start at A.

A descent-only method stops immediately because its only neighbor B costs 12. For this toy tabu search, choose the lowest-cost admissible neighbor and forbid reversing the most recent move for the next selection. Keep the best solution found separately.

First move A→B, accepting deterioration from 10 to 12. A remains the best-so-far solution. At B, the reversal to A is temporarily tabu; C is admissible and costs 8, so move B→C and update the best to C. At C, the reversal to B is tabu and D is admissible, so move C→D and update the best to D, cost 6. Stop after these three moves.

The trace demonstrates escape from a local optimum and prevention of immediate reversal. It does not demonstrate a general optimality guarantee. For a separate aspiration example, if an attribute-based restriction blocks a candidate costing 5 while the best-so-far cost is 6, a specified “improves best” aspiration rule can admit it despite that restriction.

Illustrative case study

Fictional case: ShiftCraft experiments with a scheduling optimizer. Its baseline repeatedly reverses job swaps after accepting a worse schedule. The team adds a short memory of swap attributes and records both current and best-feasible costs.

On small instances, reviewers inspect whether restrictions encourage exploration or block too many useful moves. They compare tenure settings under equal evaluation budgets and verify feasibility independently. The case illustrates an evaluation process; it does not report real scheduling improvements or establish a universally suitable tenure.

Common misconceptions and mistakes

“Tabu” does not mean permanently forbidden. Restrictions normally expire or can be overridden according to explicit criteria.

The method does not have to store every full solution. Attribute-based memory can be smaller, but may also restrict moves leading to previously unseen solutions.

Accepting a worse move is not an error by itself. Confusing the current solution with the best-so-far solution is an error when reporting results.

A successful run does not prove global optimality. Randomization is optional, and comparing methods requires a fair computational budget, meaningful instances, and clear stopping rules.

Business use

Tabu search is relevant to difficult allocation and configuration problems where useful feasible solutions are needed within a limited budget. Its memory mechanisms can be tailored to the structure of the decisions being changed.

Define hard constraints separately from penalties and specify whether intermediate infeasible solutions are allowed. Record objective values, feasibility, evaluation counts, and the best solution over time. For decisions that need a proven bound or optimum, use a method that supplies that evidence or combine heuristic search with appropriate exact analysis. A low reported cost is meaningful only when the solution satisfies the intended requirements.

Check your understanding

Why is A still the best-so-far solution immediately after moving to B?

Answer: A costs 10 and B costs 12. The current solution changed, but no better solution had yet been found.

Related terms

Local search
Neighborhood
Simulated annealing
metaheuristic
aspiration criterion
intensification
diversification
combinatorial optimisation

Learn next

Study neighborhood design next. Redraw the four-state trace and distinguish current cost, best cost, and forbidden reversal at every step. Then add another neighbor to B and predict how the selected move changes under the stated admissibility and tie-breaking rules.

Neighborhood

Sources

Primary reference: Glover, Laguna, and Martí, “Principles of Tabu Search,” https://leeds-faculty.colorado.edu/glover/TS%20-%20Principles%20of%20Tabu%20Search%20-%20Glover,%20Laguna%20and%20Marti.pdf. The authors' memory and local-search discussion was read. The four-state trace and fictional case are original illustrations, not computational experiments.

Previous: Tabled logic programming Next: Tabular data