Overview
Tabu search uses a memory list to avoid cycling back to recent solutions, allowing the search to escape shallow local optima.
ExtendedSource checked
Tabu Search
Improves solutions with local moves while forbidding recently visited moves or states.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Intermediate
- Family
- Local Search
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
neighborhood movetabu listaspiration rulelocal optimum
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(neighborhood)
Average
O(iterations * neighborhood)
Worst
O(iterations * neighborhood)
Space
O(tabu tenure)
When to Use
- Use when tuning model parameters needs neighborhood move.
- Use when the input matches the assumptions behind local Search.
When Not to Use
- Avoid when the objective is cheap and convex enough for a simpler exact solver.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Improves solutions with local moves while forbidding recently visited moves or states
- Uses neighborhood move and tabu list to guide the work.
- Produces best candidate.
Use Cases
- Tuning model parameters
- Searching design spaces
- Fitting models to noisy data
Inputs
- Objective function
- Initial candidate or population
- Stopping rule
Outputs
- Best candidate
- Objective value
- Search history
Key Formulas (1)
Move choice
next = argmin allowedneighbor objective(neighbor)
next = argmin allowed_neighbor objective(neighbor)Chooses the best non-tabu move, unless an aspiration rule overrides it.
Pseudocode
- 1.Prepare the inputs and state needed for Tabu Search.
- 2.Apply the neighborhood move step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return best candidate.
Canonical Example
- Input
- Tabu Search input with a small representative case
- Output
- Best candidate
- Explanation
- Tabu Search applies neighborhood move to produce best candidate.
Implementation Notes
- Track both best-so-far and current candidate state.
- Keep the neighborhood move step separate enough to test independently.
Common Pitfalls
- Stopping too early can make a poor local result look like convergence.
- Forgetting to check edge cases can make Tabu Search look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryPlot candidate points, objective values, and improvement steps across iterations.
Step 1 of 4: Prepare the inputs and state needed for Tabu Search.
optimization-mechanismNotes
Tabu Search should be used with the assumptions and tradeoffs of local Search in mind.
Sources (1)
What each reference supports for this entry.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageImproves onHill Climbing
Tabu search adds memory to avoid immediately revisiting poor local moves.
Alternative toSimulated Annealing
Both attempt to improve local search on rugged objective landscapes.
Related Algorithms
Tags
OptimizationLocal SearchMetaheuristicHeuristic