复杂结构解析算法7：禁忌搜索算法

casjxm

禁忌搜索算法（Tabu Search, TS）是一种基于局部搜索的元启发式算法，由Fred Glover于1986年提出。它通过引入禁忌表（Tabu List）来避免重复搜索和陷入局部最优，从而在解空间中高效地寻找全局最优解。禁忌搜索算法广泛应用于组合优化问题，如旅行商问题（TSP）、作业车间调度、车辆路径问题（VRP）等。

核心思想
禁忌搜索算法的核心思想是通过禁忌表和特赦准则来引导搜索过程：

• 局部搜索：从当前解出发，在其邻域中寻找更优的解。
• 禁忌表：记录最近访问过的解或移动，禁止在一定步数内重复访问，以避免陷入循环。
• 特赦准则：当某个被禁忌的解优于当前最优解时，允许突破禁忌，接受该解。
• 多样化策略：通过引入扰动或重启机制，增加搜索的多样性，避免过早收敛。
  

关键操作

• 初始解生成：随机生成或通过启发式方法生成初始解。
• 邻域解生成：在当前解的邻域中生成一组候选解。
• 禁忌表管理：将最近访问的解或移动加入禁忌表，禁止在禁忌步数内重复访问。
• 特赦准则：如果某个被禁忌的解优于当前最优解，则接受该解。
• 更新当前解：从候选解中选择一个未被禁忌或满足特赦准则的解作为新的当前解。
• 迭代：重复上述步骤，直到满足终止条件。
  

算法流程

• 初始化：生成初始解 x0x0​，初始化禁忌表和最优解。
• 迭代优化：
  

生成当前解的邻域解。
根据禁忌表和特赦准则选择新解。
更新禁忌表和当前解。
如果新解优于当前最优解，则更新最优解。

• 终止：当达到最大迭代次数或满足其他终止条件时，输出最优解。
  

参数设置

• 禁忌表大小：控制禁忌表的长度，通常设置为问题规模的函数。
• 禁忌步数：控制解或移动在禁忌表中的保留时间。
• 邻域生成策略：根据问题特点设计邻域生成方法，例如在TSP中可以通过交换两个城市生成邻域解。
• 特赦准则：允许突破禁忌的条件，通常基于目标函数值。
• 多样化策略：通过扰动或重启机制增加搜索多样性。
  

应用领域

• 组合优化：如旅行商问题（TSP）、背包问题等。
• 调度问题：如作业车间调度、资源分配等。
• 车辆路径问题（VRP）：优化车辆配送路径。
• 机器学习：如特征选择、参数优化等。
• 工程设计：如电路设计、结构优化等。
  

优点

• 全局搜索能力强：通过禁忌表和特赦准则，能够有效避免陷入局部最优。
• 灵活性高：可以根据问题特点设计邻域生成策略和禁忌表管理方法。
• 易于与其他算法结合：可以与遗传算法、模拟退火等算法结合，提高搜索效率。
  

缺点

• 参数敏感：禁忌表大小、禁忌步数等参数需要仔细调整。
• 计算复杂度高：在大规模问题中，邻域解生成和禁忌表管理可能较耗时。
• 收敛速度慢：在复杂问题中，可能需要较多迭代才能找到最优解。
  

示例：求解旅行商问题（TSP）
以求解TSP为例，禁忌搜索算法的步骤如下：

• 初始化：生成初始路径，初始化禁忌表和最优路径。
• 迭代优化：
  

生成当前路径的邻域路径（如通过交换两个城市）。
根据禁忌表和特赦准则选择新路径。
更新禁忌表和当前路径。
如果新路径优于当前最优路径，则更新最优路径。

• 终止：当达到最大迭代次数时，输出最优路径。
  

总结
禁忌搜索算法通过引入禁忌表和特赦准则，具有较强的全局搜索能力和灵活性，适用于组合优化和调度问题。尽管存在参数敏感和计算复杂度高的缺点，但通过合理设计邻域生成策略和禁忌表管理方法，禁忌搜索算法能够有效解决复杂的实际问题。

代码示例（Python）

import random

def distance(city1, city2):
    return ((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2)**0.5

def total_distance(path, cities):
    return sum(distance(cities[path], cities[path[i + 1]]) for i in range(len(path) - 1))

def generate_neighbor(path):
    i, j = random.sample(range(len(path)), 2)
    neighbor = path.copy()
    neighbor, neighbor[j] = neighbor[j], neighbor
    return neighbor

def tabu_search(cities, max_iterations, tabu_size):
    # 初始化
    current_path = list(range(len(cities)))
    random.shuffle(current_path)
    best_path = current_path.copy()
    best_distance = total_distance(best_path, cities)
    tabu_list = []
   
    for iteration in range(max_iterations):
        # 生成邻域解
        neighbors = [generate_neighbor(current_path) for _ in range(10)]
        
        # 选择最佳邻域解
        best_neighbor = None
        best_neighbor_distance = float('inf')
        for neighbor in neighbors:
            if neighbor not in tabu_list:
                neighbor_distance = total_distance(neighbor, cities)
                if neighbor_distance < best_neighbor_distance:
                    best_neighbor = neighbor
                    best_neighbor_distance = neighbor_distance
        
        # 更新当前解
        if best_neighbor:
            current_path = best_neighbor
            tabu_list.append(best_neighbor)
            if len(tabu_list) > tabu_size:
                tabu_list.pop(0)
        
        # 更新最优解
        if best_neighbor_distance < best_distance:
            best_path = best_neighbor
            best_distance = best_neighbor_distance
   
    return best_path, best_distance

# 参数设置
cities = [(random.random(), random.random()) for _ in range(20)]  # 随机生成20个城市
max_iterations = 1000
tabu_size = 10

# 运行算法
best_path, best_distance = tabu_search(cities, max_iterations, tabu_size)
print(f"Best path: {best_path}, Best distance: {best_distance}")