差分进化算法求解TSP问题的Python实现详解

2025年12月17日 互联网

差分进化算法求解TSP问题的Python实现详解

旅行商问题（TSP）是经典的组合优化难题，旨在寻找访问多个城市并返回起点的最短路径。传统方法如动态规划在规模较大时计算成本高昂，而差分进化算法（Differential Evolution, DE）作为一种基于群体智能的随机优化算法，通过变异、交叉和选择操作在解空间中高效搜索，尤其适合求解高维非线性问题。本文将结合Python实现，详细阐述如何利用DE算法求解TSP问题。

一、差分进化算法原理

差分进化算法通过模拟生物进化中的变异、交叉和选择机制，逐步优化候选解。其核心步骤包括：

  1. 初始化种群：随机生成一组初始解（个体），每个个体代表一个可能的TSP路径。
  2. 变异操作：对当前种群中的个体进行变异，生成变异向量。常见变异策略包括DE/rand/1、DE/best/1等，例如： 
    1. v_i = x_r1 + F * (x_r2 - x_r3)

    其中，x_r1、x_r2、x_r3为随机选择的个体，F为缩放因子（通常0.4~1.0）。

  3. 交叉操作：将变异向量与目标向量（当前个体）进行交叉，生成试验向量。交叉方式包括二项交叉、指数交叉等，例如二项交叉： 
    1. u_j = v_j if (rand() < CR or j == j_rand) else x_i,j

    其中，CR为交叉概率（通常0.1~1.0），j_rand为随机选择的维度。

  4. 选择操作：比较试验向量与目标向量的适应度（路径长度），保留更优的个体进入下一代。

二、TSP问题的DE算法实现

1. 问题建模与适应度函数

TSP问题的解是一个排列，表示城市访问顺序。适应度函数为路径总长度的倒数（或直接取负值），以便DE算法最大化适应度。例如：

  1. def calculate_distance(path, distance_matrix):
  2.     total_distance = 0
  3.     for i in range(len(path)-1):
  4.         total_distance += distance_matrix[path[i]][path[i+1]]
  5.     total_distance += distance_matrix[path[-1]][path[0]]  # 返回起点
  6.     return total_distance
  8. def fitness(path, distance_matrix):
  9.     return 1 / calculate_distance(path, distance_matrix)  # 适应度为距离的倒数

2. 种群初始化与变异策略

TSP的解是排列，需确保变异和交叉操作不破坏排列的合法性。常见方法包括：

  • 顺序交叉（OX）：保留部分排列顺序，填充剩余城市。
  • 交换变异：随机交换路径中的两个城市。
  • 逆序变异：随机选择一段子路径并逆序。

示例代码（交换变异）：

  1. import numpy as np
  3. def swap_mutation(path, mutation_rate):
  4.     if np.random.rand() > mutation_rate:
  5.         return path
  6.     i, j = np.random.randint(0, len(path), 2)
  7.     path_copy = path.copy()
  8.     path_copy[i], path_copy[j] = path_copy[j], path_copy[i]
  9.     return path_copy

3. 完整DE算法实现

