遗传算法求解 TSP（GA）

目录

• 项目概览
• 实验结果汇总
  • 个性化实验参数
  • 基准参数实验结果
  • 全实验最优结果图
  • 种群规模对算法性能的影响
  • 交叉概率对算法性能的影响
  • 选择策略对算法性能的影响
  • 与模拟退火算法的结果比较分析
  • 结论分析
• 当前支持功能
• 项目结构
• 核心实现片段
  • 个体编码方式
  • 适应度函数
  • 种群更新策略
• 快速开始
• 后续改进方向

---

项目概览

本项目使用**遗传算法（Genetic Algorithm, GA）**求解旅行商问题（TSP），并围绕三类关键参数开展对比实验，分析不同参数设置对收敛速度与解质量的影响。

本次重点考察的参数包括：

1. 种群规模
2. 交叉概率
3. 选择策略

城市坐标的生成方式与原程序保持完全一致，因此所有实验均基于同一组城市进行。

---

实验结果汇总

个性化实验参数

为保证实验可复现性，本文采用固定随机种子，并在相同城市规模、初始种群方式、交叉方式、变异方式和终止条件下开展对比实验。个性化参数设置如下。

参数	值
随机种子	24341
城市数量 N	50
坐标范围	1000 × 1000
学号后两位	41
基准种群规模 POP_SIZE	120
最大迭代代数 N_GENERATIONS	1000
交叉概率 CROSSOVER_PROB	0.90
变异概率 MUTATION_PROB	0.20
精英保留数 ELITE_SIZE	2
选择策略 SELECTION_METHOD	tournament
锦标赛规模 TOURNAMENT_SIZE	4
初始种群方式 INITIAL_POP_METHOD	random
交叉方式 CROSSOVER_METHOD	ordered
变异方式 MUTATION_METHOD	swap
提前停止参数 PATIENCE	120

基准参数实验结果

在基准参数设置下，程序运行结果如下。

指标	数值
最优路径长度	7208.64
实际迭代代数	599
耗时（秒）	3.60

基准参数用于体现默认配置下的运行效果，但它并不是本轮全部实验中的最优结果。

全实验最优结果图

当前程序生成的 tsp_ga_best_result.png 已不再固定展示基准参数的结果，而是会从“基准实验 + 三组参数对比实验”中自动筛选出真正最短路径对应的方法，并将该方法的路线图与收敛过程保存为总结果图。

在本轮 N_GENERATIONS = 1000 的实验中，全实验最优结果如下。

指标	数值
最优方法	selection_method = rank
最优路径长度	6536.12
对应迭代代数	663
耗时（秒）	4.84

对应结果图文件：

• tsp_ga_best_result.png

因此，tsp_ga_best_result.png 当前表示的是全实验最优路径图，而不是“基准参数下的结果图”。

种群规模对算法性能的影响

首先，在其余参数保持不变的条件下，对种群规模进行对比实验。实验结果如下。

种群规模	迭代代数	最优路径长度	耗时（秒）
60	612	7999.14	1.76
120	599	7208.64	3.47
180	462	8051.17	4.25

由表可见，当最大迭代代数提升到 1000 后，三组种群规模实验的实际停止代数发生了变化，但最优路径长度并没有出现突破性改善。120 仍然保持最好结果 7208.64，说明在当前交叉与变异设置下，继续增加迭代上限并没有显著改变“中等规模种群更优”的结论；而 180 仍然表现较差，且耗时最高。

对应结果图文件：

• ga_pop_size_comparison.png

交叉概率对算法性能的影响

在其余参数保持不变的条件下，对交叉概率进行对比实验。实验结果如下。

交叉概率	迭代代数	最优路径长度	耗时（秒）
0.70	539	8148.24	2.82
0.85	782	7419.02	4.64
0.95	500	7233.65	3.15

与之前相比，0.85 交叉概率下的结果有明显改善，由原先较差的 8246.42 降至 7419.02，说明增大最大迭代代数后，该参数组合获得了更多搜索机会；不过综合来看，0.95 仍然给出了最优结果 7233.65，因此“较高交叉概率更有利”的总体结论不变。

对应结果图文件：

• ga_crossover_prob_comparison.png

选择策略对算法性能的影响

在其余参数保持不变的条件下，对三种选择策略进行对比实验。实验结果如下。

选择策略	迭代代数	最优路径长度	耗时（秒）
roulette	706	14849.06	4.79
tournament	599	7208.64	3.72
rank	663	6536.12	4.84

与此前结果相比，rank 选择策略从 6555.02 进一步提升到 6536.12，而 roulette 也从 15822.49 略微改善到 14849.06。这说明增加最大迭代代数对 GA 仍然有一定帮助，尤其是对部分非最优参数组合能带来更充分的搜索；但总体排序并未改变，仍然是 rank 最优、tournament 次之、roulette 最差。

对应结果图文件：

• ga_selection_method_comparison.png

与模拟退火算法的结果比较分析

由于 GA 与 SA 使用相同随机种子、相同城市数量和相同坐标生成方式，因此两者结果具有可比性。将本次 GA 在 N_GENERATIONS = 1000 下的新结果与 SA 在不同退火系数下的结果进行比较，可得到如下结论。

1. 解质量比较

SA 在三组典型参数下的最优路径长度分别为：

• α = 0.85：6012.33
• α = 0.92：5824.29
• α = 0.99：5487.02

