什么是 TABU 搜索？

禁忌搜索是一种用于解决优化问题的元启发式算法。它的名字来源于阿拉伯语“tabu”，意为任何被禁止的东西。通过维护搜索过程的短期记忆，并利用这些知识将搜索引向有希望的区域，禁忌搜索能够有效地探索解空间。

算法从一个解开始，通过进行某些调整或修改来迭代地检查周围的解。它根据当前问题的特定目标函数或评估标准来评估每个邻居的质量。目标是选择最优解或最大化特定的目标函数。

使用禁忌列表是禁忌搜索的一个显著特征。这个列表跟踪最近使用的移动或转换，从而阻止搜索回到已访问过的确切解或陷入循环。禁忌列表确保了多样化的搜索过程，从而能够探索更大的解空间。

除了禁忌列表，禁忌搜索还采用了其他几种方法来有效地指导搜索过程。这些方法包括利用潜在位置的强化方法、鼓励探索解空间其他区域的多样化策略，以及允许在某些情况下执行特定禁忌移动的雄心标准。

禁忌搜索方法可以用来解决各种优化问题，包括组合优化、调度问题和路由问题。其有效性在于它能够平衡探索和利用，使其能够在具有挑战性和复杂的搜索环境中提供高质量的结果。

在禁忌搜索中，明确的记忆有两个目的，如下所示：

• 防止搜索重复访问已访问过的解。
• 探索解空间的未访问区域。

禁忌搜索通过解决不同领域的优化问题来解决。它是一种灵活的方法，当需要确定最佳答案或优化特定目标函数时，可以将其用于解决各种问题。以下是一些禁忌搜索的常见用途：

最优组合设计

• 旅行商问题 (TSP) 涉及确定一名推销员访问多个地点时所需的最快路线。
• 车辆路径问题 (VRP) 是指选择最佳路线，让车辆车队提供产品或服务。
• 背包问题是指从有限数量的物品中选择具有最大价值的子集。

时间表和调度

• 作业车间调度是指选择机器上的活动顺序，以最大限度地提高生产效率。
• 将任务和资源分配给项目，以实现截止日期并降低成本。
• 考试调度：在考虑了考场可用性和学生偏好等限制的情况下，为学生规划考试。

路由和网络问题

• 网络设计：选择最佳的网络基础设施配置或架构，以节省成本或提高性能。
• 设施选址：为了节省运输成本，确定设施（如配送中心或仓库）的最佳位置。
• 网络路由：网络路由是指在考虑各种限制的情况下，找到数据、产品或服务在网络中流动的最佳路径或路线。

图论和图着色

• 图着色：图着色涉及为每个顶点分配不同的颜色，以便没有两个相邻的顶点具有相同的颜色。
• 最大团问题：找到图中每个顶点对都相连的最大顶点集合是最大团问题。

约束满足问题

• 八皇后问题：找到一种在棋盘上放置八个皇后而不相互威胁的方法。
• 数独：根据设定的规则和限制，用数字填充 9x9 网格。

使用禁忌搜索的好处

• 有效地探索解空间，使算法能够避免局部最优。
• 灵活且能够适应各种优化问题。
• 可以处理离散、组合和受限问题。
• 基于记忆的技术可确保有效地利用搜索历史。
• 通常能及时提供高质量的答案。

局限性和需要考虑的事项

• 问题特征和参数选择对禁忌搜索的性能有显著影响。
• 解空间的大小和评估函数的复杂性可能会影响搜索的效率。
• 对于某些问题，选择合适的邻域结构可能很困难。
• 虽然禁忌搜索不总是能产生最佳结果，但它通常能产生高质量的结果。

禁忌搜索已被用于解决物流、制造、电信和调度等各个领域的众多实际优化问题。由于其在探索和利用解空间方面的有效性，它在优化领域的学者和从业者中是一个受欢迎的选择。

如何使用禁忌搜索来改进算法？

使用有限的迭代次数和禁忌列表，通过禁忌搜索方法优化解，以发现最佳解，该解可最小化给定初始解的目标函数的适应度值。

通过用目标函数评估它们的适应度，并使用邻域函数创建附近的解，代码使用禁忌搜索来反复研究解。它避免返回到以前研究过的替代方案，而是使用禁忌列表在设定的迭代次数后找到具有最低适应度的最佳解。

代码

输出

Best Solution: ['A', 'B', 'C', 'D', 'E']
Total Distance: 19

说明

上面代码中实现的禁忌搜索算法解决了旅行商问题 (TSP)。TSP 是一个著名的优化问题，其目标是确定一名推销员访问多个城市并返回起始位置的最快路线。

代码的第一行定义了 TSP 问题数据，包括城市列表及其各自的距离。禁忌期限（一个移动保持禁忌状态的迭代次数）和最大迭代次数被配置为禁忌搜索参数。

该方法开始时，将初始最佳解设置为当前解，并随机初始化当前解。由 evaluate() 函数确定特定解覆盖的总距离。

主要的禁忌搜索循环通过交换当前解中的两个城市来反复创建邻域解。它评估每个邻域解的适应度（总距离）。它选择不在禁忌列表上且适应度等级高于当前最佳解的最佳邻域解。

如果最佳邻域解比当前最佳解更优，则将当前解更新为最佳邻域解，并将最佳解更新。如果禁忌列表的长度超过禁忌期限，则将移动（邻域解）添加到禁忌列表中，并删除最旧的移动。

循环将继续运行，直到达到最大迭代次数。然后生成最佳解及其覆盖的距离。