反应式禁忌搜索（RTS）

Goat_Yang2026/3/21约 1911 字大约 6 分钟

反应式禁忌搜索（RTS）

名称

反应式禁忌搜索（Reactive Tabu Search, RTS）

策略

禁忌搜索基础

反应式禁忌搜索建立在禁忌搜索的核心原理之上。禁忌搜索是一种基于局部搜索的优化算法。该算法通过在当前解与其邻域解之间迭代移动来探索解空间，即使该移动会导致目标函数值变差，也可能被接受。为了防止搜索重复访问近期探索过的解并陷入局部最优，禁忌搜索维护一个禁忌表，用于存储在一定迭代次数内被禁止的移动或解属性。

反应式机制

反应式禁忌搜索的关键特征在于引入了反应式机制，该机制能够依据搜索历史和问题景观特征动态调整搜索参数。这些机制旨在提升算法对不同问题实例的适应能力，并平衡搜索过程中的探索与开发。

在反应式禁忌搜索中，反应式机制通常包括对禁忌表长度和特赦准则（aspiration criteria）的调整。禁忌表长度决定某一移动或解属性保持禁忌状态的迭代次数，而特赦准则允许算法在某一禁忌移动能够产生优于当前已知最优解的目标函数值时，忽略其禁忌状态并予以接受。

基于反馈的参数自适应

反应式禁忌搜索采用反馈机制，根据搜索进展对搜索参数进行自适应调整。算法会监控搜索历史，并收集关于已访问解质量、解循环出现频率以及搜索多样化程度等信息。

基于这些反馈信息，算法动态调整禁忌表长度和特赦准则。当搜索停滞于局部最优，或在先前访问过的解之间发生循环时，算法会增大禁忌表长度，以促进搜索多样化并鼓励探索解空间中的新区域。相反，当搜索持续找到改进解时，算法会减小禁忌表长度，以加强对有前景区域的深入搜索。

过程

数据结构

当前解（current_solution）：当前正在探索的解。
最优解（best_solution）：迄今为止找到的最优解。
禁忌表（tabu_list）：禁忌移动或禁忌解属性的列表。
搜索历史（search_history）：已访问解及其目标函数值的记录。

参数

最大迭代次数（max_iterations）：允许执行的最大迭代次数。
初始禁忌长度（initial_tabu_tenure）：禁忌长度的初始值。
最小禁忌长度（min_tabu_tenure）：允许的最小禁忌长度。
最大禁忌长度（max_tabu_tenure）：允许的最大禁忌长度。
特赦阈值（aspiration_threshold）：用于覆盖禁忌状态的特赦阈值。

反应式禁忌搜索算法

初始化：

生成一个初始解，并将其设为 current_solution 和 best_solution。
将 tabu_list 初始化为空。
将 tabu_tenure 设为 initial_tabu_tenure。

当停止准则未满足时（例如尚未达到 max_iterations）：
1. 生成一组候选邻域解。
2. 计算每个候选解的目标函数值。
3. 选择最优的候选解，要求其要么不在 tabu_list 中，要么满足特赦准则。
4. 用所选候选解更新 current_solution。
5. 若 current_solution 优于 best_solution，则更新 best_solution。
6. 将所选移动或解属性加入 tabu_list。
7. 若 tabu_list 的大小超过 tabu_tenure，则移除其中最早加入的条目。
8. 用 current_solution 及其目标函数值更新 search_history。
9. 根据搜索历史调整 tabu_tenure：
- 若搜索停滞于局部最优或检测到循环，则增大 tabu_tenure（但不超过 max_tabu_tenure）。
- 若搜索持续找到改进解，则减小 tabu_tenure（但不低于 min_tabu_tenure）。
返回找到的 best_solution。