GA 当前实验中的代表性结果为：

• 基准参数（tournament）：7208.64
• 全实验最优方法（rank）：6536.12

与先前 N_GENERATIONS = 500 的结果相比，GA 的最优结果由 6555.02 小幅改进为 6536.12，说明增加最大迭代代数确实带来了额外收益；但从整体上看，当前 SA 的结果仍然明显优于当前 GA。即使取 GA 已完成实验中的最好结果 6536.12，仍然高于 SA 在 α = 0.85、α = 0.92 和 α = 0.99 下的结果。

2. 时间开销比较

SA 的运行时间大致为：

• α = 0.85：0.10s
• α = 0.92：0.19s
• α = 0.99：1.63s

GA 的运行时间大致为：

• 基准参数：3.60s
• 全实验最优方法 rank：4.84s

由此可见，在当前实验中，SA 仍然同时具备更优路径质量与更低时间开销。即使把 GA 的最大迭代代数提升到 1000，其运行时间进一步上升，但解质量改善幅度相对有限。

3. 搜索机制差异分析

两种算法结果差异，主要来自搜索机制本身不同：

• SA 通过接受一定概率的劣解跳出局部最优，随后逐步降温，使搜索从“全局探索”过渡到“局部收敛”；
• GA 依赖种群多样性、交叉重组和变异操作完成搜索，但当前参数下种群规模、交叉方式和变异强度可能还不足以充分挖掘更优结构。

从本次结果看，单纯增加迭代上限能够带来一定改进，但不足以让 GA 追平 SA。这说明当前 GA 的性能瓶颈不只在“代数不够”，还与参数组合和搜索结构本身有关。

4. 更新后的公平比较结论

在 N_GENERATIONS = 1000 条件下，GA 的部分结果相较之前有所改善，尤其是：

• rank：6555.02 → 6536.12
• crossover_prob = 0.85：8246.42 → 7419.02
• roulette：15822.49 → 14849.06

但总体来看，更新后的结论没有发生根本变化：在当前实现与当前实验参数下，SA 的综合表现依然优于 GA；GA 虽然通过增加最大迭代代数获得了小幅提升，但仍然存在较大优化空间。

结论分析

综合以上最新实验结果，可以得到以下结论：

1. 将最大迭代代数从 500 提高到 1000 后，GA 的部分参数组合结果有所改善，但基准结果 7208.64 并未突破；
2. tsp_ga_best_result.png 当前展示的是全实验真正最优的方法结果，而不是默认基准参数结果；
3. 种群规模方面，120 依然是当前设置下的最佳选择，说明中等规模种群最适合当前问题；
4. 交叉概率方面，0.95 仍然表现最好，而 0.85 在更大迭代上限下有了明显改善；
5. 选择策略方面，rank 依旧是最优方案，并且在新实验中进一步提升到了 6536.12；
6. 与当前实验条件下的模拟退火算法相比，遗传算法虽然略有进步，但在解质量和运行效率上仍然落后于 SA；
7. 因此，若要进一步提升 GA 的性能，后续重点不应只是继续增加迭代代数，还应继续优化变异方式、初始种群方式与混合局部搜索机制。

---

当前支持功能

• 个体编码方式：排列编码
• 选择策略：roulette、tournament、rank
• 交叉方式：ordered
• 变异方式：swap、insert、reverse
• 种群更新策略：精英保留 + 子代填充
• 终止条件：最大迭代代数 / 连续若干代无改进提前停止
• 参数对比实验：支持种群规模、交叉概率、选择策略三类参数对比

---

项目结构

文件名	说明
config_GA.py	遗传算法实验参数配置文件，包含问题规模、遗传算法参数与对比实验参数列表
tsp_genetic_algorithm.py	主算法实现文件，包含城市生成、适应度函数、选择、交叉、变异、种群更新及结果可视化
README_GA.md	项目说明文档，包含算法设计、实验结果分析与使用说明
tsp_ga_best_result.png	全实验真正最优方法对应的路线图与收敛图
ga_pop_size_comparison.png	不同种群规模的汇总对比图
ga_crossover_prob_comparison.png	不同交叉概率的汇总对比图
ga_selection_method_comparison.png	不同选择策略的汇总对比图

---

核心实现片段

个体编码方式

individual = list(range(n))
np.random.shuffle(individual)

适应度函数

lengths = np.array([tour_length(ind, dist_matrix) for ind in population], dtype=float)
fitness = 1.0 / (lengths + 1e-9)

种群更新策略

elite_idx = np.argsort(lengths)[:elite_size]
new_population = [population[i].copy() for i in elite_idx]

while len(new_population) < pop_size:
    parent1 = select_parent(population, fitness, selection_method)
    parent2 = select_parent(population, fitness, selection_method)
    child1, child2 = crossover(parent1, parent2, crossover_prob, crossover_method)
    new_population.append(mutate(child1, mutation_prob, mutation_method))
    if len(new_population) < pop_size:
        new_population.append(mutate(child2, mutation_prob, mutation_method))

---

快速开始

python tsp_genetic_algorithm.py

如需调参，请编辑 config_GA.py 中的相关配置（如 POP_SIZES、CROSSOVER_PROBS、SELECTION_METHODS 等）。

---

后续改进方向

• 多次独立运行统计（如 10~30 次，记录 mean/std/best/worst）
• 自适应调整交叉概率与变异概率
• 结合局部搜索策略进一步提升路径质量