禁忌搜索算法详解（含算法示例）

谁践踏了优雅 2022-11-21 09:28 242阅读 0赞

# 1.算法简介 #

禁忌搜索算法TS（Tabu Search）是由美国科罗拉多州大学的Fred Glover教授在1986年左右提出来的，是一个用来跳出局部最优的搜寻方法。

禁忌搜索是一种亚启发式随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向。

TS是人工智能的一种体现，是局部领域搜索的一种扩展。禁忌搜索是在领域搜索的基础上，通过设置禁忌表来禁忌一些已经历的操作，并利用藐视准则来奖励一些优良状态，其中涉及**邻域 、禁忌表、禁忌长度、候选解、藐视准则**等影响禁忌搜索算法性能的关键因素。迄今为止，TS算法在组合优化等计算机领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。

# 2.算法流程框架 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70_pic_center]  
注：  
特赦（藐视）原则  
（1）基于评价值的规则，若出现一个解的目标值好于前面任何一个最佳候选解，可特赦；  
（2）基于最小错误的规则，若所有对象都被禁忌，特赦一个评价值最小的解；

# 3.算法示例 #

示例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70_pic_center 1]  
禁忌对象为分量的变化，也就是交换两个城市，禁忌长度初始设置为3：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70_pic_center 2]  
第一步可以看出对换CD评价值最小，因此将其放到禁忌表中，将该解作为当前解：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70_pic_center 3]  
第二步，可以看出此时对换BC评价值最小，因此将BC放入禁忌表，将该解作为当前解。注意此处禁忌对象及长度表示的理解如下：  
![在这里插入图片描述][2020110416221352.png_pic_center]  
对于第一行有3个正方形表示A可以和BCD进行对换，以此类推，对于CD（右下角）标注为3表示此时禁忌对象为CD，禁忌长度是3，后面在添加禁忌对象时就让其减一，进而可以表示进入禁忌表的顺序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70_pic_center 4]  
第三步，由于CD和BC以及被禁忌掉，所以此时BD作为禁忌对象，并以该解作为当前解。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70_pic_center 5]  
此时由于禁忌表已经满了，此时满足藐视准则，将BD替换掉最早进入禁忌表的解CD，同时以该解作为当前解。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70_pic_center 6]

# 4.算法实际应用时的注意点 #

经过上面的示例，可以看出：  
**禁忌表的主要指标**（两项指标）

*  禁忌对象：禁忌表中被禁的那些变化元素
 *  禁忌长度：禁忌的步数

对于**禁忌对象的选取**有以下三种形式：

1.  解的简单变化：对于上述TSP问题而言，例如：ABCD、BACD等
2.  解的分量的变化：也就是上述示例的形式
3.  目标值的变化：对于上述TSP问题，也就是总路径的长度

**候选集合的确定**  
（1）从邻域中选择若干目标值最佳的邻居入选；  
（2）随机选取。  
**评价函数**  
（1）直接评价函数，通过目标函数的运算得到评价函数；  
（2）间接评价函数，构造其他评价函数替代目标函数，应反映目标函数的特性，减少计算复杂性。

**记忆频率信息**  
根据记忆的频率信息（禁忌次数等）来控制禁忌参数（禁忌长度等）。  
例如：  
如果一个元素或序列重复出现或目标值变化很小，可增加禁忌长度以避开循环；  
如果一个最佳目标值出现频率很高，则可以终止计算认为已达到最优值。  
**终止规则**  
（1）确定步数终止，优点是易于操作和控制时间，但无法保证解的效果，应记录当前最优解；  
（2）频率控制原则，当某一个解、目标值或元素序列的频率超过一个给定值时，终止计算；  
（3）目标控制原则，如果在一个给定步数内，当前最优值没有变化，同规则2，可终止计算。

其它较优文章（含代码示例）  
https://blog.csdn.net/zuochao\_2013/article/details/72292466  
https://blog.csdn.net/tyhj\_sf/article/details/54235550

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/b51b2b29632844caae19a00ff60ddf8b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/9d3327cae96d416daba81e1d346ceaf8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/12cd22532c8242c29f5000e810649a70.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/ef1e92d3ac28449293ba6c75d13f4bb5.png
[2020110416221352.png_pic_center]: /images/20221120/2ebab52a8ade4440a85be7b07671e29e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/cbbe5e51d9f048028ae854475c69d4df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221120/3e1c9407755c4f7c9f5d94eb128a26be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221120/e48e7e46da0348a5a94fc5c421fcc1e0.png