Stochastic Tabu Search — Randomized Metaheuristic with Memory
Stochastic Tabu Search — Randomized metaheuristic optimization with tabu memory · Also known as: STS, Randomized Tabu Search, Probabilistic Tabu Search, Noisy Tabu Search
Stochastic Tabu Search (STS) is an extension of classical Tabu Search that introduces randomness into the neighborhood exploration and move-selection phases. By combining tabu memory — which forbids recently visited solutions — with probabilistic acceptance or random candidate sampling, STS escapes local optima more effectively and explores rugged solution landscapes that deterministic TS may fail to traverse.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Use Stochastic Tabu Search when solving combinatorial or continuous black-box optimization problems with rugged, multimodal landscapes where deterministic local search consistently gets trapped (e.g., scheduling, routing, feature selection). It is especially valuable when full neighborhood evaluation is computationally expensive, making random subsampling necessary. Do NOT use STS when the problem is convex or unimodal — gradient-based or exact methods are faster and optimal. Avoid it when you need guaranteed global optimality, since STS offers no convergence guarantee beyond heuristic best-found solutions. Also avoid when the objective function is cheap to evaluate completely and a deterministic TS with exhaustive neighbor search is feasible.
Strengths & limitations
- Escapes local optima more effectively than deterministic Tabu Search by combining memory with probabilistic exploration.
- Scales to large neighborhood structures by subsampling candidates, reducing per-iteration computational cost.
- Tabu memory prevents cycling, a common failure mode of pure stochastic methods like random restart hill climbing.
- Flexible framework: perturbation probability and tabu tenure can be tuned to balance intensification and diversification.
- Applicable to both combinatorial problems (TSP, scheduling) and continuous optimization with minor adaptation.
- No theoretical guarantee of finding the global optimum; solution quality depends heavily on parameter settings.
- Tabu tenure and candidate list size require problem-specific tuning; poor choices lead to premature convergence or slow progress.
- Stochastic runs are non-reproducible without a fixed random seed, complicating benchmarking and auditing.
- Memory overhead grows with tabu list size; attribute-based tabu representations are needed for large solution spaces.
Frequently asked
How does Stochastic Tabu Search differ from Simulated Annealing?
Both are stochastic metaheuristics, but STS uses an explicit tabu memory to forbid recently visited moves, preventing cycling. SA has no memory — it accepts worse solutions with a probability that decreases over time (temperature schedule). STS is generally stronger on combinatorial problems where revisiting moves is a clear danger.
How many iterations (I_max) should I run?
There is no universal rule. A common practice is to run multiple independent trials (e.g., 10-30 restarts) with a budget proportional to problem size, then report the best and average outcomes. For benchmarking, match the total function-evaluation budget used by competing methods.
Can Stochastic Tabu Search handle continuous variables?
Yes, but it requires defining a continuous neighborhood (e.g., Gaussian perturbation around the current solution) and a suitable attribute for the tabu list (e.g., a region or direction). Most STS literature targets combinatorial problems; for continuous spaces, Differential Evolution or CMA-ES are often more natural alternatives.
What is the role of aspiration criteria?
Aspiration criteria override the tabu status of a move if accepting it yields a solution better than the best found so far. Without aspiration, the algorithm might permanently reject globally improving moves that happen to be tabu, severely limiting solution quality.
Should I fix the random seed for reproducibility?
Yes, fix the seed when reporting results in research to ensure reproducibility. In practice, run with multiple seeds and report statistics (mean, best, standard deviation) to give a reliable picture of algorithm performance across the stochastic landscape.
Sources
- Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94. DOI: 10.1287/inte.20.4.74 ↗
- Hu, J., Fu, M. C., & Marcus, S. I. (2007). A model reference adaptive search method for global optimization. Operations Research, 55(3), 549-568. DOI: 10.1287/opre.1060.0367 ↗
How to cite this page
ScholarGate. (2026, June 3). Stochastic Tabu Search — Randomized metaheuristic optimization with tabu memory. ScholarGate. https://scholargate.app/en/simulation/stochastic-tabu-search
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Genetic AlgorithmOptimization↔ compare
- Particle Swarm OptimizationOptimization↔ compare
- Simulated AnnealingOptimization↔ compare
- Stochastic Genetic AlgorithmSimulation↔ compare
- Tabu SearchOptimization↔ compare