禁忌搜索（Tabu search）
- 从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。
- 为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是
Tabu 表的建立。
- 标记已经解得的局部最优解或求解过程，并在进一步的迭代中避开这些局部最优解或求解过程。局部搜索的缺点在于，太过于对某一局部区域以及其邻域的搜索，导致一叶障目。为了找到全局最优解，禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它，从而或得更多的搜索区域。
相关概念
邻域
- 所谓邻域，简单的说即是给定点附近其他点的集合。邻域就是指对当前解进行一个操作（这个操作可以称之为邻域动作）可以得到的所有解的集合。
邻域动作
- 邻域动作是一个函数，通过这个函数，对当前解 s
，产生其相应的邻居解集合。
- 例如:对于一个 bool 型问题，其当前解为： s = 1001
，当将邻域动作定义为翻转其中一个 bit 时，得到的邻居解的集合 。
禁忌表
- 禁忌对象：由于需要避免一些操作的重复进行，就要将一些元素放到禁忌表中以禁止对这些元素进行操作，这些元素就是我们指的禁忌对象（通常指找到的局部最优解）。
- 禁忌长度：禁忌长度是被禁对象不允许选取的迭代次数。一般是给被禁对象 x
一个数（禁忌长度） t ，要求对象 x 在 t 步迭代内被禁，在禁忌表中采用
记忆，每迭代一步，该项指标做运算 ，直到 时解禁。
侯选集合
- 侯选集合由邻域中的邻居组成。常规的方法是从邻域中随机（或基于先验知识）选择若干个目标值作为最佳的邻居入选。
评价函数(目标函数)
- 评价函数是侯选集合元素选取的一个评价公式，侯选集合的元素通过评价函数值来选取。
特赦规则
- 在禁忌搜索算法的迭代过程中，会出现侯选集中的全部对象都被禁忌，或有一对象被禁，但若解禁则其目标值将有非常大的下降情况。在这样的情况下，为了达到全局最优，我们会让一些禁忌对象重新可选。这种方法称为特赦，相应的规则称为特赦规则。
具体算法
- 禁忌表 H = 空集，并选定一个初始解 ；
- 在 的邻域 中选择候选集 ，并且在候选集 中选一个评价值最佳的解 ;
-
不在禁忌表中，选为当前解
-
在禁忌表中，满足破禁条件，
为当前解，否则从不在禁忌表解中，选择一个最优解
- 重复 2 ，直到满足停止条件。
具体实例
求下图的旅行商回路
- 随机选择一个城市序列：21543 ，路径长度 889
选择的最优交换策略，放入禁忌表中
- 最优访问顺序：25143 ，最优长度 804
当前访问顺序：25143 ， 长度 804
尽管
是候选集中的最优策略，但上一步已经置入禁忌表了，这次选择次优解。
- 最优访问顺序：25143 ，最优长度 804
当前访问顺序：25413 ， 长度 928
- 最优访问顺序：23415 ，最优长度 786
当前访问顺序：23415 ， 长度 786
- 最优访问顺序：24315 ，最优长度 768
当前访问顺序：24315 ， 长度 768
此处特赦规则是目前长度比历史最优长度都要好。
迭代 5 次最优访问顺序：21345 ，最优长度 737
