Agent-Based Tabu Search — Distributed Multi-Agent Metaheuristic Optimization
- Introduced by
- Glover, F. (tabu search); multi-agent extension by various researchers in the 1990s–2000s
- Year
- 1989–1995
- Type
- Hybrid metaheuristic — agent-based distributed tabu search
- Family
- Simulation / optimization
What does it do?
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.
The intuition behind the method
Classic tabu search can get stuck exploring a narrow region even with its short-term memory mechanism. By deploying multiple autonomous agents, each maintaining its own tabu list and neighborhood, the search fans out across diverse starting points. Agents periodically share elite solutions (intensification) and deliberately scatter to unexplored regions (diversification). This cooperative yet independent structure mirrors biological swarm behavior — no single agent has the full picture, yet the collective finds high-quality solutions much faster than any individual searcher.
History
Tabu search was formalized by Fred Glover in 1986–1989. Distributed and parallel variants emerged in the early 1990s as researchers sought to exploit multi-processor architectures. Verhoeven and Aarts (1995) provided a systematic study of parallel local search including cooperative tabu strategies. The agent-based framing became prominent in the 2000s as agent-based modeling vocabulary entered operations research.
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.
Limitations and considerations
- 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.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- 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.
Applications
- Vehicle routing and logistics: coordinating multiple agents each optimizing route sub-problems.
- Job-shop and flexible manufacturing scheduling: agents handle machine subsets cooperatively.
- Telecommunications network design: distributed channel assignment and topology optimization.
- Supply chain planning: multi-echelon inventory and distribution optimization.
- Protein structure prediction: parallel neighborhood search over conformational spaces.
- Academic timetabling and course scheduling with distributed department-level agents.
How it works
How it works
Define a population of autonomous agents. Each agent is assigned a role: some focus on intensification (deep local search around promising regions), others on diversification (escaping to unexplored areas). Each agent maintains its own tabu list of forbidden moves, a current solution, and a neighborhood structure tailored to the problem type (e.g., swap, insertion, or 2-opt moves for combinatorial problems).
Initialize agents with distinct starting solutions, either randomly generated or seeded via a constructive heuristic (e.g., nearest-neighbor for routing). Diversity among starting solutions is crucial — identical starts lead to redundant parallel searches. Evaluate the objective function for each initial solution and record the global best solution across all agents.
Each agent executes its own tabu search loop: generate the neighborhood of the current solution, evaluate all (or a subset of) neighbor solutions, select the best non-tabu neighbor as the next move (aspiration criterion allows overriding the tabu list if the candidate surpasses the global best), and update the tabu list by adding the reverse move with a tenure drawn from a fixed or adaptive range.
Agents communicate at defined synchronization intervals or event triggers. Common strategies include broadcasting the current global best to all agents (who may restart from it), injecting the elite solution into a shared pool that agents periodically consult, or peer-to-peer exchange of solutions between neighboring agents in a topology (ring, fully connected, or random). Diversity controls prevent premature convergence by penalizing agents with identical solutions.
Terminate when a maximum iteration budget, wall-clock time limit, or stagnation criterion is met (e.g., no improvement in the global best for a given number of iterations). Select the globally best solution found across all agents across all iterations as the final output. Optionally report a Pareto front if multiple objectives are tracked.
Common pitfalls
- Setting all agents to identical starting solutions wastes parallel capacity — ensure diverse initialization.
- Over-frequent communication forces agents into the same solution basin, eliminating diversification benefits and effectively reducing the search to one thread.
- Ignoring the aspiration criterion in the tabu list design can cause agents to miss obviously better solutions, particularly in the early search phase.
- Applying ABTS to problems where neighborhood evaluation is extremely costly without a surrogate model will result in prohibitive runtimes.
Frequently asked questions
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.
Related methods
Sources
Glover, F. (1989). Tabu search — Part I. ORSA Journal on Computing, 1(3), 190–206.
Open DOI referenceCopied.Verhoeven, M. G. A., Aarts, E. H. L. (1995). Parallel local search. Journal of Heuristics, 1(1), 43–65.
Open DOI referenceCopied.