结合上述操作，完整DE算法的Python实现如下：

  1. import numpy as np
  3. class DifferentialEvolutionTSP:
  4.     def __init__(self, distance_matrix, pop_size=50, F=0.8, CR=0.9, max_gen=1000):
  5.         self.distance_matrix = distance_matrix
  6.         self.pop_size = pop_size
  7.         self.F = F  # 缩放因子
  8.         self.CR = CR  # 交叉概率
  9.         self.max_gen = max_gen
  10.         self.num_cities = len(distance_matrix)
  12.     def initialize_population(self):
  13.         population = []
  14.         for _ in range(self.pop_size):
  15.             path = np.arange(self.num_cities)
  16.             np.random.shuffle(path)
  17.             population.append(path)
  18.         return population
  20.     def mutate(self, population):
  21.         mutated_population = []
  22.         for i in range(self.pop_size):
  23.             # 选择三个不同的个体
  24.             candidates = [x for idx, x in enumerate(population) if idx != i]
  25.             x_r1, x_r2, x_r3 = np.random.choice(candidates, 3, replace=False)
  27.             # DE/rand/1 变异策略
  28.             v = x_r1.copy()
  29.             j_rand = np.random.randint(0, self.num_cities)
  30.             for j in range(self.num_cities):
  31.                 if np.random.rand() < self.CR or j == j_rand:
  32.                     # 简单实现：直接交换（需改进为排列保持的变异）
  33.                     # 更优方案：使用顺序交叉或部分映射
  34.                     pass  # 此处需替换为排列保持的变异操作
  35.             mutated_population.append(v)
  36.         return mutated_population
  38.     # 更优的变异实现（示例：部分映射交叉）
  39.     def pmx_mutation(self, x_r1, x_r2):
  40.         size = len(x_r1)
  41.         a, b = np.random.randint(0, size, 2)
  42.         if a > b:
  43.             a, b = b, a
  44.         child = np.full(size, -1, dtype=int)
  46.         # 复制中间段
  47.         child[a:b+1] = x_r1[a:b+1]
  49.         # 填充剩余位置
  50.         for i in range(size):
  51.             if i < a or i > b:
  52.                 val = x_r2[i]
  53.                 while val in child[a:b+1]:
  54.                     pos = np.where(x_r1 == val)[0][0]
  55.                     val = x_r2[pos]
  56.                 child[i] = val
  57.         return child
  59.     def run(self):
  60.         population = self.initialize_population()
  61.         best_path = None
  62.         best_fitness = -np.inf
  64.         for gen in range(self.max_gen):
  65.             mutated_population = []
  66.             for i in range(self.pop_size):
  67.                 # 选择三个不同的个体
  68.                 candidates = [x for idx, x in enumerate(population) if idx != i]
  69.                 x_r1, x_r2, x_r3 = np.random.choice(candidates, 3, replace=False)
  71.                 # 使用部分映射交叉实现变异
  72.                 v = self.pmx_mutation(x_r1, x_r2)
  73.                 mutated_population.append(v)
  75.             # 交叉与选择
  76.             new_population = []
  77.             for i in range(self.pop_size):
  78.                 target = population[i]
  79.                 trial = mutated_population[i]
  81.                 # 二项交叉
  82.                 cross_points = np.random.rand(self.num_cities) < self.CR
  83.                 if not np.any(cross_points):
  84.                     cross_points[np.random.randint(0, self.num_cities)] = True
  86.                 trial_cross = trial.copy()
  87.                 for j in range(self.num_cities):
  88.                     if cross_points[j]:
  89.                         trial_cross[j] = trial[j]
  91.                 # 确保交叉后仍为合法排列（需额外处理）
  92.                 # 简化处理：直接比较适应度
  93.                 fitness_target = 1 / self.calculate_distance(target, self.distance_matrix)
  94.                 fitness_trial = 1 / self.calculate_distance(trial_cross, self.distance_matrix)
  96.                 if fitness_trial > fitness_target:
  97.                     new_population.append(trial_cross)
  98.                 else:
  99.                     new_population.append(target)
  101.                 # 更新全局最优
  102.                 if fitness_trial > best_fitness:
  103.                     best_fitness = fitness_trial
  104.                     best_path = trial_cross.copy()
  106.             population = new_population
  107.             if (gen+1) % 100 == 0:
  108.                 print(f"Generation {gen+1}, Best Distance: {1/best_fitness if best_fitness > 0 else 'N/A'}")
  110.         return best_path, 1/best_fitness
  112.     def calculate_distance(self, path, distance_matrix):
  113.         total = 0
  114.         for i in range(len(path)-1):
  115.             total += distance_matrix[path[i]][path[i+1]]
  116.         total += distance_matrix[path[-1]][path[0]]
  117.         return total

4. 优化建议与注意事项

  1. 变异策略选择：TSP问题需保持排列的合法性，推荐使用顺序交叉（OX）、部分映射交叉（PMX）或循环交叉（CX）。
  2. 参数调优：缩放因子F通常设为0.4~1.0，交叉概率CR设为0.1~1.0，需通过实验确定最优组合。
  3. 种群多样性：初期可增大种群规模（如100~200），后期逐步减小以加速收敛。

  4. 混合策略：结合局部搜索（如2-opt、3-opt）可显著提升解的质量。示例：

    1. def two_opt_swap(path, i, j):
    2.     new_path = path[:i] + path[i:j+1][::-1] + path[j+1:]
    3.     return new_path
    5. def local_search(path, distance_matrix, max_iter=100):
    6.     improved = True
    7.     best_path = path.copy()
    8.     best_dist = calculate_distance(best_path, distance_matrix)
    10.     for _ in range(max_iter):
    11.         improved = False
    12.         for i in range(len(best_path)-1):
    13.             for j in range(i+1, len(best_path)):
    14.                 new_path = two_opt_swap(best_path, i, j)
    15.                 new_dist = calculate_distance(new_path, distance_matrix)
    16.                 if new_dist < best_dist:
    17.                     best_path, best_dist = new_path, new_dist
    18.                     improved = True
    19.                     break
    20.             if improved:
    21.                 break
    22.         if not improved:
    23.             break
    24.     return best_path

三、性能对比与扩展应用

1. 与其他算法的对比

  • 遗传算法（GA）：DE的变异策略更灵活，收敛速度通常更快。
  • 蚁群算法（ACO）：ACO适合动态环境，但DE在静态问题中参数调整更简单。
  • 模拟退火（SA）：SA易陷入局部最优，DE通过群体进化避免此问题。

2. 扩展应用场景

  • 动态TSP：结合在线学习机制，适应实时变化的城市距离。
  • 多目标TSP：修改适应度函数为多目标加权和，求解带时间窗的TSP。
  • 大规模TSP：采用分布式DE或分层优化策略，提升可扩展性。

四、总结与展望

差分进化算法为求解TSP问题提供了一种高效、灵活的框架，尤其适合大规模或动态场景。通过合理设计变异和交叉操作，结合局部搜索优化，可显著提升解的质量。未来研究可聚焦于：

  1. 自适应参数调整机制，动态优化F和CR。
  2. 与深度学习结合，利用神经网络预测优质解区域。
  3. 并行化实现，充分利用多核或分布式计算资源。

开发者可根据实际需求调整算法参数和操作策略，平衡求解精度与计算效率，为物流、交通、制造等领域的路径优化问题提供可靠解决方案。

最新文章