禁忌搜索

禁忌搜索（tabu search）在邻域搜索中保留近期动作或状态的记忆，暂时禁止容易造成回退的选择，并可用破禁准则允许特别有价值的候选。它通常选择当前允许邻域中最好的候选，即使比当前点更差；与只接受改善的局部搜索不同。

用短期记忆打断来回循环

考虑四个排成线的状态 $A,B,C,D$，只允许相邻移动，代价依次为 $0,1,2,-1$。从A开始，纯下降搜索没有可接受邻居。若改成每次选代价最低的邻居但不用记忆，则会反复 $A\to B\to A\to B$：在B处回到A比去C便宜。

采用一种简化的“离开状态两步内禁返”规则。第一步A到B后把A记为禁忌；第二步在B处不能回A，只能去C；随后B也暂时禁返，所以第三步从C去D。当前代价先升到一、二，再降到负一。这里的记忆迫使搜索跨过了高代价状态，而非直接证明高处总有更好的谷底。

短期禁返打断 A、B 的循环，使本次轨迹继续走向 D。

明确禁忌期限和破禁准则

设有限可行状态集为X，邻域为 $N(x)\subseteq X$，目标c要最小化。本文用状态禁忌作教学变体：第k步离开x后，令其到期编号为 $\tau (x)=k+L$，期限 $L\ge 1$ 为整数。第k步选择候选y时，若 $k\le \tau (y)$，通常禁止；到期后解除。初始所有到期编号为零。

破禁准则选为“若 $c(y)<c(x_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}})$，即优于全程最好值，则允许”。所以可选集为 $$A_k(x)=\{y\in N(x):k>\tau (y)\text{或}c(y)<c(x_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}})\}.$$ 从该集选目标最低者，平局使用预先声明的规则；集合为空则报告无可选候选。实际应用常存储动作属性而非完整状态，例如禁止刚交换的两个位置立即换回；这更节省内存，却可能同时禁止多个不同候选。禁忌期限、记忆对象、破禁规则都要随实现说明。

当前值允许上升；保存的最好值保持历史最小。

若候选D被某项记忆标为禁忌，而全程最好值仍为零，由于 $c(D)=-1<0$，破禁规则仍会让它进入候选集。这是本例的变式；破禁不是把整个禁忌表清空，而只解除该候选的这一阻挡。

能证明的运行性质

始终单独保存最好状态，更新规则为仅当新代价更低才替换。归纳可得 $c(x_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t},\mathrm{k}})=\underset{0\le j\le k}{min}c(x_j)$，所以最好值单调不增；当前值却可上下波动。有限期限也保证过期状态不会永久被这一短期记忆封锁，但它并不保证每个状态一定被访问。

在本例里可以枚举全部四个状态，独立确认D最优；一般大问题的禁忌搜索若只跑有限步，没有这样的枚举或有效下界，找到的最好解仍只是已知方案。无可选候选、连续若干步没有改善、达到时间预算，都是停止原因，不能分别当作不可行或全局最优证明。期限太长还可能让一个有可行邻居的当前点暂时没有允许移动。

可运行的状态记忆版

函数输入邻接表、代价、初态、正整数期限和预算，返回当前轨迹、最好状态与停止原因，不改写输入。邻接表索引代表可行状态；候选评价与禁忌查表是常数成本时，每轮约 $O(\mathrm{deg}x)$，到期数组占 $O(|X|)$，历史另占 $O(K)$。复杂目标评价或动作增量需另计。

Python 3

def tabu_search(neighbors,costs,start=0,tenure=2,budget=8):
    c = tuple(map(float,costs))
    graph = tuple(tuple(row) for row in neighbors)
    if len(graph) != len(c) or not 0 <= start < len(c) or tenure < 1 or budget < 0:
        raise ValueError("invalid graph or parameters")
    if any(y < 0 or y >= len(c) for row in graph for y in row):
        raise ValueError("invalid neighbor index")
    expiry = [0]*len(c)
    x,best,trace = start,start,[(0,start,c[start],start,c[start])]
    reason = "budget"
    for k in range(1,budget+1):
        allowed = [y for y in graph[x] if k > expiry[y] or c[y] < c[best]]
        if not allowed:
            reason = "no_admissible_neighbor"
            break
        y = min(allowed,key=lambda y:(c[y],y))
        expiry[x] = k+tenure
        x = y
        if c[x] < c[best]:
            best = x
        trace.append((k,x,c[x],best,c[best]))
    return trace,best,reason

trace,best,reason = tabu_search([[1],[0,2],[1,3],[2]],[0,1,2,-1])
for row in trace:
    print(row)
print("best",best,"stop",reason)
assert [row[1] for row in trace[:4]] == [0,1,2,3]