Tabu Search

in reviewThis lesson is complete and being validated before release - details may still change.

Tabu search

Loading interactive demo…

The grid is the walk: a row per choice the search stands on, a column per item, a 1 where the choice takes the item. Each iteration scores every one-flip neighbour, takes the best allowed one even when it is worse, and forbids flipping that item back for the tenure; a forbidden flip is allowed only when it beats the best score ever seen. The strip beneath lists the items by weight and value, and the plot tracks the score per iteration against the exact optimum from the knapsack table. Tap an item to read its tabu status.Take the tour, or press and explore. Legend:

The panel beside the stage is the real TabuSearch class from the published library executing in your browser, with the current line highlighted.

An item taken, tinted deeper the higher its row scores.
An item left, and the item and row headers.
The cell flipped to reach a row, and the item just flipped in the strip.
An item forbidden at that row, and in the strip.
A flip the aspiration rule let through, and the box around the best row so far.
A row number whose choice the walk had stood on before.
The picked item's column header.

score is the current row's score over the table's optimum; best is the best score so far; tabu names the items forbidden right now; revisits counts the rows whose choice had been stood on before; and iteration is which one is on display. The plot's second line is the best so far of the finished run.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

A walk over choices, not points. Simulated annealing, the prerequisite, walked a plane and read heights. Here the search walks the choices of a knapsack: a choice is a string of $n$ bits, one per item, and its neighbours are the $n$ strings with one bit flipped. Each neighbour is scored as its value less a penalty for every unit of weight over the capacity,

s(x) = v(x) - p \cdot \max(0,\, w(x) - C)

with $p$ twice the best value per unit of weight, rounded up, so an overweight choice never outscores a fitting one. Every iteration scores all $n$ neighbours and moves to the best allowed one.

Why a climber needs memory. Set the tenure to 0 and the rule is simply "take the best neighbour". At a local optimum every neighbour is worse, so the walk steps down to the least bad one; from there the best neighbour is the optimum it just left, one flip away, and it steps back. Two rows alternate for the rest of the run, which the revisits readout counts. Tabu search keeps a list of the items flipped in the last $t$ iterations, the tenure, and refuses to flip them again: the step back is forbidden, so the walk has to go somewhere new. The list is a memory of moves, not of states, which is why it is short and cheap.

Aspiration. A list that could never be overridden would also refuse a forbidden flip that happens to reach the best score ever seen. The aspiration rule allows exactly that case: a tabu move is taken when its score is strictly above the best so far. A tie never aspires, or the walk could step back into the optimum it just left. When every item is forbidden and none aspires, the one whose ban expires soonest is flipped.

The tenure trade-off. A short list cycles: with a tenure of 3 on the default bag the walk still returns to an earlier row after eight moves, because eight flips are enough to rebuild a choice the list has forgotten. A long list forbids too much: a tenure of 8 on a bag of 4 items forbids everything after four moves, and the walk is marched through the expiry order whatever the scores say. The right tenure is a property of the problem, and the stage lets you find it by eye.

Chance versus memory. Annealing escapes a local optimum by luck, an uphill move that passes a roll, and settles as the temperature falls. Tabu search escapes by rule: the downhill step is always taken and the step back is always refused, so the same seed gives the same walk at every tenure, and the only random draw is the start. Both are heuristics in the same sense: No Free Lunch (Wolpert and Macready, 1997) says that averaged over all possible objectives no search method beats any other, so tabu search is only good relative to a family of problems, those where a short memory of moves is enough to keep a walk from retracing itself.

What it costs and what it promises. An iteration scores $n$ neighbours at $O(n)$ each, so a run of $I$ iterations is $O(I n^2)$ with $O(n)$ memory for the choice and the list. It promises nothing about the answer: the best readout is the search's score over the exact optimum, which the knapsack lesson's table computes in $O(nC)$ and which this stage reads from the same table. A run may stop short of it, and a longer run or another start may reach it.

