一文搞懂什么是禁忌搜索算法Tabu Search【附应用举例】

69 阅读 0 评论 46 点赞

我是靠谱客的博主爱笑金针菇，最近开发中收集的这篇文章主要介绍一文搞懂什么是禁忌搜索算法Tabu Search【附应用举例】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Python代码链接放文末。

本文参考了很多张军老师《计算智能》的第十章知识。

本文来源：https://blog.csdn.net/qq_44186838/article/details/109181453

禁忌搜索算法

1.1 算法思想

禁忌搜索(Tabu Search, TS)也是属于模拟人类智能的一种优化算法。
在这里插入图片描述
上图涉及到了禁忌搜索中的一些基本概念，现在来对这些概念作解释。

禁忌表（Tabu List，TL）
是用来存放（记忆）禁忌对象的表。它是禁忌搜索得以进行的基本前提。禁忌表本身是有容量限制的，它的大小对存放禁忌对象的个数有影响，会影响算法的性能。

禁忌对象（Tabu Object，TO）
是指禁忌表中被禁的那些变化元素。禁忌对象的选择可以根据具体问题而制定。例如在旅行商问题（Traveling Salesman Problem，TSP）中可以将交换的城市对作为禁忌对象，也可以将总路径长度作为禁忌对象。

禁忌期限（Tabu Tenure，TT）
也叫禁忌长度，指的是禁忌对象不能被选取的周期。禁忌期限过短容易出现循环，跳不出局部最优，长度过长会造成计算时间过长。

渴望准则（Aspiration Criteria，AC）
也称为特赦规则。当所有的对象都被禁忌之后，可以让其中性能最好的被禁忌对象解禁，或者当某个对象解禁会带来目标值的很大改进时，也可以使用特赦规则。

1.2 基本流程

禁忌搜索算法在初始化的时候，在搜索空间随机生成一个初始解 i，禁忌表H置空，当前解i记为历史最优解 s，然后进入迭代的搜索过程。在每一次迭代中，都从当前的解i出发，在当前禁忌表H的限制下，构造出解i的邻域A，然后从A中选出适应值最好的解 j 来替换解 i，同时更新禁忌表H。在解 j 替换解 i 之后，如果解 i 的质量得到改善，那么历史最优的解 s 将被解 i 替换；否则，s 保持不变，即使解 i 虽然暂时变差了，但是由于扩大了搜索空间，仍有利于跳出局部最优。得到了新的当前解 i 之后，算法返回迭代的开始继续进行，直到找到最优解或者运行了一定的迭代次数等终止条件的时候结束算法。

基本流程图和伪代码如下：

在这里插入图片描述
1.3 应用举例

啥？上面听不懂？那麻烦给我点个赞，然后看一看下面的内容哈哈。

问题：已知一个旅行商问题为四城市（a，b，c，d）问题，城市间的距离如矩阵D所示，为方便起见，假设邻域映射定义为两个城市位置对换，而始点和终点城市都是a。请分析使用禁忌搜索算法求解该问题的前面三代的过程与主要步骤。
在这里插入图片描述

在开始求解之前我们先分析一下问题。

分析：这是一个简单的问题,利用枚举的方法也可以找到最优的答案，但是，找到答案不是我们的目的，我们主要是想通过一一个简单的例子来理解禁忌搜索是如何进行工作的。从距离矩阵D可以看到，这是一个非对称的TSP问题，但是这并不影响算法的执行。由于题目假设了邻域构造的方式，而且规定了始点和终点都是城市a，因此，在以下的求解过程中，我们不使用城市a和其他城市进行交换，这样的操作并不会影响全局寻优的能力。

求解：
在这里插入图片描述
注：在实际应用中，通过选择更高的禁忌对象，设置合理的禁忌期限，或者采用其他更好的的参数，都可以避免循环（反复出现同种情况的邻域值）的出现，提高算法的性能。