禁忌搜索算法-关键操作与原则
目录
1 禁忌搜索
1.1 禁忌对象的选取
1.2 注意事项
2 禁忌长度
2.1 禁忌长度的选取
2.2 特赦（藐视）原则(Aspiration criteria)
3 候选集合
4 评价函数
5 终止规则
1 禁忌搜索
禁忌搜索（Tabu search）是局部搜索算法的推广，禁忌是禁止重复前面的工作，有助于跳出局部最优点。
禁忌长度：禁忌的步数
禁忌对象：禁忌表中被禁的那些变化元素（被禁用了以后，该对象需要等待几轮【步长】才能继续使用）
1.1 禁忌对象的选取
- 禁忌对象为简单的解变化：相同的解不能连续出现
- 禁忌对象为分量变化：同样的操作不能连续出现，比如调换B和D位置
- 禁忌对象为目标值变化：同一个目标值不能连续出现
1.2 注意事项
解的简单变化比解的分量变化和目标值变化的受禁范围要小，可能造成计算时间的增加，但也给予了较大的搜索范围。解分量的变化和目标值变化的禁忌范围大，减少了计算时间，可能导致陷在局部最优点。
2 禁忌长度
- 禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出；
- 禁忌长度过长，造成计算时间较大，也可能造成计算无法继续下去。
2.1 禁忌长度的选取
- t 可以为常数，易于实现；（t不动）
-
，t 是可以变化的数，tmin和tmax是确定的。（t动，边界不动）
- tmin和tmax根据问题的规模确定，t 的大小主要依据实际问题、实验和设计者的经验。
- tmin和tmax的动态选择。（边界动）
2.2 特赦（藐视）原则(Aspiration criteria)
- 基于评价值的规则，若出现一个解的目标值好于前面任何一个最佳候选解，可特赦；
- 基于最小错误的规则，若所有对象都被禁忌，特赦一个评价值最小的解；
- 基于影响力的规则，可以特赦对目标值影响大的对象。
3 候选集合
- 从邻域中选择若干目标值最佳的邻居入选；
- 在邻域中的一部分邻居中选择若干目标值最佳的状态入选；
- 随机选取；
4 评价函数
- 直接评价函数，通过目标函数的运算得到评价函数；
- 间接评价函数，构造其他评价函数替代目标函数，应反映目标函数的特性，减少计算复杂性。
5 终止规则
- 确定步数终止，无法保证解的效果，应记录当前最优解；
- 频率控制原则，当某一个解、目标值或元素序列的频率超过一个给定值时，终止计算；
- 目标控制原则，如果在一个给定步数内，当前最优值没有变化，可终止计算；
