Bayesian Tabu Search — Probabilistic guidance integrated with memory-based local search
Also known as: BTS, Bayesian-guided tabu search, probabilistic tabu search, Bayes-TS
Bayesian Tabu Search (BTS) is a hybrid metaheuristic that couples the memory-based forbidden-move mechanism of classic Tabu Search with a Bayesian probabilistic model. The Bayesian component learns from past evaluations to score candidate moves, focusing the search on promising regions while the tabu list prevents cycling. This combination reduces wasted function evaluations in expensive combinatorial and continuous optimization problems.
Key highlights
- Reduces the number of expensive true function evaluations by using the surrogate model to pre-screen candidates.
- Inherits tabu search's ability to escape local optima through memory-based move prohibition.
- Bayesian model improves over iterations, making later search steps increasingly informed.
- Naturally incorporates domain knowledge through informative priors on solution quality.
- Applicable to both combinatorial (discrete) and continuous optimization landscapes.
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
When to use it
Use Bayesian Tabu Search when the objective function is expensive to evaluate (e.g., requires simulation, physical experiment, or complex computation) and when historical or prior information about the search space can inform a surrogate model. It excels in combinatorial scheduling, hyperparameter tuning, and engineering design where function evaluations are the bottleneck. Avoid it when the objective function is cheap to evaluate thousands of times — plain Tabu Search or full-grid methods will be faster and simpler. Also avoid when no meaningful prior or past run data exists and when the search space is so small that exhaustive search is feasible.
Strengths & limitations
- Reduces the number of expensive true function evaluations by using the surrogate model to pre-screen candidates.
- Inherits tabu search's ability to escape local optima through memory-based move prohibition.
- Bayesian model improves over iterations, making later search steps increasingly informed.
- Naturally incorporates domain knowledge through informative priors on solution quality.
- Applicable to both combinatorial (discrete) and continuous optimization landscapes.
- Surrogate model fitting adds computational overhead per iteration, which may outweigh savings if evaluations are cheap.
- Performance depends heavily on the choice of surrogate model, kernel, and acquisition function — requires tuning.
- Tabu list length and tenure parameters must still be set, and poor choices can trap or over-restrict the search.
- Bayesian model accuracy degrades in very high-dimensional spaces without sufficient observations.
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
How is Bayesian Tabu Search different from plain Bayesian Optimization?
Plain Bayesian Optimization (BO) uses a surrogate and acquisition function to propose the single best next point, then evaluates it. Bayesian Tabu Search generates a neighborhood of candidates, scores them with the surrogate, but also enforces a tabu list to prevent cycling — making it better suited to discrete and combinatorial spaces where BO's continuous relaxation is awkward.
What surrogate model should I use?
Gaussian Processes work well for low-dimensional continuous problems and provide calibrated uncertainty estimates. Tree-structured Parzen Estimators (TPE) handle mixed discrete-continuous spaces and scale better. Random Forest surrogates are another option for purely categorical spaces.
How do I set the tabu tenure in this hybrid?
A common starting point is a tenure between 5 and 15 moves, or sqrt(n) where n is the number of decision variables. Because the Bayesian model helps avoid revisits probabilistically, shorter tenures are sometimes sufficient compared to plain tabu search.
Does Bayesian Tabu Search guarantee finding the global optimum?
No. Like all metaheuristics, it provides no global optimality guarantee. The Bayesian component improves the probability of finding high-quality solutions within a limited evaluation budget, but convergence to the true global optimum is not assured.
When should I prefer standard Tabu Search over the Bayesian variant?
When objective function evaluations are cheap (microseconds to milliseconds), the overhead of fitting and querying a surrogate model is not justified. Standard Tabu Search will explore far more neighbors in the same wall-clock time.
Sources
- 1.Glover, F. (1989). Tabu search — Part I. ORSA Journal on Computing, 1(3), 190–206.
- 2.Bergstra, J., Bardenet, R., Bengio, Y., Kegl, B. (2011). Algorithms for hyper-parameter optimization. Advances in Neural Information Processing Systems (NIPS), 24, 2546–2554.
You have read it. What now?
Cite this page
ScholarGate. (2026, June 3). Bayesian Tabu Search. ScholarGate. https://scholargate.app/simulation/bayesian-tabu-search