Where this goes next. The unit keeps the gradient-free walk and changes what stands in for the memory: a genetic algorithm trades one walker for a population, and ant colonies trade the list for a trail of pheromone.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

The list expires at the top of the loop. Each iteration begins by dropping every entry whose until is not past the iteration, so scan reports exactly the items forbidden for this round. The list move reports is taken after the push, so it can hold tenure + 1 items, the oldest of which expires before the next scan; the stage draws what the next scan will see.
Strictly better, or it is not an aspiration. The loop skips a tabu item unless s > bestScore; a tie with the best does not qualify, or the walk could step straight back into the optimum it has just been forced out of. aspired records whether the chosen item was tabu, and aspire fires only then.
Ties go to the lower index. s > scores[chosen] keeps the first item that reached the best score, so the walk is the same in Node and in the browser; nothing in a move depends on chance.
When everything is forbidden. If no item is allowed and none aspires, the entries are sorted by until and then by item, and the first is flipped: the ban that expires soonest gives way.
Tenure 0 pushes nothing. With tenure > 0 false the list stays empty and isTabu never fires, so the same loop is a plain best-neighbour climb; the two-cycle on the stage is that loop, not a special case.
Revisits are a set of strings. visited holds every choice as its bit string; a move whose key is already there is a revisit. That is the cycling the list exists to break, and the readout counts it.
The penalty is a static. defaultPenalty is twice the best value per weight, rounded up, so an overweight choice can never outscore a fitting one, and the knapsack lesson's exact optimum is the ceiling every score is drawn against.

Tabu search came out of Fred Glover's work on integer programming in the mid 1980s. A local search that only takes a better neighbour stops at the first local optimum, and one that takes the best neighbour even when it is worse walks straight back the next step. Glover's answer was memory: a short list of recent moves that may not be undone, with an aspiration rule that lets a forbidden move through when it reaches a new best. The 1986 paper that proposed it also used the word metaheuristic for the first time, and two papers in 1989 and 1990 set the method out in full.

1986Fred Glover - 'Future Paths for Integer Programming and Links to Artificial Intelligence' in Computers and Operations Research proposes tabu search, and contains the first mention of the term metaheuristic.source
1989Fred Glover - 'Tabu Search, Part I' in the ORSA Journal on Computing formalizes the method: the memory of recent moves, the tabu tenure, and the aspiration criteria that override it.source
1990Fred Glover - 'Tabu Search, Part II' in the same journal completes the account.source
1997Fred Glover and Manuel Laguna - The book 'Tabu Search' from Kluwer Academic Publishers gathers a decade of the method into its standard reference.source

Used today

Scheduling and timetabling - Job shops, exam timetables, and rosters: a move swaps two assignments, the score counts clashes, and the list stops the schedule from swapping the same pair back and forth.
Vehicle routing - Moving a customer from one route to another is a neighbour; the list forbids moving it straight back while the rest of the routes adjust around the change.
Graph colouring - Recolour one vertex that is in conflict, forbid giving it its old colour back for a few rounds, and the number of conflicts is the score to drive to zero.
Resource planning and telecommunications - Assigning frequencies, capacity, or staff under constraints, where a neighbour is one reassignment and the search must leave a local optimum without undoing itself.

bag

items8

iters20

hold3 rounds

score: 38 of 40
best: 40 of 40
tabu: g, d, h
revisits: 10
iteration: 20 of 20

tabu-search.ts

