《ERP高级计划》书的解读－APS算法之六禁忌搜索TS（上）（蔡颖）

禁忌搜索Tabu Search (TS)：它的算法是创立一初始化的方案 ；基于初始化的方案 ，算法“移动” 到一相邻的方案 。一般来说，许多移动是连续的过程，方案的质量被提高。 一个禁忌 tabu 清单被用于指导搜寻 ，当一特殊的中断条件达到时，算法就结束。 (如. 当运行时间已经达到时)，它是(确定性) 搜寻算法。

它和基因算法GA不同是, 禁忌TS，它是(确定性) 搜寻算法，试图找到一组合优化问题的最佳方案。但是，它的算法也还是包括随机取样的方法。

禁忌搜索TS: 基本概念：它的约束搜寻是由它的移动禁止的分类条件来进行的  (如, tabu)。

爬山探索”“ (对最小化问题)

1.      选择初始化方案 x

2.      选择一些移动s(x) 如下

目标函数值 s(x) < 目标函数值 x

如果没有移动存在，那么x 就是最佳的，方法停止。否者 ,

1. 让 x := s(x)

及回到第二步  2.

它是非常简单的探索 ，其缺点是：局部优化，也许不是全局的优化。 

禁忌搜索TS 特点：

l      它的约束搜寻是由它的移动禁止的分类条件来进行的   

l       是由一“遗忘策略”提供的短期记忆函数来自由搜索。

熟悉分类的方法：爬山探索, 从它们的开始点到一个本地优化采取单向的前进。  (在前后最小化里, 山是“倒置”以致于爬山的方向是向下的。)

在一组合问题里，爬山过程的主要限制：在开始点得到本地优化，当没有提高的移动是可能的时候，也许不是一个全局优化。

爬山探索不能保证一个全局的优化。 =>禁忌搜索TS 向导就像一个探索连续 探险。由于没有提高移动，就不会成为困惑，也不会落后到一个先前出现本地优化。

爬山法：

依赖于初始方案和移动的定义“爬山探索”可以找到最佳方案，但是，大部分情况下，它总是局部优化。

1，选择初始化方案 x  和让 x* := x. 设置重复计数 k := 0, and 开始用一个空的tabu 清单.

2，邻近的决策方案和选择最佳方案:
如果删除所有的禁忌, 那么就去第四步4.
否则设置 k := k+1 and 选择最佳的可能的移动用相应的事先定义好的评估函数

3，检查, 是否从第二步改善目前最佳目标函数值：
如果是真，那么让 x* := x.

4，检查, 是否中断条件达到:
如果一个选择迭代次数已经占用，或是在整个，或是因为 x* 是最后的改善, 或如果所有移动被禁止，在从第二步直接达到这一步时，或如果运行时间被消耗，停止。 x* 是最好的方案.
　

否则, 更新tabu清单 and 回到第二步2.

l      本地搜索算法的组合（如爬山探索）用禁忌tabu 清单来克服局部优化。

l      禁忌清单tabu使用，提供“约束搜索”的方法。方案的产生关键依赖于禁忌清单的组成内容和第4步的更新方法。

l      对局部优化的条件没有参照的方法，除非指明那里是局部优化在先前找到的最佳方案上的提高。一个“最好”的移动（而不是提高移动），在每一步被选择，在评估函数里嵌入使用条件。

l      3个重要方面：

1，评估函数的定义：

第二步的每一执行移动，从当前的方案x  到一相邻的方案，产出最大的提高－或, 缺少提高的可能性, 最小化的没有提高。在目标里，以允许只有非禁忌移动的限制为条件。

2，更新禁忌 tabu清单

使用禁忌清单的主要目标是避免回到先前的方案状态。 禁忌 tabu清单是以移动集合，，在最后最近搜索过程中迭代次数里，可以“倒退”（或undo) 一个移动

3，中断条件

这里：迭代次数 (要么整个，要么提高步骤), 或运行时间.

（待续）

本文由作者向AMT提供
蔡颖 专栏