Interactive companion · Chapter 6 · Tabu search

Tabu Search Lab

Local search with a memory. Tabu search moves to the best neighbor it is allowed to visit, even uphill, and forbids recent moves for a while so it can walk out of local optima.

♛ Constraint satisfaction 0110 Binary x, y Continuous 3 1 5 2 4 Routing WS Assembly lines

Based on Chapter 6, “Tabu search,” in Alaa Khamis, Optimization Algorithms: AI techniques for design, planning, and control problems, Manning Publications, 2024 (ISBN 978-1633438835).

Tabu search on Himmelblau’s function. Dashed circles mark recently visited points, which are tabu.

Part 1 · Sections 6.1 and 6.2

From local search to tabu search

Local search moves only when a neighbor improves the current solution, so it stops at the first local optimum. Tabu search (TS) adds memory: it accepts the best neighbor even when it is worse, and forbids moves back to recently visited solutions.

Sections 6.1 and 6.2 of the book build this idea from a resort-restaurant analogy and weigh the pros and cons of TS.

Escaping local optima

Both searches start at the same point. Local search stops at the first valley; tabu search keeps going and marks each visited position tabu for T iterations (red bars). Click the landscape to choose a new start, then Step or Run.

Local search vs. tabu search

Minimize f(x)

Part 2 · Section 6.2

The tabu search algorithm

Algorithm 6.1: Local search Input: an initial feasible solution s while termination criteria not met generate a neighbor s′ by local moves if s′ is better than s then s ← s′

Algorithm 6.2: Tabu search Input: an initial feasible solution s while termination criteria not met choose the best s′ ∈ N(s) − T(s) + A(s) # neighbors, minus tabu moves, plus moves # allowed by the aspiration criterion memorize s′ if it improves the best known solution s ← s′ # even if s′ is worse update the tabu list T(s) and aspiration A(s)

Each iteration builds a candidate list of moves, evaluates them, discards tabu ones unless they pass the aspiration criterion, and makes the best admissible move, even a worsening one.

Figure 6.1 in Section 6.2 walks through this loop, with stopping rules and a small TSP neighborhood example.

Part 3 · Section 6.2.1

Memory structures

Recency (short-term) memory forbids recent moves for a number of iterations, the tabu tenure. Frequency (long-term) memory counts how often each move is made and penalizes frequent ones to diversify the search.

Section 6.2.1 links these memories to models of human memory and compares static, dynamic, adaptive and reactive tenure rules (Figure 6.7).

The tabu structure in action

Order seven laminate sheets for maximum strength (Listing C.5); each move swaps two sheets. Step through the search and watch the triangle: tenures fill the upper half, swap counts the lower half.

Recency and frequency memory

Maximize strength · 21 swap neighbors

Order

Upper triangle (red): iterations a swap stays tabu. Lower triangle: how many times the swap has been made. Read swap (i, j) at row i, column j above the diagonal and at row j, column i below it.

Aspiration criteria and the tabu tenure

An aspiration criterion lifts the tabu status of a move that would beat the best solution found so far. The tenure matters most: too short risks cycling, too long risks stagnation (try the experiment in Part 9).

Figure 6.6 and Section 6.2.1 explain the tenure trade-off and list every TS parameter you can tune or adapt during a run.

Part 4 · Section 6.3

Constraint satisfaction: n-queens

Place n queens so that none attack each other. As a permutation, only diagonal collisions remain to minimize; a move swaps two queens’ columns and that swap becomes tabu. Step from the book’s board or a random one.

Section 6.3 carries out the first iterations by hand on Figure 6.8 and solves larger boards with Listing 6.1.

n-queens with tabu search

Minimize collisions

Columns C

Run it in Python: Listing 6.1 n-queens From-scratch code ↓

Listing 6.1 uses a different neighborhood (single-queen moves) from the swap moves above.

Part 5 · Binary problems

A 0/1 knapsack problem