import { KnapsackProblem } from "../dynamic-programming/knapsack-problem";import { Mulberry32 } from "../random";import type { Tracer } from "../trace";export const TABU_MAX_ITERATIONS = 30;export const TABU_MAX_TENURE = 8;export interface TabuOptions {  problem: KnapsackProblem;  seed: number;  /** Default 20, an integer in [1, TABU_MAX_ITERATIONS]. */  iterations?: number;  /** How many iterations a flipped item stays forbidden; default 3, an integer in [0, TABU_MAX_TENURE]; 0 is a plain best-neighbour climb that can cycle. */  tenure?: number;  /** Per unit of overweight; default ceil(2 * the best value per weight), so no overweight choice outscores a fitting one. */  penalty?: number;  /** The bits to start from; default a seeded random choice. */  start?: readonly number[];}/** One forbidden move: the item and the first iteration it may be flipped again. */export interface TabuEntry {  readonly item: number;  readonly until: number;}export interface TabuResult {  /** The best choice found, as bits. */  best: number[];  score: number;  value: number;  weight: number;  /** The current score after each iteration. */  history: number[];  /** Moves that beat the best so far. */  improvements: number;  /** Moves taken although the item was tabu, because they beat the best. */  aspirations: number;  /** Moves that landed on a choice already visited: the cycling a tenure of 0 allows. */  revisits: number;  iterations: number;}/** * Tabu search over a 0/1 knapsack: from the current choice look at every * neighbour (one item flipped in or out), take the best one even when it * is worse than where you stand, and forbid flipping that item back for * the next few iterations. The forbidden list is the memory a hill * climber lacks: without it the best neighbour of a local optimum is the * optimum itself one flip away, and the search bounces between the two * forever. One exception, the aspiration rule: a forbidden move is taken * when it reaches a score better than any seen. When every move is * forbidden and none aspires, the one that expires soonest is taken. * * Time: O(I * n) scores for I iterations over n items, each score O(n). * Space: O(n) for the choice and the tabu list, O(I) for the history. */export class TabuSearch {  readonly iterations: number;  readonly tenure: number;  readonly penalty: number;  readonly start: readonly number[] | undefined;  constructor(    readonly options: TabuOptions,    private readonly tracer?: Tracer,  ) {    const { problem, seed } = options;    const iterations = options.iterations ?? 20;    const tenure = options.tenure ?? 3;    if (!Number.isInteger(iterations) || iterations < 1 || iterations > TABU_MAX_ITERATIONS) throw new RangeError(`iterations must be a whole number in [1, ${TABU_MAX_ITERATIONS}]`);    if (!Number.isInteger(tenure) || tenure < 0 || tenure > TABU_MAX_TENURE) throw new RangeError(`tenure must be a whole number in [0, ${TABU_MAX_TENURE}]`);    if (!Number.isFinite(seed)) throw new RangeError(`seed must be finite, got ${seed}`);    const penalty = options.penalty ?? TabuSearch.defaultPenalty(problem);    if (!(penalty > 0) || !Number.isFinite(penalty)) throw new RangeError("penalty must be a positive number");    if (options.start !== undefined) problem.evaluate(options.start);    this.iterations = iterations;    this.tenure = tenure;    this.penalty = penalty;    this.start = options.start;  }  /** Twice the best value per unit of weight, rounded up: an overweight choice always scores below a fitting one. */  static defaultPenalty(problem: KnapsackProblem): number {    return Math.ceil(2 * Math.max(...problem.items.map((item) => item.value / item.weight)));  }  /** A choice's value less the penalty for every unit over the capacity. */  score(bits: readonly number[]): number {    const plan = this.options.problem.evaluate(bits);    return plan.value - this.penalty * Math.max(0, plan.weight - this.options.problem.capacity);  }  /** The score of each neighbour, item i flipped. */  neighbourScores(bits: readonly number[]): number[] {    return bits.map((_, i) => this.score(TabuSearch.flipped(bits, i)));  }  /** True while the item may not be flipped at this iteration. */  static isTabu(tabu: readonly TabuEntry[], item: number, iteration: number): boolean {    return tabu.some((entry) => entry.item === item && entry.until > iteration);  }  static flipped(bits: readonly number[], item: number): number[] {    const next = [...bits];    next[item] = bits[item] === 1 ? 0 : 1;    return next;  }  run(): TabuResult {    const { problem } = this.options;    const n = problem.size;    const itemCount = problem.size;    const rng = new Mulberry32(this.options.seed);    const random = new Mulberry32(this.options.seed);    let bits = this.start ? [...this.start] : Array.from({ length: n }, () => rng.index(2));    let bits = this.start ? [...this.start] : Array.from({ length: itemCount }, () => random.index(2));    let score = this.score(bits);    let best = [...bits];    let bestScore = score;    let tabu: TabuEntry[] = [];    const visited = new Set<string>([TabuSearch.text(bits)]);    const history: number[] = [];    let improvements = 0;    let aspirations = 0;    let revisits = 0;    // ▸ the start: one random bit per item, 1 to take it and 0 to leave it; its score is the best so far    this.tracer?.emit("init", { bits: TabuSearch.text(bits), capacity: problem.capacity, items: n, score });    this.tracer?.emit("init", { bits: TabuSearch.text(bits), capacity: problem.capacity, items: itemCount, score });    for (let iteration = 1; iteration <= this.iterations; iteration++) {      tabu = tabu.filter((entry) => entry.until > iteration);      const scores = this.neighbourScores(bits);      const forbidden = tabu.map((entry) => entry.item);      // ▸ score every neighbour, the current choice with one item flipped, and note which items are still forbidden      this.tracer?.emit("scan", { forbidden: [...forbidden], iteration, scores });      let chosen = -1;      let aspired = false;      for (let item = 0; item < n; item++) {      for (let item = 0; item < itemCount; item++) {        const blocked = TabuSearch.isTabu(tabu, item, iteration);        const s = scores[item]!;        const candidateScore = scores[item]!;        if (blocked && !(s > bestScore)) continue;        if (blocked && !(candidateScore > bestScore)) continue;        if (chosen === -1 || s > scores[chosen]!) {        if (chosen === -1 || candidateScore > scores[chosen]!) {          chosen = item;          aspired = blocked;        }      }      if (chosen === -1) {        // Every move is forbidden and none beats the best: take the one that expires soonest.        const soonest = [...tabu].sort((a, b) => a.until - b.until || a.item - b.item)[0]!;        chosen = soonest.item;      }      if (aspired) {        aspirations++;        // ▸ a forbidden flip beats the best score ever seen: the aspiration rule lets it through        this.tracer?.emit("aspire", { item: chosen, iteration, score: scores[chosen]! });      }      bits = TabuSearch.flipped(bits, chosen);      score = scores[chosen]!;      tabu = tabu.filter((entry) => entry.item !== chosen);      if (this.tenure > 0) tabu.push({ item: chosen, until: iteration + this.tenure + 1 });      const key = TabuSearch.text(bits);      const revisit = visited.has(key);      if (revisit) revisits++;      visited.add(key);      const improved = score > bestScore;      if (improved) {        improvements++;        bestScore = score;        best = [...bits];      }      history.push(score);      // ▸ flip the best allowed item, even when the score falls, and forbid flipping it back for tenure iterations      this.tracer?.emit("move", {        bits: key,        forbidden: tabu.map((entry) => entry.item),        improved,        item: chosen,        iteration,        revisit,        score,      });    }    const plan = problem.evaluate(best);    // ▸ the best choice seen anywhere on the walk, with its score and weight    this.tracer?.emit("verdict", { best: TabuSearch.text(best), iterations: this.iterations, score: bestScore, weight: plan.weight });    return { best, score: bestScore, value: plan.value, weight: plan.weight, history, improvements, aspirations, revisits, iterations: this.iterations };  }  private static text(bits: readonly number[]): string {    return bits.join("");  }}

best =: 01011011
score =: 40
weight =: 14
improvements =: 2
aspirations =: 0
revisits =: 10

The run ends with 01011011 at score 40 and weight 14: 2 improvements, 0 aspirations, and 10 revisits of a choice already seen. The dynamic programming table is the exact answer the search is measured against.

import { KnapsackProblem } from "../dynamic-programming/knapsack-problem";import { Mulberry32 } from "../random";import type { Tracer } from "../trace";export const TABU_MAX_ITERATIONS = 30;export const TABU_MAX_TENURE = 8;export interface TabuOptions { problem: KnapsackProblem; seed: number; /** Default 20, an integer in [1, TABU_MAX_ITERATIONS]. */ iterations?: number; /** How many iterations a flipped item stays forbidden; default 3, an integer in [0, TABU_MAX_TENURE]; 0 is a plain best-neighbour climb that can cycle. */ tenure?: number; /** Per unit of overweight; default ceil(2 * the best value per weight), so no overweight choice outscores a fitting one. */ penalty?: number; /** The bits to start from; default a seeded random choice. */ start?: readonly number[];}/** One forbidden move: the item and the first iteration it may be flipped again. */export interface TabuEntry { readonly item: number; readonly until: number;}export interface TabuResult { /** The best choice found, as bits. */ best: number[]; score: number; value: number; weight: number; /** The current score after each iteration. */ history: number[]; /** Moves that beat the best so far. */ improvements: number; /** Moves taken although the item was tabu, because they beat the best. */ aspirations: number; /** Moves that landed on a choice already visited: the cycling a tenure of 0 allows. */ revisits: number; iterations: number;}/** * Tabu search over a 0/1 knapsack: from the current choice look at every * neighbour (one item flipped in or out), take the best one even when it * is worse than where you stand, and forbid flipping that item back for * the next few iterations. The forbidden list is the memory a hill * climber lacks: without it the best neighbour of a local optimum is the * optimum itself one flip away, and the search bounces between the two * forever. One exception, the aspiration rule: a forbidden move is taken * when it reaches a score better than any seen. When every move is * forbidden and none aspires, the one that expires soonest is taken. * * Time: O(I * n) scores for I iterations over n items, each score O(n). * Space: O(n) for the choice and the tabu list, O(I) for the history. */export class TabuSearch { readonly iterations: number; readonly tenure: number; readonly penalty: number; readonly start: readonly number[] | undefined; constructor( readonly options: TabuOptions, private readonly tracer?: Tracer, ) { const { problem, seed } = options; const iterations = options.iterations ?? 20; const tenure = options.tenure ?? 3; if (!Number.isInteger(iterations) || iterations < 1 || iterations > TABU_MAX_ITERATIONS) throw new RangeError(`iterations must be a whole number in [1, ${TABU_MAX_ITERATIONS}]`); if (!Number.isInteger(tenure) || tenure < 0 || tenure > TABU_MAX_TENURE) throw new RangeError(`tenure must be a whole number in [0, ${TABU_MAX_TENURE}]`); if (!Number.isFinite(seed)) throw new RangeError(`seed must be finite, got ${seed}`); const penalty = options.penalty ?? TabuSearch.defaultPenalty(problem); if (!(penalty > 0) || !Number.isFinite(penalty)) throw new RangeError("penalty must be a positive number"); if (options.start !== undefined) problem.evaluate(options.start); this.iterations = iterations; this.tenure = tenure; this.penalty = penalty; this.start = options.start; } /** Twice the best value per unit of weight, rounded up: an overweight choice always scores below a fitting one. */ static defaultPenalty(problem: KnapsackProblem): number { return Math.ceil(2 * Math.max(...problem.items.map((item) => item.value / item.weight))); } /** A choice's value less the penalty for every unit over the capacity. */ score(bits: readonly number[]): number { const plan = this.options.problem.evaluate(bits); return plan.value - this.penalty * Math.max(0, plan.weight - this.options.problem.capacity); } /** The score of each neighbour, item i flipped. */ neighbourScores(bits: readonly number[]): number[] { return bits.map((_, i) => this.score(TabuSearch.flipped(bits, i))); } /** True while the item may not be flipped at this iteration. */ static isTabu(tabu: readonly TabuEntry[], item: number, iteration: number): boolean { return tabu.some((entry) => entry.item === item && entry.until > iteration); } static flipped(bits: readonly number[], item: number): number[] { const next = [...bits]; next[item] = bits[item] === 1 ? 0 : 1; return next; } run(): TabuResult { const { problem } = this.options; const n = problem.size; const itemCount = problem.size; const rng = new Mulberry32(this.options.seed); const random = new Mulberry32(this.options.seed); let bits = this.start ? [...this.start] : Array.from({ length: n }, () => rng.index(2)); let bits = this.start ? [...this.start] : Array.from({ length: itemCount }, () => random.index(2)); let score = this.score(bits); let best = [...bits]; let bestScore = score; let tabu: TabuEntry[] = []; const visited = new Set<string>([TabuSearch.text(bits)]); const history: number[] = []; let improvements = 0; let aspirations = 0; let revisits = 0; // ▸ the start: one random bit per item, 1 to take it and 0 to leave it; its score is the best so far this.tracer?.emit("init", { bits: TabuSearch.text(bits), capacity: problem.capacity, items: n, score }); this.tracer?.emit("init", { bits: TabuSearch.text(bits), capacity: problem.capacity, items: itemCount, score }); for (let iteration = 1; iteration <= this.iterations; iteration++) { tabu = tabu.filter((entry) => entry.until > iteration); const scores = this.neighbourScores(bits); const forbidden = tabu.map((entry) => entry.item); // ▸ score every neighbour, the current choice with one item flipped, and note which items are still forbidden this.tracer?.emit("scan", { forbidden: [...forbidden], iteration, scores }); let chosen = -1; let aspired = false; for (let item = 0; item < n; item++) { for (let item = 0; item < itemCount; item++) { const blocked = TabuSearch.isTabu(tabu, item, iteration); const s = scores[item]!; const candidateScore = scores[item]!; if (blocked && !(s > bestScore)) continue; if (blocked && !(candidateScore > bestScore)) continue; if (chosen === -1 || s > scores[chosen]!) { if (chosen === -1 || candidateScore > scores[chosen]!) { chosen = item; aspired = blocked; } } if (chosen === -1) { // Every move is forbidden and none beats the best: take the one that expires soonest. const soonest = [...tabu].sort((a, b) => a.until - b.until || a.item - b.item)[0]!; chosen = soonest.item; } if (aspired) { aspirations++; // ▸ a forbidden flip beats the best score ever seen: the aspiration rule lets it through this.tracer?.emit("aspire", { item: chosen, iteration, score: scores[chosen]! }); } bits = TabuSearch.flipped(bits, chosen); score = scores[chosen]!; tabu = tabu.filter((entry) => entry.item !== chosen); if (this.tenure > 0) tabu.push({ item: chosen, until: iteration + this.tenure + 1 }); const key = TabuSearch.text(bits); const revisit = visited.has(key); if (revisit) revisits++; visited.add(key); const improved = score > bestScore; if (improved) { improvements++; bestScore = score; best = [...bits]; } history.push(score); // ▸ flip the best allowed item, even when the score falls, and forbid flipping it back for tenure iterations this.tracer?.emit("move", { bits: key, forbidden: tabu.map((entry) => entry.item), improved, item: chosen, iteration, revisit, score, }); } const plan = problem.evaluate(best); // ▸ the best choice seen anywhere on the walk, with its score and weight this.tracer?.emit("verdict", { best: TabuSearch.text(best), iterations: this.iterations, score: bestScore, weight: plan.weight }); return { best, score: bestScore, value: plan.value, weight: plan.weight, history, improvements, aspirations, revisits, iterations: this.iterations }; } private static text(bits: readonly number[]): string { return bits.join(""); }}