差分进化算法在TSP问题中的Python实现与英文解析

2025年12月16日 互联网

差分进化算法在TSP问题中的Python实现与英文解析

一、差分进化算法（DE）概述

差分进化算法（Differential Evolution, DE）是一种基于群体智能的随机优化算法，通过模拟生物进化中的变异、交叉和选择机制，在连续或离散空间中搜索全局最优解。其核心思想是通过差分向量（即个体间的差异）生成新解，并通过贪心选择保留更优个体。

1.1 算法特点

  • 自适应性强：无需预设参数（如步长、交叉概率），通过群体协作动态调整搜索方向。
  • 全局收敛性：通过变异和交叉操作避免陷入局部最优。
  • 简单易实现：仅需定义目标函数和个体表示方式，即可适配不同问题。

1.2 英文术语解析

  • Differential Evolution (DE): 差分进化算法。
  • Population: 种群，即候选解的集合。
  • Mutation: 变异操作，生成新解的核心步骤。
  • Crossover: 交叉操作，混合父代与变异解的信息。
  • Selection: 选择操作，保留适应度更高的解。
  • Fitness Function: 适应度函数，用于评估解的优劣。

二、TSP问题与差分进化算法的适配

旅行商问题（TSP）是经典的组合优化问题，目标是找到访问所有城市并返回起点的最短路径。传统DE算法设计用于连续空间优化，而TSP的解是离散的排列（Permutation），因此需对DE进行以下适配：

2.1 个体表示

将TSP的解表示为城市排列（如[0, 2, 1, 3]表示访问顺序为城市0→2→1→3）。变异和交叉操作需保持排列的有效性（即无重复城市）。

2.2 变异策略

针对排列问题，常用以下变异方式：

  • 交换变异（Swap Mutation）：随机选择两个位置交换城市。
  • 插入变异（Insertion Mutation）：随机选择一个城市插入到另一位置。
  • 逆序变异（Inversion Mutation）：随机选择一段子路径并逆序。

2.3 交叉策略

  • 顺序交叉（Order Crossover, OX）：保留父代的部分排列顺序，填充剩余城市。
  • 部分匹配交叉（PMX）：通过映射关系交换子代的部分基因。

三、Python实现步骤

以下是一个基于差分进化算法的TSP问题Python实现框架：

3.1 初始化种群

  1. import numpy as np
  3. def initialize_population(pop_size, num_cities):
  4.     population = []
  5.     for _ in range(pop_size):
  6.         path = np.arange(num_cities)
  7.         np.random.shuffle(path)
  8.         population.append(path)
  9.     return population

3.2 适应度函数（计算路径总距离）

  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(population, distance_matrix):
  9.     return [1 / calculate_distance(p, distance_matrix) for p in population]  # 距离越小，适应度越高

3.3 变异操作（交换变异）

  1. def mutate(individual):
  2.     idx1, idx2 = np.random.choice(len(individual), 2, replace=False)
  3.     mutated = individual.copy()
  4.     mutated[idx1], mutated[idx2] = mutated[idx2], mutated[idx1]
  5.     return mutated

3.4 交叉操作（顺序交叉OX）

  1. def crossover(parent1, parent2):
  2.     size = len(parent1)
  3.     idx1, idx2 = np.random.choice(size, 2, replace=False)
  4.     start, end = min(idx1, idx2), max(idx1, idx2)
  6.     child = np.full(size, -1)
  7.     child[start:end+1] = parent1[start:end+1]
  9.     current_pos = (end + 1) % size
  10.     parent2_pos = (end + 1) % size
  11.     while current_pos != start:
  12.         if parent2[parent2_pos] not in child:
  13.             child[current_pos] = parent2[parent2_pos]
  14.             current_pos = (current_pos + 1) % size
  15.         parent2_pos = (parent2_pos + 1) % size
  16.     return child

3.5 主算法流程

  1. def differential_evolution_tsp(distance_matrix, pop_size=50, generations=1000, F=0.8, CR=0.9):
  2.     num_cities = len(distance_matrix)
  3.     population = initialize_population(pop_size, num_cities)
  5.     for gen in range(generations):
  6.         new_population = []
  7.         for i in range(pop_size):
  8.             # 选择三个不同的父代
  9.             candidates = [x for x in range(pop_size) if x != i]
  10.             a, b, c = np.random.choice(candidates, 3, replace=False)
  12.             # 变异：a + F*(b - c)
  13.             mutant = mutate(population[a]) if np.random.rand() < F else population[a]
  15.             # 交叉：生成试验解
  16.             trial = np.zeros(num_cities, dtype=int)
  17.             cross_points = np.random.choice(num_cities, 2, replace=False)
  18.             start, end = min(cross_points), max(cross_points)
  19.             trial[start:end+1] = mutant[start:end+1]
  21.             # 填充剩余基因（保持排列有效性）
  22.             remaining_cities = [city for city in population[i] if city not in trial]
  23.             remaining_positions = [idx for idx in range(num_cities) if trial[idx] == -1]
  24.             for pos, city in zip(remaining_positions, remaining_cities):
  25.                 trial[pos] = city
  27.             # 选择：保留更优解
  28.             if calculate_distance(trial, distance_matrix) < calculate_distance(population[i], distance_matrix):
  29.                 new_population.append(trial)
  30.             else:
  31.                 new_population.append(population[i])
  33.         population = new_population
  35.         # 输出当前最优解
  36.         distances = [calculate_distance(p, distance_matrix) for p in population]
  37.         best_idx = np.argmin(distances)
  38.         print(f"Generation {gen}: Best Distance = {distances[best_idx]}")
  40.     best_idx = np.argmin([calculate_distance(p, distance_matrix) for p in population])
  41.     return population[best_idx]

四、性能优化与注意事项

4.1 参数调优

  • 种群规模（pop_size）：通常设为50~100，过大增加计算量，过小易早熟。
  • 变异因子（F）：控制变异强度，建议范围[0.5, 1.0]。
  • 交叉概率（CR）：控制交叉频率，建议范围[0.7, 0.9]。

4.2 混合策略

结合局部搜索（如2-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):
  6.     improved = True
  7.     while improved:
  8.         improved = False
  9.         for i in range(len(path)-1):
  10.             for j in range(i+1, len(path)):
  11.                 new_path = two_opt_swap(path, i, j)
  12.                 if calculate_distance(new_path, distance_matrix) < calculate_distance(path, distance_matrix):
  13.                     path = new_path
  14.                     improved = True
  15.                     break
  16.             if improved:
  17.                 break
  18.     return path

4.3 并行化加速

利用多进程或GPU并行计算适应度函数，显著缩短运行时间。

五、总结与扩展

差分进化算法通过灵活的变异和交叉策略，可有效解决TSP等组合优化问题。实际应用中需结合问题特性调整操作符（如变异方式），并可与遗传算法、模拟退火等混合使用。对于大规模TSP（如城市数>1000），建议结合降维技术（如聚类）或分布式计算框架。

英文关键词总结：

  • Differential Evolution (DE): 差分进化算法
  • Traveling Salesman Problem (TSP): 旅行商问题
  • Mutation Operator: 变异操作
  • Crossover Operator: 交叉操作
  • Fitness Evaluation: 适应度评估
  • Permutation-based DE: 基于排列的差分进化

通过上述方法，开发者可快速实现TSP的差分进化求解，并根据实际需求调整算法参数和操作符。

最新文章