Pack seven items into a 50 kg knapsack. A solution is a bit string, and f below rewards filling the knapsack exactly while packing high utility (minimize):

f = f₁ − f₂, f₁ = |Σw_i − 50| (+ 50 if overloaded), f₂ = Σu_i

A move flips one item, which then becomes tabu.

Knapsack with tabu search

Minimize f

Part 6 · Graph problems

Connecting factory units with cables

Connect five factory units at minimum cable cost (a minimum spanning tree). A move swaps one tree edge for another; the edge just added is tabu to remove for T = 2 iterations. Press Step to follow each swap.

Edge-swap tabu search

Minimize cable cost

Part 7 · Assignment problems

The quadratic assignment problem

Place n objects on n sites to minimize total flow × distance (the NUG5 instance; matrices at right):

cost(p) = Σ_i Σ_j f_{p_ip_j} d_ij

A move exchanges two sites’ objects; returning an object to a site it just left is tabu for a while. Step and watch the tabu matrix.

QAP with tabu search

Minimize flow × distance

Tabu matrix: red cells show how long an object may not return to a site.

Part 8 · Section 6.4

Continuous functions

Here a candidate is tabu if it falls within a tabu radius of a recent point. Pick a function (Himmelblau, Mishra’s Bird or Schwefel) and Run.

Section 6.4 solves Himmelblau’s function with the book’s optalgotools solver in Listing 6.2, and Listing C.4 tackles the deceptive Schwefel function.

Continuous tabu search lab

Minimize f(x, y)

Current value (faint) and best value per iteration.

Run it in Python: Listing 6.2 Function optimization Listing C.4 Schwefel From-scratch code ↓

Part 9 · Section 6.5

Routing: the Berlin52 TSP

Find the shortest tour through 52 Berlin locations (optimum 7,542). A 2-opt move reverses a segment; removed edges become tabu. Run it, then try the swap neighborhood.

Section 6.5 solves Berlin52 with Google OR-Tools in Listing 6.3 and with the generic solver, and Listing 6.4 routes a delivery semi-truck.

Berlin52 tabu search lab

Minimize tour length

Current (faint) and best tour length per iteration.

Effect of the tabu tenure

Run 2-opt tabu search four times per tenure and compare the best tours. Look for cycling at short tenures and stagnation at long ones.

Tenure experiment

Berlin52 · 4 runs per tenure

Mean best tour length (line) and each run (dots) against the tabu tenure. The dashed line is the optimum, 7,542.

Run it in Python: Listing 6.3 Berlin52 Listing 6.4 Delivery semi-truck From-scratch code ↓

Part 10 · Section 6.6

Assembly line balancing

Assign tasks to workstations so no station exceeds the cycle time CT and precedence is respected. SALBP-1 minimizes the number of stations; balance is measured by the smoothing index:

SI = √( Σ_i=1..NS (WL_max − WL_i)² / NS )

A solution is a task sequence; a move swaps two tasks. Step through the 6-task example below.

Section 6.6 defines the SALBP and TSALBP variants (Table 6.1) and works this example by hand with Listing 6.5.

Precedence diagram (Figure 6.22).

Hand iterations, automated

6 tasks · CT = 4 · tenure 3

Sequence

Benchmark lab

Pick a SALBP benchmark and Run: tabu search minimizes stations first, then the smoothing index.

SALBP-1 benchmarks

Minimize stations, then SI

Best number of stations + SI/CT per iteration (lower is better).

Run it in Python: Listing 6.5 SALBP Listing 6.6 Benchmarks From-scratch code ↓

Part 11 · Section 6.5 and appendix C

More applications

Delivery semi-truck routing

Route a truck through 18 stores in the Greater Toronto Area.

Listing 6.4

Schwefel function

A deceptive multimodal test function.

Listing C.4

Composite laminate design

The problem behind the Part 3 demo.

Listing C.5

Assembly line balancing

Another SALBP solved with tabu search.

Listing C.6

Part 12 · Code

Python in Google Colab

