遗传算法实战：用Python解决30城TSP问题（附完整代码）
·
遗传算法实战：用Python解决30城TSP问题（附完整代码）
你是否曾好奇，计算机如何为一位需要访问30个不同城市的旅行商规划出最短的路线？这看似简单的需求背后，隐藏着一个被称为“旅行商问题”（TSP）的计算难题。随着城市数量的增加，可能的路线数量会呈爆炸式增长，用传统方法寻找最优解几乎不可能。这正是启发式算法，特别是遗传算法大显身手的舞台。它不追求一步到位的最优，而是模拟自然界“物竞天择”的进化过程，在庞大的解空间中高效地搜寻出令人满意的优质路径。
对于Python开发者，尤其是那些对算法优化和实际应用感兴趣的初学者和中级爱好者来说，亲手实现一个遗传算法来解决TSP，不仅能深刻理解进化计算的核心思想，还能掌握如何将数学概念转化为可运行、可观察的代码。本文将带你从零开始，构建一个完整的、可视化的遗传算法求解器，针对30个城市的经典TSP实例，一步步拆解原理，编写代码，并亲眼见证算法如何从一团乱麻的随机路径中，迭代进化出一条清晰、高效的旅行环线。我们将重点关注如何用NumPy高效处理数据、如何设计关键的遗传算子（选择、交叉、变异），并解决实现中最棘手的路径冲突问题，最终提供一个可直接在Jupyter Notebook中运行和交互的完整方案。
1. 问题定义与遗传算法核心思想
旅行商问题（Traveling Salesman Problem, TSP）是组合优化领域最著名的问题之一。其描述非常直观：给定一系列城市和每对城市之间的距离，旅行商需要访问每个城市恰好一次，并最终回到起点，目标是找到总距离最短的环路。尽管描述简单，但TSP属于NP-hard难题，意味着随着城市数量N的增加，解空间（可能的路径数量）以阶乘级（(N-1)!/2）膨胀。对于30个城市，可能的路径数量已经是一个天文数字，穷举搜索完全不现实。
遗传算法（Genetic Algorithm, GA）正是为应对这类复杂搜索问题而生的。其灵感来源于达尔文的生物进化论，核心思想是“优胜劣汰”。算法维护一个包含多个潜在解（称为“个体”或“染色体”）的“种群”。每个个体代表一条可能的旅行路径。通过模拟自然选择、交叉（杂交）和变异等过程，种群一代代演化，其中适应环境（即路径更短）的个体有更大机会生存和繁衍，从而逐步逼近问题的最优解。
遗传算法解决TSP的基本流程可以概括为以下几步：
- 初始化：随机生成一组初始路径（种群）。
- 评估：计算每条路径的总长度，作为其“适应度”（路径越短，适应度越高）。
- 选择：根据适应度，选择优秀的个体作为父代，用于产生下一代。
- 交叉：将两个父代个体的部分路径信息进行交换重组，生成新的子代个体。
- 变异：以较小概率随机改变子代个体中的部分城市访问顺序，引入新的可能性。
- 迭代：用新生成的子代种群替代旧种群，重复步骤2-5，直到满足终止条件（如达到最大迭代次数或解的质量稳定）。
提示：遗传算法是一种启发式算法，它不保证找到数学上的绝对最优解，但能在合理时间内找到质量非常高的近似解，这对于许多实际应用已经足够。
2. 环境准备与数据加载
在开始编码之前，我们需要搭建好Python环境并准备好城市坐标数据。本项目推荐使用Jupyter Notebook进行交互式开发和可视化。
2.1 安装必要的库
我们将主要依赖numpy进行高效的数值计算，matplotlib进行结果可视化。可以通过以下命令安装：
pip install numpy matplotlib
2.2 定义城市坐标与距离矩阵
我们使用一个包含30个城市二维坐标的经典数据集。为了清晰和可复现，我们将坐标直接定义在代码中。
import numpy as np
import matplotlib.pyplot as plt
# 30个城市的坐标 (x, y)
city_coordinates = np.array([
[87, 7], [91, 38], [83, 46], [71, 44], [64, 60],
[68, 58], [83, 69], [87, 76], [74, 78], [71, 71],
[58, 69], [54, 62], [51, 67], [37, 84], [41, 94],
[2, 99], [7, 64], [22, 60], [25, 62], [18, 54],
[4, 50], [13, 40], [18, 40], [24, 42], [25, 38],
[41, 26], [45, 21], [44, 35], [58, 35], [62, 32]
])
num_cities = len(city_coordinates)
print(f"城市数量: {num_cities}")
接下来，我们需要计算所有城市两两之间的欧氏距离，并存储在一个距离矩阵中。这个矩阵将用于快速计算任何一条路径的总长度。
def compute_distance_matrix(coords):
"""计算城市间的欧氏距离矩阵"""
n = len(coords)
dist_matrix = np.zeros((n, n))
for i in range(n):
for j in range(i+1, n): # 利用对称性，只计算上三角
dist = np.linalg.norm(coords[i] - coords[j])
dist_matrix[i, j] = dist
dist_matrix[j, i] = dist # 对称赋值
return dist_matrix
distance_matrix = compute_distance_matrix(city_coordinates)
print(f"距离矩阵形状: {distance_matrix.shape}")
print(f"示例：城市0到城市1的距离: {distance_matrix[0, 1]:.2f}")
为了直观感受城市的分布，我们可以先将其可视化：
def plot_cities(coords, title="30个城市分布图"):
"""绘制城市坐标点"""
plt.figure(figsize=(10, 8))
plt.scatter(coords[:, 0], coords[:, 1], c='red', s=50, marker='o')
for i, (x, y) in enumerate(coords):
plt.text(x, y, str(i), fontsize=9, ha='right')
plt.xlabel("X 坐标")
plt.ylabel("Y 坐标")
plt.title(title)
plt.grid(True, alpha=0.3)
plt.show()
plot_cities(city_coordinates)
3. 遗传算法关键组件实现
有了数据和基础环境，我们现在开始构建遗传算法的核心部件。每个部件都需要仔细设计，以确保算法能有效进化。
3.1 染色体编码与种群初始化
在TSP中，一条路径（即一个解）可以自然地表示为一个城市访问顺序的列表。例如，[0, 5, 12, ..., 29, 3]表示从城市0出发，依次访问城市5、12...最后访问城市3并返回起点0。这种表示方法称为“顺序编码”。
种群就是多个这样的路径（染色体）的集合。初始化时，我们随机打乱城市顺序来生成不同的路径。
def create_individual(num_cities):
"""创建一个随机的个体（一条路径）"""
individual = np.arange(num_cities)
np.random.shuffle(individual)
return individual
def initialize_population(pop_size, num_cities):
"""初始化种群"""
population = []
for _ in range(pop_size):
population.append(create_individual(num_cities))
return np.array(population)
# 参数设置
POPULATION_SIZE = 100 # 种群大小
MAX_GENERATIONS = 1000 # 最大迭代代数
# 初始化
population = initialize_population(POPULATION_SIZE, num_cities)
print(f"种群大小: {population.shape}")
print("第一个个体的路径示例:", population[0])
3.2 适应度函数设计
适应度函数用于评价一个个体的好坏。在TSP中，路径越短越好，因此我们通常将路径总长度的倒数作为适应度值（长度越短，倒数越大，适应度越高）。为了避免除零错误，我们也可以直接使用路径长度的负值，然后在选择时处理。
def calculate_total_distance(individual, dist_matrix):
"""计算一条路径的总距离"""
total_dist = 0.0
# 计算从第一个城市到最后一个城市的距离
for i in range(len(individual) - 1):
city_from = individual[i]
city_to = individual[i + 1]
total_dist += dist_matrix[city_from, city_to]
# 加上从最后一个城市回到起点的距离
total_dist += dist_matrix[individual[-1], individual[0]]
return total_dist
def evaluate_fitness(population, dist_matrix):
"""评估整个种群的适应度（这里用路径长度，越小越好）"""
fitness = np.zeros(len(population))
for i, ind in enumerate(population):
fitness[i] = calculate_total_distance(ind, dist_matrix)
return fitness
# 测试适应度计算
sample_individual = population[0]
sample_distance = calculate_total_distance(sample_individual, distance_matrix)
print(f"示例路径总长度: {sample_distance:.2f}")
3.3 选择算子：优胜劣汰
选择算子的目的是从当前种群中选出较优的个体作为父代，用于繁殖下一代。常见的选择策略有“轮盘赌选择”和“锦标赛选择”。这里我们实现一种结合了精英保留策略的锦标赛选择：每次随机选取k个个体，保留其中最好的一个。
def selection_tournament(population, fitness, tournament_size=3, elite_size=5):
"""
锦标赛选择 + 精英保留
population: 种群
fitness: 对应的路径长度（越小越好）
tournament_size: 锦标赛规模
elite_size: 直接保留到下一代的精英个体数量
"""
pop_size = len(population)
new_population = []
# 1. 精英保留：直接复制适应度最好（路径最短）的前elite_size个个体
elite_indices = np.argsort(fitness)[:elite_size]
new_population.extend(population[elite_indices].tolist())
# 2. 锦标赛选择填充剩余位置
for _ in range(pop_size - elite_size):
# 随机选择 tournament_size 个参赛者
contestants = np.random.choice(pop_size, size=tournament_size, replace=False)
# 找出其中适应度最好（路径最短）的
winner_idx = contestants[np.argmin(fitness[contestants])]
new_population.append(population[winner_idx].copy())
return np.array(new_population)
# 测试选择操作
current_fitness = evaluate_fitness(population, distance_matrix)
selected_pop = selection_tournament(population, current_fitness)
print(f"选择后种群形状: {selected_pop.shape}")
print(f"原种群最优距离: {np.min(current_fitness):.2f}")
3.4 交叉算子：路径重组
交叉是遗传算法产生新个体的主要手段。对于TSP的顺序编码，交叉不能简单地交换片段，因为那样很容易产生重复或缺失城市的非法路径。这里我们实现一种常用的有序交叉（Order Crossover, OX）。
有序交叉（OX）步骤：
- 随机选择两个交叉点，截取父代A在这两点间的片段。
- 将父代B中未被该片段包含的城市，按其在B中出现的顺序，填充到子代剩余位置。
def crossover_ox(parent1, parent2, crossover_rate=0.8):
"""
有序交叉 (OX)
以 crossover_rate 的概率执行交叉，否则直接返回父代1的副本
"""
if np.random.rand() > crossover_rate:
return parent1.copy()
size = len(parent1)
# 随机选择两个交叉点
point1, point2 = np.sort(np.random.choice(size, 2, replace=False))
# 初始化子代，先用-1填充
child = -np.ones(size, dtype=int)
# 从parent1复制交叉点之间的片段到子代
child[point1:point2+1] = parent1[point1:point2+1]
# 从parent2填充剩余位置
parent2_pos = 0
for i in range(size):
if child[i] == -1: # 需要填充的位置
# 在parent2中寻找一个尚未出现在子代中的城市
while parent2[parent2_pos] in child:
parent2_pos = (parent2_pos + 1) % size
child[i] = parent2[parent2_pos]
parent2_pos = (parent2_pos + 1) % size
return child
def apply_crossover(population, crossover_rate=0.8):
"""对整个种群应用交叉操作（两两配对）"""
new_population = []
pop_size = len(population)
for i in range(0, pop_size, 2):
parent1 = population[i]
parent2 = population[(i + 1) % pop_size] # 防止奇数种群
child1 = crossover_ox(parent1, parent2, crossover_rate)
child2 = crossover_ox(parent2, parent1, crossover_rate) # 对称交叉
new_population.extend([child1, child2])
# 如果种群大小是奇数，处理最后一个个体（与第一个个体交叉）
if pop_size % 2 == 1:
new_population[-1] = crossover_ox(population[-1], population[0], crossover_rate)
return np.array(new_population)
# 测试交叉操作
parent_a = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
parent_b = np.array([9, 8, 7, 6, 5, 4, 3, 2, 1, 0])
child = crossover_ox(parent_a, parent_b, crossover_rate=1.0)
print(f"父代A: {parent_a}")
print(f"父代B: {parent_b}")
print(f"子代: {child}")
print(f"子代是否合法（无重复）: {len(np.unique(child)) == len(child)}")
3.5 变异算子：引入随机性
变异操作以较小概率随机改变个体中的基因，有助于维持种群多样性，避免算法过早收敛到局部最优解。对于TSP，常用的变异操作是“交换变异”或“倒置变异”。这里我们实现交换变异：随机选择两个位置，交换其城市。
def mutate_swap(individual, mutation_rate=0.05):
"""交换变异：以 mutation_rate 的概率随机交换两个城市的位置"""
if np.random.rand() > mutation_rate:
return individual.copy()
size = len(individual)
# 随机选择两个不同的位置
pos1, pos2 = np.random.choice(size, 2, replace=False)
mutated = individual.copy()
mutated[pos1], mutated[pos2] = mutated[pos2], mutated[pos1]
return mutated
def apply_mutation(population, mutation_rate=0.05):
"""对整个种群应用变异操作"""
mutated_population = []
for ind in population:
mutated_population.append(mutate_swap(ind, mutation_rate))
return np.array(mutated_population)
# 测试变异操作
test_individual = np.arange(10)
np.random.shuffle(test_individual)
mutated = mutate_swap(test_individual, mutation_rate=1.0)
print(f"原始个体: {test_individual}")
print(f"变异后: {mutated}")
print(f"变异是否发生（顺序改变）: {not np.array_equal(test_individual, mutated)}")
4. 算法整合、迭代与可视化
现在我们将所有组件组装起来，构建完整的遗传算法主循环，并添加可视化功能来观察进化过程。
4.1 主算法流程
我们将上述步骤整合到一个函数中，并记录每一代的最佳路径和距离，以便后续分析。
def genetic_algorithm_tsp(coords, pop_size=100, max_gens=500,
crossover_rate=0.8, mutation_rate=0.05,
tournament_size=3, elite_size=5):
"""
遗传算法求解TSP主函数
返回: (best_distance_history, best_route_history, final_best_route)
"""
num_cities = len(coords)
dist_matrix = compute_distance_matrix(coords)
# 初始化
population = initialize_population(pop_size, num_cities)
fitness = evaluate_fitness(population, dist_matrix)
# 记录历史最佳
best_distance_history = []
best_route_history = []
# 当前全局最佳
global_best_idx = np.argmin(fitness)
global_best_route = population[global_best_idx].copy()
global_best_distance = fitness[global_best_idx]
print("开始遗传算法迭代...")
for generation in range(max_gens):
# 1. 选择
population = selection_tournament(population, fitness, tournament_size, elite_size)
# 2. 交叉
population = apply_crossover(population, crossover_rate)
# 3. 变异
population = apply_mutation(population, mutation_rate)
# 4. 评估新种群
fitness = evaluate_fitness(population, dist_matrix)
# 5. 更新全局最佳
current_best_idx = np.argmin(fitness)
current_best_distance = fitness[current_best_idx]
if current_best_distance < global_best_distance:
global_best_distance = current_best_distance
global_best_route = population[current_best_idx].copy()
# 记录
best_distance_history.append(global_best_distance)
best_route_history.append(global_best_route.copy())
# 每100代输出一次进度
if (generation + 1) % 100 == 0:
print(f"代 {generation+1}/{max_gens}, 当前最佳距离: {global_best_distance:.2f}")
print(f"迭代完成。最终最佳距离: {global_best_distance:.2f}")
return best_distance_history, best_route_history, global_best_route
4.2 运行算法与结果分析
现在，让我们用一组相对稳健的参数运行算法，看看效果如何。
# 设置算法参数并运行
POP_SIZE = 150 # 稍大的种群有助于保持多样性
MAX_GENS = 800 # 迭代代数
CX_RATE = 0.85 # 交叉概率
MUT_RATE = 0.03 # 变异概率（不宜过高）
TOURNAMENT_SIZE = 5 # 锦标赛规模
ELITE_SIZE = 10 # 精英保留数量
best_dist_history, best_route_history, final_best_route = genetic_algorithm_tsp(
city_coordinates,
pop_size=POP_SIZE,
max_gens=MAX_GENS,
crossover_rate=CX_RATE,
mutation_rate=MUT_RATE,
tournament_size=TOURNAMENT_SIZE,
elite_size=ELITE_SIZE
)
4.3 进化过程可视化
可视化是理解算法行为的关键。我们将绘制两个图：一是算法收敛曲线，展示历代最佳路径长度的变化；二是最终找到的最佳路径图。
def plot_convergence(distance_history):
"""绘制最佳距离随迭代次数的收敛曲线"""
plt.figure(figsize=(10, 6))
plt.plot(distance_history, linewidth=2)
plt.xlabel('迭代代数', fontsize=12)
plt.ylabel('最佳路径长度', fontsize=12)
plt.title('遗传算法收敛曲线', fontsize=14)
plt.grid(True, alpha=0.5)
# 标记最终结果
final_dist = distance_history[-1]
plt.scatter(len(distance_history)-1, final_dist, color='red', s=50, zorder=5)
plt.text(len(distance_history)*0.7, final_dist*1.05, f'最终长度: {final_dist:.2f}', fontsize=11)
plt.show()
def plot_route(coords, route, title="最佳旅行路径"):
"""绘制给定路径连接城市的顺序图"""
plt.figure(figsize=(10, 8))
# 绘制城市点
plt.scatter(coords[:, 0], coords[:, 1], c='red', s=80, marker='o', edgecolors='k', linewidths=1)
for i, (x, y) in enumerate(coords):
plt.text(x, y, str(i), fontsize=10, ha='center', va='center', color='white', fontweight='bold')
# 绘制路径连线
route_coords = coords[route]
# 形成闭环
route_coords = np.vstack([route_coords, route_coords[0]])
plt.plot(route_coords[:, 0], route_coords[:, 1], 'b-', linewidth=1.5, alpha=0.7)
plt.plot(route_coords[:, 0], route_coords[:, 1], 'bo', markersize=4, alpha=0.7)
plt.xlabel("X 坐标", fontsize=12)
plt.ylabel("Y 坐标", fontsize=12)
plt.title(f"{title} (总长度: {calculate_total_distance(route, compute_distance_matrix(coords)):.2f})", fontsize=14)
plt.grid(True, alpha=0.3)
plt.show()
# 绘制收敛曲线
plot_convergence(best_dist_history)
# 绘制最终找到的最佳路径
plot_route(city_coordinates, final_best_route, "遗传算法找到的最佳旅行商路径")
通过收敛曲线，你可以清晰地看到算法是如何一步步优化路径的：初期改进迅速，后期逐渐趋于平稳。最佳路径图则直观地展示了旅行商访问30个城市的顺序。
4.4 关键参数的影响与调优尝试
遗传算法的性能很大程度上依赖于参数设置。没有一套放之四海而皆准的最优参数，需要根据问题特性和运行结果进行调整。下面我们通过一个简单的参数对比实验来感受一下。
def run_experiment(param_name, param_values, base_params):
"""运行一组参数实验，比较最终结果"""
results = []
for value in param_values:
params = base_params.copy()
params[param_name] = value
print(f"正在测试 {param_name} = {value} ...")
# 为了公平比较，固定随机种子
np.random.seed(42)
dist_history, _, best_route = genetic_algorithm_tsp(city_coordinates, **params)
results.append(dist_history[-1]) # 记录最终最佳距离
return results
# 基础参数配置
base_config = {
'pop_size': 100,
'max_gens': 300, # 为了快速实验，减少迭代次数
'crossover_rate': 0.8,
'mutation_rate': 0.05,
'tournament_size': 3,
'elite_size': 5
}
# 测试不同种群大小的影响
pop_sizes = [50, 100, 150, 200]
pop_results = run_experiment('pop_size', pop_sizes, base_config)
# 测试不同交叉概率的影响
cx_rates = [0.6, 0.7, 0.8, 0.9]
cx_results = run_experiment('crossover_rate', cx_rates, base_config)
# 结果对比表格
import pandas as pd
results_df = pd.DataFrame({
'参数': ['种群大小']*len(pop_sizes) + ['交叉概率']*len(cx_rates),
'取值': pop_sizes + cx_rates,
'最终最佳距离': pop_results + cx_results
})
print("\n参数对比实验结果:")
print(results_df.to_string(index=False))
在我的多次运行经验中，对于这个30城问题，种群大小在100到200之间通常能取得较好的平衡，既能保持多样性，又不会让计算开销过大。交叉概率在0.7到0.9之间效果较好，而变异概率则不宜超过0.1，过高的变异率会破坏已找到的好模式，使搜索变得过于随机。
5. 进阶优化与扩展思路
基础的遗传算法框架已经搭建完成，但仍有很大的优化空间。以下是几个可以进一步提升算法性能或扩展功能的思路。
5.1 改进选择与交叉策略
我们之前实现的选择和交叉算子虽然有效，但并非唯一选择。你可以尝试以下变体：
-
轮盘赌选择：个体被选中的概率与其适应度成正比。适应度越高（路径越短），被选中的概率越大。这能更好地体现“适者生存”，但可能导致选择压力过大，精英个体过快占据种群。
def selection_roulette(population, fitness): """轮盘赌选择""" # 将距离转换为适应度（距离越短，适应度越高） # 为避免除零，使用距离的倒数，并做适当缩放 fitness_values = 1.0 / (fitness + 1e-10) # 加一个小值防止除零 prob = fitness_values / fitness_values.sum() chosen_indices = np.random.choice(len(population), size=len(population), p=prob, replace=True) return population[chosen_indices].copy() -
部分映射交叉：另一种处理顺序编码的交叉方法，能更好地保留父代的相对顺序信息。
5.2 局部搜索与混合算法
遗传算法全局搜索能力强，但局部精细搜索能力弱。一个常见的改进是引入局部搜索（如2-opt优化）作为变异算子或后处理步骤。2-opt通过尝试交换路径中的两条边来寻找局部改进。
def two_opt_swap(route, i, j):
"""执行2-opt交换：反转路径中从i到j的子段"""
new_route = route.copy()
new_route[i:j+1] = route[i:j+1][::-1]
return new_route
def local_search_2opt(individual, dist_matrix, max_iter=100):
"""对单个个体进行2-opt局部搜索优化"""
improved = True
current_route = individual.copy()
current_dist = calculate_total_distance(current_route, dist_matrix)
iteration = 0
while improved and iteration < max_iter:
improved = False
for i in range(1, len(current_route) - 2):
for j in range(i + 1, len(current_route)):
if j - i == 1: continue # 相邻边交换无意义
# 尝试交换
new_route = two_opt_swap(current_route, i, j)
new_dist = calculate_total_distance(new_route, dist_matrix)
if new_dist < current_dist:
current_route = new_route
current_dist = new_dist
improved = True
break # 找到改进就跳出内层循环，重新开始搜索
if improved:
break
iteration += 1
return current_route
# 可以在变异后或每一代结束时，对精英个体应用局部搜索
将局部搜索嵌入遗传算法框架，就构成了混合遗传算法，往往能显著提升解的质量和收敛速度。
5.3 处理更大规模问题与性能考量
当城市数量增加到数百甚至上千时，算法的计算复杂度会成为瓶颈。以下几点优化至关重要：
- 距离矩阵预计算与缓存：我们已经做了，这是必须的。避免在循环中重复计算两点距离。
- 适应度计算的向量化：使用NumPy的向量化操作批量计算种群中所有个体的路径长度，比循环快得多。
def evaluate_fitness_vectorized(population, dist_matrix): """向量化计算种群适应度（距离）""" # 计算顺序相邻城市间的距离 pop_rolled = np.roll(population, shift=-1, axis=1) # 将每个路径循环左移一位 # 利用高级索引从距离矩阵中批量获取距离 # population[:, :-1] 和 pop_rolled[:, :-1] 获取所有边（除了最后一条） edge_dists = dist_matrix[population[:, :-1], pop_rolled[:, :-1]] # 加上最后一条返回起点的边 return_dist = dist_matrix[population[:, -1], population[:, 0]] total_dists = edge_dists.sum(axis=1) + return_dist return total_dists - 自适应参数：让交叉概率、变异概率随着迭代代数动态变化。例如，前期使用较高的变异率探索空间，后期降低变异率进行精细搜索。
- 并行化：评估种群适应度、执行交叉变异等操作可以并行进行，充分利用多核CPU。
5.4 完整可运行的Jupyter Notebook代码整合
为了方便你直接运行和实验，下面提供了一个整合后的代码块，包含了所有核心函数和一个简单的主程序。你可以将其复制到一个新的Jupyter Notebook单元格中运行。
# 遗传算法求解30城TSP - 完整代码块
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
# ========== 1. 数据与工具函数 ==========
city_coordinates = np.array([
[87, 7], [91, 38], [83, 46], [71, 44], [64, 60],
[68, 58], [83, 69], [87, 76], [74, 78], [71, 71],
[58, 69], [54, 62], [51, 67], [37, 84], [41, 94],
[2, 99], [7, 64], [22, 60], [25, 62], [18, 54],
[4, 50], [13, 40], [18, 40], [24, 42], [25, 38],
[41, 26], [45, 21], [44, 35], [58, 35], [62, 32]
])
def compute_distance_matrix(coords):
n = len(coords)
dist_matrix = np.zeros((n, n))
for i in range(n):
for j in range(i+1, n):
dist = np.linalg.norm(coords[i] - coords[j])
dist_matrix[i, j] = dist_matrix[j, i] = dist
return dist_matrix
def calculate_total_distance(route, dist_matrix):
total = 0.0
for i in range(len(route)-1):
total += dist_matrix[route[i], route[i+1]]
total += dist_matrix[route[-1], route[0]]
return total
# ========== 2. 遗传算法核心组件 ==========
def create_individual(n):
ind = np.arange(n)
np.random.shuffle(ind)
return ind
def initialize_population(pop_size, n):
return np.array([create_individual(n) for _ in range(pop_size)])
def evaluate_fitness(pop, dist_mat):
return np.array([calculate_total_distance(ind, dist_mat) for ind in pop])
def selection_tournament(pop, fitness, tourn_size=3, elite=5):
pop_size = len(pop)
new_pop = []
elite_idx = np.argsort(fitness)[:elite]
new_pop.extend(pop[elite_idx].tolist())
for _ in range(pop_size - elite):
contestants = np.random.choice(pop_size, size=tourn_size, replace=False)
winner = contestants[np.argmin(fitness[contestants])]
new_pop.append(pop[winner].copy())
return np.array(new_pop)
def crossover_ox(p1, p2, cx_rate=0.8):
if np.random.rand() > cx_rate:
return p1.copy()
size = len(p1)
pt1, pt2 = np.sort(np.random.choice(size, 2, replace=False))
child = -np.ones(size, dtype=int)
child[pt1:pt2+1] = p1[pt1:pt2+1]
pos = 0
for i in range(size):
if child[i] == -1:
while p2[pos] in child:
pos = (pos + 1) % size
child[i] = p2[pos]
pos = (pos + 1) % size
return child
def apply_crossover(pop, cx_rate=0.8):
new_pop = []
size = len(pop)
for i in range(0, size, 2):
p1, p2 = pop[i], pop[(i+1)%size]
new_pop.extend([crossover_ox(p1, p2, cx_rate), crossover_ox(p2, p1, cx_rate)])
if size % 2 == 1:
new_pop[-1] = crossover_ox(pop[-1], pop[0], cx_rate)
return np.array(new_pop)
def mutate_swap(ind, mut_rate=0.05):
if np.random.rand() > mut_rate:
return ind.copy()
size = len(ind)
i, j = np.random.choice(size, 2, replace=False)
mutated = ind.copy()
mutated[i], mutated[j] = mutated[j], mutated[i]
return mutated
def apply_mutation(pop, mut_rate=0.05):
return np.array([mutate_swap(ind, mut_rate) for ind in pop])
# ========== 3. 主算法与可视化 ==========
def ga_tsp_main(coords, pop_size=150, max_gens=500, cx_rate=0.85, mut_rate=0.03, tourn=5, elite=10):
n = len(coords)
dist_mat = compute_distance_matrix(coords)
pop = initialize_population(pop_size, n)
fitness = evaluate_fitness(pop, dist_mat)
best_dist_history = []
best_route_history = []
global_best_idx = np.argmin(fitness)
global_best_route = pop[global_best_idx].copy()
global_best_dist = fitness[global_best_idx]
for gen in range(max_gens):
pop = selection_tournament(pop, fitness, tourn, elite)
pop = apply_crossover(pop, cx_rate)
pop = apply_mutation(pop, mut_rate)
fitness = evaluate_fitness(pop, dist_mat)
curr_best_idx = np.argmin(fitness)
curr_best_dist = fitness[curr_best_idx]
if curr_best_dist < global_best_dist:
global_best_dist = curr_best_dist
global_best_route = pop[curr_best_idx].copy()
best_dist_history.append(global_best_dist)
best_route_history.append(global_best_route.copy())
if (gen+1) % 100 == 0:
print(f"Gen {gen+1:4d} | Best Dist: {global_best_dist:.2f}")
return best_dist_history, best_route_history, global_best_route
def plot_results(coords, dist_history, best_route):
fig, axes = plt.subplots(1, 2, figsize=(16, 6))
# 收敛曲线
axes[0].plot(dist_history, linewidth=2)
axes[0].set_xlabel('迭代代数')
axes[0].set_ylabel('最佳路径长度')
axes[0].set_title('算法收敛过程')
axes[0].grid(True, alpha=0.5)
axes[0].scatter(len(dist_history)-1, dist_history[-1], color='red', s=50)
# 最佳路径图
route_coords = coords[best_route]
route_coords = np.vstack([route_coords, route_coords[0]])
axes[1].scatter(coords[:, 0], coords[:, 1], c='red', s=80, edgecolors='k')
for i, (x, y) in enumerate(coords):
axes[1].text(x, y, str(i), fontsize=9, ha='center', va='center', color='white', fontweight='bold')
axes[1].plot(route_coords[:, 0], route_coords[:, 1], 'b-', linewidth=1.5, alpha=0.7)
axes[1].plot(route_coords[:, 0], route_coords[:, 1], 'bo', markersize=4, alpha=0.7)
axes[1].set_xlabel('X 坐标')
axes[1].set_ylabel('Y 坐标')
axes[1].set_title(f'最佳路径 (长度: {dist_history[-1]:.2f})')
axes[1].grid(True, alpha=0.3)
plt.tight_layout()
plt.show()
# ========== 4. 运行示例 ==========
if __name__ == '__main__':
print("开始运行遗传算法求解30城TSP...")
np.random.seed(123) # 设置随机种子以便复现结果
dist_hist, route_hist, final_route = ga_tsp_main(
city_coordinates,
pop_size=120,
max_gens=600,
cx_rate=0.82,
mut_rate=0.04,
tourn=4,
elite=8
)
print(f"\n最终找到的最佳路径长度: {dist_hist[-1]:.2f}")
print(f"路径顺序: {final_route}")
plot_results(city_coordinates, dist_hist, final_route)
运行这段代码，你将看到算法迭代过程在控制台输出，并最终生成一张包含收敛曲线和最佳路径图的综合结果图。多运行几次（去掉固定的随机种子），你会发现每次找到的路径长度可能略有不同，这正是随机算法的特点，但通常都能稳定在一个较优的区间内（对于这个30城数据集，通常在420-450左右）。
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
1
0- 0
已为社区贡献5条内容
所有评论(0)