Home / Curated / Algorithms / Tabu search

Tabu search

Algorithms AIMech:TabuSearch DRAFT

Aliases: TS

A memory-guided optimization framework that steers a search trajectory by making selected moves temporarily inadmissible from search history, allowing non-improving moves and, where specified, aspiration-based overrides.

Identity Notes & Concept Scope This record denotes the tabu-search framework through the original Part I formulation. It is not merely a list of visited nodes, Ant System’s per-tour feasibility list, or a global best-first frontier. Recency restrictions, aspiration and longer-term memory are configurable mechanisms; no single fixed tenure or exact prohibition rule defines all variants. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 301 preceding native IDs/names/aliases. Full-checkout fixed-string searches included ignored and hidden files in worktree and main, returning 37 and 37 lines respectively. All 13 unique hit contents were inspected: prior local-search candidate leads, Ant System’s feasibility-list distinction, and their saved reports/reviews. These were references to methods rather than existing candidate records. Six exact AIO CLASS nodes with scoped synonyms/comments and outgoing edges and seven native neighboring mechanisms were inspected. Absence is bounded to this snapshot and semantic neighborhood.

Claims & Grounded Evidence

1 Claim

Mechanism #method

Maintain the current solution, the best solution found, a neighborhood of applicable moves and memory-based tabu conditions on moves or their attributes. In the simple cost-minimizing version, choose the best admissible candidate under the configured evaluator even when every admissible move worsens the current objective, move there, and update the best-so-far record only on improvement. Update tabu memory so recent reversals or selected attributes remain restricted for a declared tenure, then expire restrictions according to that rule. Attribute-based restrictions can exclude unvisited solutions that share an attribute with a recent move. In the aspiration extension, a move satisfying the declared aspiration criterion can be admissible despite tabu status. Candidate sampling or approximate evaluation may replace full-neighborhood minimization. Intermediate-term memory can intensify search around features of good solutions, while longer-term frequency information can diversify it toward underexplored features; these are framework components whose concrete rules must be specified.

supports Source: Tabu Search—Part I · Locator: Section 2, PDF pp.2–4 / journal pp.191–193, Simple Tabu Search and attribute restrictions; Sections 3–4, PDF pp.6–7 / journal pp.195–196, aspiration; Section 8, PDF pp.10–11 / journal pp.199–200, intensification and diversification

⚠️ Curated Limitations & Negative Results

Finite recency memory is not a proof of cycle freedom or eventual global optimality. Attribute-based restrictions can exclude useful unvisited moves, and aspiration overrides must be designed with their effect on cycling in mind. The Part II finiteness construction was not inspected or generalized here.
The simple pseudocode stops when no admissible move exists, while the subsequent prose describes releasing oldest restrictions to restore a move. These are distinct handling choices; the conceptual record does not silently present them as one fully specified executable algorithm.
Tabu tenure, attributes, aspiration thresholds, candidate lists, move connectivity, initialization and stopping affect the search. Choosing the best currently admissible move does not imply monotonic objective improvement or a globally optimal final solution.
The source also discusses probabilistic, strategic-oscillation and mixed-integer extensions. This record does not instantiate all variants or curate performance comparisons. Memory-based search need not be a reinforcement-learning task.

Artificial Intelligence Ontology (AIO) Grounding

Explicit AIO Snapshot Assessment: No Match

Rationale: No suitable AIO target was found for this general optimization framework in the inspected snapshot and semantic neighborhood. Search memory, local costs and optional machine-learning applications do not by themselves identify a learning task or model class.

Search Scope: All 442 pinned AIO CLASS identities and scoped synonyms, all 301 preceding maintained identities, ignored/hidden full-checkout text, six exact AIO targets and seven native neighboring methods.

Examined AIO Candidate	Rejection Reason
`AIO:TrainingStrategy`	The definition concerns preprocessing or training machine-learning models. General local-search optimization is not restricted to such training.
`AIO:MachineLearningTask`	The target concerns learning methods from data; minimizing a supplied combinatorial objective is not necessarily that task.
`AIO:ReinforcementLearning`	Memory, adaptive penalties or an acceptance criterion do not themselves define a policy/environment learning problem. Exploration terminology is insufficient for a forced mapping.
`AIO:ReinforcementLearningLLM`	The method is not a language model fine-tuned through reward feedback.
`AIO:EvolutionaryLLM`	The target is a large language model. Its related evolutionary-algorithms synonym does not identify all optimizers or convert a single-trajectory method into a model.
`AIO:MarkovChain`	Some memoryless configurations admit a Markov description, while others use search history. That mathematical representation alone does not identify the optimization framework with the pinned network/model class or its semantic parent.

Evidence Sources & Primary Literature

1 Source

Source ID	Publication / Document	Type / Access	Reference & Checksum
`method-source`	Tabu Search—Part I Fred Glover	primary paper full_text	ID: doi:10.1287/ijoc.1.3.190 sha256:fb1102afc415…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-11T14:13:40Z

Updated: 2026-10-11T14:18:28Z

Source File: data/curated/TabuSearch.yaml