Open the book’s notebooks in Colab, or the companion notebook with the from-scratch code below.

Notebooks

All examplesTS Lab companion notebookThe from-scratch code below, ready to run Chapter 6Listing 6.1n-queens problem Chapter 6Listing 6.2Function optimization Chapter 6Listing 6.3Berlin52 TSP Chapter 6Listing 6.4Delivery semi-truck routing Chapter 6Listing 6.5Assembly line balancing Chapter 6Listing 6.6SALBP benchmarks Appendix CListing C.4Schwefel function Appendix CListing C.5Composite laminate design Appendix CListing C.6Assembly line balancing

From-scratch implementations

Open all six in Colab

# Tabu search for the n-queens problem (Chapter 6, Section 6.3)
# A solution is a permutation: queens[i] is the column of the queen in row i, so rows and columns never clash
# and only diagonal collisions remain. The neighborhood swaps the columns of two queens.
import numpy as np


def collisions(q):
    n = len(q)
    return sum(abs(q[i] - q[j]) == j - i for i in range(n) for j in range(i + 1, n))


def swap(q, i, j):
    q = list(q)
    q[i], q[j] = q[j], q[i]
    return q


# The book's starting board (Figure 6.8): Q1..Q7 in columns 4, 5, 3, 6, 7, 1, 2
book = [4, 5, 3, 6, 7, 1, 2]
print("initial collisions:", collisions(book))                       # 4
for i, j in [(1, 7), (2, 3), (2, 6), (5, 6), (1, 5)]:
    print(f"swap Q{i}, Q{j}: delta = {collisions(swap(book, i - 1, j - 1)) - collisions(book)}")


def tabu_search(n=7, tenure=3, max_iter=500, aspiration=True, init=None, seed=0):
    rng = np.random.default_rng(seed)
    q = list(init) if init is not None else list(rng.permutation(n))
    tabu = np.zeros((n, n), int)            # tabu[i, j]: last iteration at which the swap (i, j) is tabu-active
    best, best_val = q, collisions(q)
    for it in range(1, max_iter + 1):
        if best_val == 0:
            break
        cands = []
        for i in range(n):
            for j in range(i + 1, n):
                v = collisions(swap(q, i, j))
                is_tabu = tabu[i, j] >= it
                if not is_tabu or (aspiration and v < best_val):       # aspiration: better than the best so far
                    cands.append((v, rng.random(), i, j))
        if not cands:
            continue
        v, _, i, j = min(cands)                 # best admissible move, ties broken at random
        q = swap(q, i, j)
        tabu[i, j] = it + tenure
        if v < best_val:
            best, best_val = q, v
    return best, best_val, it


sol, val, it = tabu_search(init=[c - 1 for c in book])
print("7-queens from the book's board:", [c + 1 for c in sol], "collisions:", val, "iterations:", it)
sol, val, it = tabu_search(n=20, tenure=5, seed=1)
print("20-queens:", [c + 1 for c in sol], "collisions:", val, "iterations:", it)

# Tabu search for a 0/1 knapsack problem: capacity 50 kg, 7 items
# Minimize f = f1 - f2, where f1 = |total weight - capacity| (+50 if overloaded) and f2 = total utility.
import itertools
import numpy as np

W = np.array([10, 12, 15, 27, 30, 20, 7])
U = np.array([2, 1, 3, 4, 1, 3, 1])
C, PENALTY = 50, 50


def f(x):
    w = W @ x
    return abs(w - C) + (PENALTY if w > C else 0) - U @ x


def neighbors(x, two_moves):
    """Add or delete one item; optionally also add one item and delete another in the same move."""
    out = []
    for i in range(len(x)):
        y = x.copy(); y[i] ^= 1
        out.append((y, (("Add" if y[i] else "Delete"), i + 1), (i,)))
    if two_moves:
        for a in np.flatnonzero(x == 0):
            for d in np.flatnonzero(x == 1):
                y = x.copy(); y[a], y[d] = 1, 0
                out.append((y, ("Add", a + 1, "Delete", d + 1), (a, d)))
    return out


