禁忌搜索（Tabu Search, TS）
禁忌搜索在邻域搜索框架上引入短期记忆，结合渴望准则，在探索与利用之间折中。属单点、带记忆的元启发式，见 元启发式总览。
禁忌表（Tabu List）
对象：表内通常不直接「禁止解向量本身」（维度过大），而禁止可逆、可标识的移动属性 a。同一邻域上属性与移动的抽取规则要一致，否则「禁忌了谁」在实现上会含糊。示例如下：
- TSP：例如「边 刚被删除又立刻加回」等可标识逆移。
- 调度：例如「某工序对在相邻换位」等。
Recency 与 tenure：表维护的是近若干步内、或每属性剩余禁忌迭代数。
- 固定 tenure L：a 在入选后，连续 L 步内禁止再次出现「由该属性标识的逆移动」或相同属性再选（与邻域如何定义逆有关）。L 过短易短循环，过长易过度排斥合理探索。
- 变长 tenure：在区间 [Lmin, Lmax] 上随机、或随搜索阶段调整，以减轻周期性与参数敏感。
实现形态：常见有：
- 循环队列或滑动窗口：存最近 L 个属性。
- 每属性一计数器：每迭代减一，至 0 解禁。
- 大邻域：只对候选子集演算、不必每步扫全邻域（可与 candidate list 结合）。
与邻域/逆移：禁忌针对的是「属性」在文献中有时对应「禁止逆移一定步数」；逆移的定义依赖编码（如 2-opt 的逆操作）。实现前应在问题说明里写清一条移动对应什么属性、逆移动对应何属性对。
渴望准则（Aspiration Criteria）
作用：在移动因禁忌被挡时，若该移动特别有价值，则允许破禁执行。否则禁忌表会机械地挡住全局最优邻域点，渴望避免这一情形。
经典准则（最常用）：若候选 s′ 满足 f(s′) < f(s⋆)（带出新历史最优），则允许即使对应移动属性仍在禁忌期也选用该步。这保证「有记录以来最好的解」不会被禁忌机械排除（在邻域能到达的前提下）。
其他常见变体（可组合使用、按问题调参）：
- 按目标渴望：f(s′) 优于某一参考阈值（如本阶段最佳、加惩罚后的评价）。
注：破禁时仍应更新禁忌表与 s⋆ 的规则与常规步一致，并在日志中区分「渴望步」与「普通过步」便于调参复现。
主循环（最小化示意）
以目标函数 f(s) 最小化叙述；与一次移动 m 可关联的属性记为 a（如边、对换对等）。禁忌表在实现上可视为：近期被禁止的属性及其剩余禁忌步数的集合。渴望条件见上节「渴望准则」；禁忌的进入与释放见上节「禁忌表」。
▶ 禁忌搜索主循环（单解、邻域 + 禁忌表）
1. 初始化
选定初始解 s，记历史最优 s⋆ ← s。禁忌结构置空。设定：邻域算子、tenure 或其区间、最大迭代/时间、与渴望相关的参数。
2. 邻域与筛选
自当前 s 得候选集 N(s)（可采样）。对候选移动 m 得 s′ = m(s)。若 m 的属性 a 仍处禁忌期，则 m 通常不入选，除非满足上文「渴望准则」中已写明的破禁条件。
3. 选择与移动
在可接受候选中依规则选一步（如：存在改进步则选最优改进；否则选最小增的恶化步）。执行移动，更新 s。
4. 更新禁忌与全局最优
将本步属性 a 入表，剩余步数置为 tenure（或自区间随机等变体，见上文「禁忌表」）。若 f(s) < f(s⋆)，令 s⋆ ← s。
5. 终止
达迭代/时间/无改进步数等，或触发重启；输出 s⋆。