Agent-Based Tabu Search — Distributed Multi-Agent Metaheuristic Optimization
Also known as: ABTS, Multi-Agent Tabu Search, Distributed Tabu Search, Cooperative Tabu Search
Agent-Based Tabu Search (ABTS) embeds the tabu search metaheuristic inside a multi-agent framework where autonomous agents each run independent or cooperating tabu search threads, sharing promising solutions to escape local optima and collectively explore large combinatorial or continuous search spaces more effectively than a single-thread implementation.
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 Agent-Based Tabu Search when solving hard combinatorial or mixed-integer optimization problems (scheduling, routing, network design, resource allocation) where single-thread tabu search stagnates and parallel computation resources are available. It is particularly effective when the search landscape has many local optima of similar quality. Avoid it when the problem is small enough for exact solvers (MILP, branch-and-bound), when a single evaluation is computationally prohibitive (making many parallel evaluations infeasible), or when reproducibility requirements conflict with the non-deterministic, agent-interaction dynamics.
Strengths & limitations
- Parallel exploration significantly reduces time-to-solution on large combinatorial problems compared to single-thread tabu search.
- The multi-agent framework naturally supports diversification, reducing the risk of premature convergence to poor local optima.
- Flexible architecture allows heterogeneous agents with different neighborhood structures, tabu tenure strategies, or even mixed metaheuristics.
- Cooperative solution sharing transfers discoveries across agents, accelerating intensification around high-quality regions.
- Scales well with available computational cores, making it suitable for modern multi-core and distributed computing environments.
- Synchronization overhead and communication cost between agents can negate parallelism gains on tightly coupled systems or slow networks.
- More hyperparameters than single-thread tabu search: number of agents, communication topology, synchronization frequency, and diversification triggers all require tuning.
- Theoretical convergence guarantees are weaker than exact methods; solution quality depends heavily on tuning and problem structure.
- Reproducibility is difficult to achieve because agent interactions introduce additional stochasticity beyond the random initialization.
Frequently asked
How is Agent-Based Tabu Search different from simply running multiple tabu search threads?
The key difference is cooperation. In independent parallel runs, threads never share information. In ABTS, agents actively exchange solutions, update a shared elite pool, or adopt diversification triggers based on collective state — producing emergent search behavior absent from independent runs.
How many agents should I use?
A common starting point is one agent per available CPU core. Research suggests diminishing returns beyond 8–16 agents for most combinatorial problems, as communication overhead grows. Pilot experiments with 4, 8, and 16 agents help identify the sweet spot for a given problem.
Can ABTS handle multi-objective problems?
Yes. Agents can maintain local approximations of a Pareto front and share non-dominated solutions via a shared archive. This is sometimes called Multi-Objective Agent-Based Tabu Search and is distinct from standard single-objective ABTS.
What communication topology is best?
Fully connected topologies spread good solutions fastest but create high communication cost. Ring or small-world topologies balance information diffusion with autonomy. For most practical problems, a ring or random sparse topology works well as a default.
When should I prefer a genetic algorithm or particle swarm over ABTS?
Prefer population-based methods (GA, PSO) when the problem has a continuous, smooth landscape or when crossover/recombination operators are well-defined. ABTS excels on discrete, combinatorial problems with well-defined neighborhood operators where tabu memory provides a strong search advantage.
Sources
- Glover, F. (1989). Tabu search — Part I. ORSA Journal on Computing, 1(3), 190–206. DOI: 10.1287/ijoc.1.3.190 ↗
- Verhoeven, M. G. A., Aarts, E. H. L. (1995). Parallel local search. Journal of Heuristics, 1(1), 43–65. DOI: 10.1007/bf02430365 ↗
How to cite this page
ScholarGate. (2026, June 3). Agent-Based Tabu Search — Distributed Multi-Agent Metaheuristic Optimization. ScholarGate. https://scholargate.app/en/simulation/agent-based-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.
- Agent-based genetic algorithmSimulation↔ compare
- Agent-Based ModelingSimulation↔ compare
- Multi-objective Tabu SearchSimulation↔ compare
- Tabu SearchOptimization↔ compare