def tabu_search(x0, tenure=3, max_iter=30, two_moves=False, verbose=True):
    x, best = x0.copy(), x0.copy()
    tabu = {}                                    # item -> last iteration at which changing it is tabu
    for it in range(1, max_iter + 1):
        cands = [(f(y), m, items, y) for y, m, items in neighbors(x, two_moves)]
        admissible = [c for c in cands if all(tabu.get(i, 0) < it for i in c[2]) or c[0] < f(best)]
        val, move, items, x = min(admissible, key=lambda c: c[0])
        for i in items:
            tabu[i] = it + tenure
        if val < f(best):
            best = x.copy()
        if verbose:
            print(f"iter {it:2d}: {''.join(map(str, x))}  f = {val:3d}  move = {move}")
    return best, f(best)


x0 = np.array([1, 0, 1, 0, 0, 1, 1])          # items 1, 3, 6 and 7
print("initial f =", f(x0))                   # 52 - 9 = 43
for y, m, _ in neighbors(x0, False):
    print(" ", "".join(map(str, y)), m, f(y))
best, val = tabu_search(x0, max_iter=10)
print("single moves:", "".join(map(str, best)), "f =", val)
best, val = tabu_search(x0, max_iter=6, two_moves=True)
print("one- and two-item moves:", "".join(map(str, best)), "f =", val)

opt = min((np.array(b) for b in itertools.product([0, 1], repeat=7)), key=f)
print("optimum by enumeration:", "".join(map(str, opt)), "f =", f(opt))   # items 3, 4 and 7, f = -7

# Tabu search for the quadratic assignment problem NUG5
# p[i] is the object placed on site i; cost = sum over all ordered pairs i, j of flow(p[i], p[j]) * distance(i, j).
import itertools
import numpy as np

F = np.array([[0, 5, 2, 4, 1], [5, 0, 3, 0, 2], [2, 3, 0, 0, 0], [4, 0, 0, 0, 5], [1, 2, 0, 5, 0]])
D = np.array([[0, 1, 1, 2, 3], [1, 0, 2, 1, 2], [1, 2, 0, 1, 2], [2, 1, 1, 0, 1], [3, 2, 2, 1, 0]])
n = len(F)
cost = lambda p: int((F[np.ix_(p, p)] * D).sum())


def swapped(p, r, s):
    q = p.copy(); q[r], q[s] = q[s], q[r]
    return q


p = np.array([2, 4, 1, 5, 3]) - 1                            # object 2 on site 1, object 4 on site 2, ...
print("initial cost:", cost(p))                              # 72
print("deltas:", {(r + 1, s + 1): cost(swapped(p, r, s)) - cost(p) for r, s in itertools.combinations(range(n), 2)})


def tabu_search(p, tenure=6, max_iter=30):
    best, best_cost = p.copy(), cost(p)
    T = np.zeros((n, n), int)            # T[object, site]: placing the object back on the site is tabu until then
    for it in range(1, max_iter + 1):
        moves = []
        for r, s in itertools.combinations(range(n), 2):
            q = swapped(p, r, s)
            tabu = T[p[r], s] >= it and T[p[s], r] >= it   # both objects would return to sites they recently left
            if not tabu or cost(q) < best_cost:              # aspiration by objective
                moves.append((cost(q), r, s))
        c, r, s = min(moves)
        T[p[r], r] = T[p[s], s] = it + tenure                # forbid moving them back for `tenure` iterations
        p = swapped(p, r, s)
        if c < best_cost:
            best, best_cost = p.copy(), c
        print(f"iter {it:2d}: swap sites ({r + 1}, {s + 1}) -> p = {p + 1}, cost = {c}")
    return best, best_cost


best, c = tabu_search(p, max_iter=8)
print("best:", best + 1, "cost:", c)
print("optimum by enumeration:", min(cost(np.array(q)) for q in itertools.permutations(range(n))))

