什么是 TABU 搜索？

塔布TABU搜索是一种用于解决优化问题的元启发式算法。其名称源于阿拉伯语 "Tabu"，表示任何被禁止的事物。通过保持搜索过程的短期记忆，并利用这些知识将搜索引向有希望的区域，塔布搜索可以有效地探索解空间。

该算法从一个答案开始，通过进行某些调整或修改，反复检查周围的解决方案。它根据目标函数或当前问题的特定评估标准来评估每个相邻方案的质量。目标是选择最佳解决方案或最大化特定目标函数。

使用 tabu 列表是 tabu 搜索的显著特征之一。该列表记录了最近使用过的移动或变换，可以防止搜索返回到精确的解决方案或陷入循环。塔布列表确保了搜索过程的多样性，从而能够探索更大的解决方案空间。

除了塔布列表，塔布搜索还采用了其他几种方法来成功引导搜索过程。这些方法包括利用潜在位置的强化方法、促进对解决方案空间其他部分进行研究的多样化策略，以及允许在某些情况下执行特定塔布行动的目标标准。

塔布搜索法可用于解决各种优化问题，包括组合优化、调度问题和路由问题。它的功效来自于在探索和利用之间取得平衡的能力，使其即使在具有挑战性和复杂的搜索环境中也能提供高水准的结果。

在塔布搜索中，显式内存的使用有以下两个目的：

  • 防止搜索再次出现已访问过的解决方案。
  • 探索解决方案空间中未访问过的区域。

在许多不同的领域，优化问题都是通过塔布搜索来解决的。当需要确定最佳答案或优化特定目标函数时，这种灵活的方法可用于解决各种问题。

以下是 tabu 搜索的一些常用方法：

优化组合设计：

  • 旅行推销员问题 (Travelling Salesman Problem，TSP) 涉及确定推销员访问多个地方的最快路径。
  • 为提供产品或服务的车队选择最佳路线被称为车辆路由问题（VRP）。
  • 从有限的物品中选择一个最有价值的子集，被称为 "knapsack 问题"。

时间安排和调度：
  • 选择机器上的活动顺序以最大限度地提高生产效率被称为作业车间调度。
  • 为项目分配责任和资源，以实现最后期限和削减开支。
  • 考试安排：在考虑到教室可用性和学生偏好等限制因素的情况下，为学生规划考试。

路由和网络问题：

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

图形理论和图形着色
  • 图形着色：给图着色就是给每个顶点涂上不同的颜色，使相邻的两个顶点没有相同的颜色。
  • 最大簇问题：最大簇问题是在图中寻找最大的顶点群，其中每对顶点都是相连的。

约束满足问题
  • 八个皇后想办法在棋盘上排列八个皇后，同时又不互相伤害。
  • 数独：根据设定的规则和限制在 9x9 的网格中填入数字。

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

局限性和需要考虑的问题：
  • 问题特征和参数选择会对塔布搜索的性能产生重大影响。
  • 解决方案空间的大小和评估函数的复杂程度都会影响搜索的效果。
  • 对于某些问题，选择合适的邻域结构可能会比较困难。
  • 虽然塔布搜索并不总是能产生最佳结果，但它经常能产生最佳结果。

在物流、制造、电信和调度等不同学科中，许多现实世界中的优化问题都是通过 tabu 搜索解决的。由于塔布搜索能有效地探索和利用求解空间，因此深受优化领域的学者和从业人员的青睐。

如何使用塔布搜索改进算法？
利用有限的迭代次数和塔布列表，使用塔布搜索法优化解决方案，以发现能降低给定起始解决方案的目标函数适配值的最佳解决方案。

通过使用目标函数评估它们的合适度，并使用邻域函数创建接近的解决方案，该代码使用塔布搜索反复研究解决方案。它避免回到之前研究过的备选方案，而是使用塔布列表在设定的迭代次数后找到适配度最低的最佳解决方案。

import random  
  
# Define the TSP problem data  
cities = ["A", "B", "C", "D", "E"]  
distances = {  
    "A": {"A": 0, "B": 5, "C": 9, "D": 10, "E": 6},  
    "B": {"A": 5, "B": 0, "C": 4, "D": 8, "E": 7},  
    "C": {"A": 9, "B": 4, "C": 0, "D": 3, "E": 2},  
    "D": {"A": 10, "B": 8, "C": 3, "D": 0, "E": 1},  
    "E": {"A": 6, "B": 7, "C": 2, "D": 1, "E": 0}  
}  
  
# Tabu Search Parameters  
tabu_list = []  
tabu_tenure = 5  
max_iterations = 100  
  
# Initialize the current solution  
current_solution = random.sample(cities, len(cities))  
best_solution = current_solution.copy()  
  
# 评估解决方案的合适度（总距离）  ；
def evaluate(solution):  
    total_distance = 0  
    for i in range(len(solution)):  
        current_city = solution[i]  
        next_city = solution[(i + 1) % len(solution)]  
        total_distance += distances[current_city][next_city]  
    return total_distance  
  
# Main Tabu Search Loop  
iteration = 0  
while iteration < max_iterations:  
    生成邻近解决方案  ；
    neighbors = []  
    for i in range(len(current_solution)):  
        for j in range(i + 1, len(current_solution)):  
            通过交换两个城市，创建一个邻居解决方案  ；
            neighbor = current_solution.copy()  
            neighbor[i], neighbor[j] = neighbor[j], neighbor[i]  
            neighbors.append(neighbor)  
  
    # 评估邻近解决方案，选择最佳解决方案；
    best_neighbor = None  
    best_fitness = float('inf')  
    for neighbor in neighbors:  
        # 评估相邻解决方案的适配性  ；
        fitness = evaluate(neighbor)  
        # 检查邻解是否不在 tabu 列表中，并且具有更好的适配性  ；
        if neighbor not in tabu_list and fitness < best_fitness:  
            best_neighbor = neighbor  
            best_fitness = fitness  
  
    # 更新当前最佳解决方案  ；
    current_solution = best_neighbor  
    if best_fitness < evaluate(best_solution):  
        best_solution = best_neighbor  
  
    将移动添加到 tabu 列表  ；
    tabu_list.append(best_neighbor)  
    if len(tabu_list) > tabu_tenure:  
        # 将最老的从tabu列表中删除  ；
        tabu_list.pop(0)  
  
    iteration += 1  
  
# Output the best solution found  
print("Best Solution:", best_solution)  
print("Total Distance:", evaluate(best_solution))  

Output:

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

旅行推销员问题（TSP）是利用上述代码中的塔布搜索算法解决的。旅行推销员问题是一个著名的优化问题，其目标是确定推销员访问多个城市并返回起始地点的最快路径。

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

该方法首先将初始最佳解设为当前解，并随机初始化当前解。特定解所覆盖的整个距离由 evaluate() 函数决定。

主要的塔布搜索循环通过交换当前解决方案中的两个城市，反复创建相邻解决方案。它评估每个相邻解决方案的适配度（总距离）。它会选择不在塔布搜索列表上，且适配度高于当前最佳解决方案的最佳相邻解决方案。

用最佳邻解更新当前解，如果最佳邻解比当前最佳解更合适，则更新最佳解。移动（邻解）会被添加到 tabu 列表中，如果 tabu 列表比 tabu 任职期长，则会淘汰最老的移动。

在达到最大迭代次数之前，循环将一直运行。然后生成最佳解决方案及其覆盖距离。