# Tabu search for continuous functions (Chapter 6, Section 6.4)
# Neighbors are Gaussian steps around the current point. Recently visited points are tabu: a candidate
# within the tabu radius of any of them is rejected, unless it beats the best so far (aspiration).
import numpy as np
import matplotlib.pyplot as plt


def himmelblau(x, y):
    return (x**2 + y - 11)**2 + (x + y**2 - 7)**2


def schwefel(x, y):                      # global minimum 0 at (420.9687, 420.9687)
    return 418.9829 * 2 - x * np.sin(np.sqrt(abs(x))) - y * np.sin(np.sqrt(abs(y)))


def tabu_search(f, bounds, x0=None, max_iter=100, neighbor_size=50, step=1.0, tenure=5, radius=0.5,
                aspiration=True, seed=0):
    rng = np.random.default_rng(seed)
    lo, hi = np.array(bounds, float).T
    x = rng.uniform(lo, hi) if x0 is None else np.array(x0, float)
    best, best_val = x.copy(), f(*x)
    tabu, path = [x.copy()], [x.copy()]
    for it in range(max_iter):
        cands = np.clip(x + rng.normal(0, step, (neighbor_size, 2)), lo, hi)
        vals = np.array([f(*c) for c in cands])
        ok = [k for k in range(neighbor_size)
              if min(np.linalg.norm(cands[k] - t) for t in tabu) > radius or (aspiration and vals[k] < best_val)]
        if not ok:
            continue
        k = min(ok, key=lambda k: vals[k])          # best admissible neighbor, even if it is worse
        x = cands[k]
        tabu = (tabu + [x.copy()])[-tenure:]        # recency-based memory of the last `tenure` points
        path.append(x.copy())
        if vals[k] < best_val:
            best, best_val = x.copy(), vals[k]
    return best, best_val, np.array(path)


def local_search(f, bounds, x0, max_iter=100, neighbor_size=50, step=1.0, seed=0):
    rng = np.random.default_rng(seed)
    lo, hi = np.array(bounds, float).T
    x, val = np.array(x0, float), f(*x0)
    for it in range(max_iter):
        cands = np.clip(x + rng.normal(0, step, (neighbor_size, 2)), lo, hi)
        vals = np.array([f(*c) for c in cands])
        if vals.min() < val:                         # accept improving moves only
            x, val = cands[vals.argmin()], vals.min()
    return x, val


best, val, path = tabu_search(himmelblau, [[-6, 6], [-6, 6]], seed=1)
print("Himmelblau:", np.round(best, 4), "f =", round(val, 6))

# On Schwefel's function, local search stalls in the first basin it finds; tabu search keeps moving
b = [[-500, 500], [-500, 500]]
x0 = [-300, -300]
print("Schwefel, local search:", np.round(local_search(schwefel, b, x0, max_iter=300, step=30)[1], 2))
bt, vt, pt = tabu_search(schwefel, b, x0=x0, max_iter=300, step=30, tenure=30, radius=60, seed=0)
print("Schwefel, tabu search:", np.round(bt, 2), "f =", round(vt, 2))

X, Y = np.meshgrid(np.linspace(-6, 6, 200), np.linspace(-6, 6, 200))
plt.contour(X, Y, np.log1p(himmelblau(X, Y)), 30, cmap="viridis")
plt.plot(path[:, 0], path[:, 1], ".-", c="tab:red", lw=1); plt.plot(*best, "k*", ms=14)
plt.title("Tabu search on Himmelblau's function"); plt.axis("equal"); plt.show()

# Tabu search for the Berlin52 TSP (Chapter 6, Section 6.5); the optimal tour length is 7,542
# Moves are 2-opt exchanges. The two edges a move removes become tabu: adding either of them back is
# forbidden for `tenure` iterations unless the move gives a new best tour (aspiration).
import numpy as np
import matplotlib.pyplot as plt

XY = np.array([[565, 575], [25, 185], [345, 750], [945, 685], [845, 655], [880, 660], [25, 230], [525, 1000],
    [580, 1175], [650, 1130], [1605, 620], [1220, 580], [1465, 200], [1530, 5], [845, 680], [725, 370], [145, 665],
    [415, 635], [510, 875], [560, 365], [300, 465], [520, 585], [480, 415], [835, 625], [975, 580], [1215, 245],
    [1320, 315], [1250, 400], [660, 180], [410, 250], [420, 555], [575, 665], [1150, 1160], [700, 580], [685, 595],
    [685, 610], [770, 610], [795, 645], [720, 635], [760, 650], [475, 960], [95, 260], [875, 920], [700, 500],
    [555, 815], [830, 485], [1170, 65], [830, 610], [605, 625], [595, 360], [1340, 725], [1740, 245]], float)
n = len(XY)
D = np.rint(np.hypot(*(XY[:, None, :] - XY[None, :, :]).transpose(2, 0, 1)))   # TSPLIB EUC_2D rounding
length = lambda t: D[t, np.roll(t, -1)].sum()


def tabu_search(max_iter=1500, tenure=15, sample=None, seed=0):
    rng = np.random.default_rng(seed)
    t = rng.permutation(n)
    L = length(t)
    best, best_L = t.copy(), L
    tabu = {}                                        # edge (i, j) -> last iteration at which adding it is tabu
    pairs = [(i, j) for i in range(n - 1) for j in range(i + 2, n) if not (i == 0 and j == n - 1)]
    history = []
    for it in range(1, max_iter + 1):
        cand = pairs if sample is None else [pairs[k] for k in rng.choice(len(pairs), sample, replace=False)]
        best_move, best_delta = None, np.inf
        for i, j in cand:
            a, b, c, d = t[i], t[i + 1], t[j], t[(j + 1) % n]
            delta = D[a, c] + D[b, d] - D[a, b] - D[c, d]
            is_tabu = tabu.get((min(a, c), max(a, c)), 0) >= it or tabu.get((min(b, d), max(b, d)), 0) >= it
            if (not is_tabu or L + delta < best_L) and delta < best_delta:
                best_move, best_delta = (i, j), delta
        i, j = best_move
        a, b, c, d = t[i], t[i + 1], t[j], t[(j + 1) % n]
        tabu[(min(a, b), max(a, b))] = tabu[(min(c, d), max(c, d))] = it + tenure
        t[i + 1:j + 1] = t[i + 1:j + 1][::-1]       # apply the 2-opt move, even if it makes the tour longer
        L += best_delta
        if L < best_L:
            best, best_L = t.copy(), L
        history.append(best_L)
    return best, best_L, history


best, L, hist = tabu_search()
print(f"best tour length: {L:.0f} (optimum 7,542)")
fig, ax = plt.subplots(1, 2, figsize=(12, 4.5))
ax[0].plot(*XY[np.append(best, best[0])].T, "o-", ms=3); ax[0].set_title(f"Berlin52 tour, length {L:.0f}")
ax[1].plot(hist); ax[1].axhline(7542, ls="--", c="r"); ax[1].set_xlabel("iteration"); ax[1].set_title("best length")
plt.show()

# Tabu search for the simple assembly line balancing problem, SALBP-1 (Chapter 6, Section 6.6)
# A solution is a task sequence that respects the precedence constraints. Tasks fill stations in order;
# a new station opens when the next task would exceed the cycle time.
import itertools
import numpy as np

# The book's example (Figure 6.22): six tasks, cycle time 4 minutes
TIMES = {1: 2, 2: 3, 3: 3, 4: 1, 5: 3, 6: 3}
PRED = {3: [1], 4: [2], 5: [3, 4], 6: [4]}           # task: its immediate predecessors
CT = 4


def stations(seq, times=TIMES, ct=CT):
    loads = [0]
    for task in seq:
        if loads[-1] + times[task] > ct:
            loads.append(0)
        loads[-1] += times[task]
    return loads


def smoothing_index(loads):                          # equation 6.1
    loads = np.array(loads, float)
    return np.sqrt(((loads.max() - loads) ** 2).sum() / len(loads))


def feasible(seq, pred=PRED):
    pos = {t: k for k, t in enumerate(seq)}
    return all(pos[p] < pos[t] for t, ps in pred.items() for p in ps)


def tabu_search(seq, tenure=3, max_iter=20, times=TIMES, pred=PRED, ct=CT, verbose=True):
    """Minimize the number of stations first, then the smoothing index; moves swap two tasks."""
    key = lambda s: (len(stations(s, times, ct)), smoothing_index(stations(s, times, ct)))
    cur, best = list(seq), list(seq)
    tabu = {}
    for it in range(1, max_iter + 1):
        cands = []
        for i, j in itertools.combinations(range(len(cur)), 2):
            s = cur.copy(); s[i], s[j] = s[j], s[i]
            move = tuple(sorted((cur[i], cur[j])))
            if feasible(s, pred) and (tabu.get(move, 0) < it or key(s) < key(best)):
                cands.append((key(s), move, s))
        if not cands:
            break
        k, move, cur = min(cands, key=lambda c: c[0])
        tabu[move] = it + tenure
        if k < key(best):
            best = cur
        if verbose:
            print(f"iter {it}: swap {move} -> {cur}, loads {stations(cur, times, ct)}, SI = {k[1]:.4f}")
    return best


init = [1, 2, 3, 4, 5, 6]
print("initial loads:", stations(init), "SI =", round(smoothing_index(stations(init)), 4))   # 2-3-4-3-3, 1.1832
best = tabu_search(init, max_iter=3)
print("best:", best, "loads:", stations(best), "SI =", round(smoothing_index(stations(best)), 4))

# MANSOOR benchmark from appendix B: 11 tasks, cycle time 48 (best known: 4 stations)
T = dict(enumerate([4, 38, 45, 12, 10, 8, 12, 10, 2, 10, 34], start=1))
P = {}
for a, b in [(1, 4), (2, 4), (2, 5), (3, 11), (4, 6), (5, 7), (6, 8), (7, 9), (8, 10), (9, 10), (10, 11)]:
    P.setdefault(b, []).append(a)
seq = list(range(1, 12))
best = tabu_search(seq, tenure=4, max_iter=60, times=T, pred=P, ct=48, verbose=False)
print("MANSOOR:", best, "loads:", stations(best, T, 48), "SI =", round(smoothing_index(stations(best, T, 48)), 3))

Open the companion notebook in Colab, or paste a tab’s code into any notebook.

Part 13 · Summary

What to remember

Local search + memory

Tabu search moves to the best admissible neighbor, even uphill.

Tabu list and tenure

Too short a tenure risks cycling; too long risks stagnation.

Aspiration

A tabu move is allowed if it beats the best solution so far.

Balance

Recency memory intensifies; frequency memory diversifies.

References: F. Glover, “Tabu search and adaptive memory programming: advances, applications and challenges,” 1997. F. Glover, M. Laguna and R. Martí, “Principles of tabu search.” R. Battiti and G. Tecchiolli, “The reactive tabu search,” 1994. E. Taillard, “Robust taboo search for the quadratic assignment problem,” 1991. A. Khamis, Optimization Algorithms: AI techniques for design, planning, and control problems, Manning, 2024, Chapter 6.

Part 14 · Quiz

Check your understanding

Two quick questions on Chapter 6. Pick an answer to check it.

Q1. Every neighbor of the current solution is worse, and the only improving move is tabu but would give a solution better than the best found so far. What does tabu search do?

Q2. In the tenure experiment on Berlin52, what typically goes wrong when the tabu tenure is very long?

For more exercises with full solutions, see Appendix C, “Exercises and solutions,” in Optimization Algorithms. The coding solutions are also on GitHub (Chapter 6).