遗传算法解决旅行商问题（TSP）：原理、实现与调优

提到旅行商问题TSP我到现在还记得第一次被算法课作业按在地上摩擦的感觉。十几个城市坐标摆在面前看起来就是“把所有顺序排一遍取最短”我当时天真地以为暴力枚举就能解决结果一跑才发现哪怕只有 15 个点组合数量也已经大到完全不能硬算。后来我系统把遗传算法的原理和落地实现补了一遍再回头看这件事其实解法路径非常清晰。今天这篇就把用遗传算法解决 TSP 的完整过程复盘一下从问题难度拆解、编码方式设计、Python 代码实现到参数调优和踩坑记录一次讲透。如果你正打算学智能算法或者手头刚好有路线优化、任务调度这类排序优化问题这篇文章可以直接当入门清单用。先说明一点这里说的“AI”不是指聊天机器人或者大模型而是老牌的智能算法——遗传算法Genetic Algorithm, GA。它不依赖梯度、不要求目标函数可导对付 TSP 这种组合爆炸型问题反而很顺手。1. 先搞懂对手TSP 到底难在哪1.1 一个看似简单的问题20 个城市就要算 1900 年TSP 的全称是 Travelling Salesman Problem中文通常叫旅行商问题。标准描述是给定 n 个城市的坐标一个销售员要从某个城市出发每个城市恰好访问一次最后回到出发城市要求找出一条总路程最短的闭环路线。这个问题的形式化一点也不吓人甚至可以写成一行找一个城市排列 p [p0, p1, ..., pn-1]最小化 sum(D[p[i]][p[(i1) % n]]) for i in range(n)这里的 D 是城市之间的距离矩阵。麻烦的地方在于可行解的数量。n 个城市所有可能闭环是 (n-1)!/2 种因为闭环可以旋转、可以镜像对称要去掉重复。我当年第一次算这个数的时候真的愣了几秒。n 20 的时候解空间大约是 6.08 × 10^16 种。假设你的电脑每秒可以评估 100 万条路线要穷举完 20 个城市的解空间大约需要 1900 多年。这不是慢一点的问题是完全不可行的量级。所以 TSP 实际上是组合优化里最经典的 NP-Hard 问题之一它难的不是“怎么算一条路线的长度”而是“怎么在指数级爆炸的解空间里尽快逼近最优解”。1.2 精确算法和贪心启发式的边界在哪有人会说那我不是还有动态规划、分支定界这些精确算法吗确实有但它们并不万能。Held-Karp 动态规划算法能把 TSP 的复杂度降到 O(n²·2ⁿ)。以 25 个城市为例2²⁵ 大约是 3300 万看似能扛但 n 到 30、35 之后状态数量立刻膨胀到普通机器扛不住。分支定界在对称 TSP 上表现好一些工业上能处理到几百个城市的实例但代码实现复杂而且性能高度依赖问题本身的结构。还有一个我们初学时常走的路贪心算法。比如最近邻法从任意城市出发每次都选离当前点最近的未访问城市。这个方法速度极快但结果通常很差尤其当城市分布不均匀时路线会经常出现交叉交叉意味着一定存在更短路径。贪心本质上是“只顾眼前最优”它很容易陷入局部最优而且没有任何机制能爬出来。这也是为什么后来大家普遍转向元启发式算法遗传算法、模拟退火、粒子群、蚁群算法都属于这一类。它们不保证每次都能找到精确最优解但能在可接受的时间里稳定找到工程上可用的“足够好”的解。1.3 智能算法池子里为什么先选遗传算法很多人问过我解决 TSP 用模拟退火不就行了用蚁群算法不也行为什么一定要用遗传算法我的回答是模拟退火和蚁群都能做 TSP但遗传算法是学习门槛和可扩展性结合得最好的一个尤其适合作为智能算法入门的第一站。它们的核心区别主要有几点算法核心思想优势常见坑遗传算法种群并行进化交叉变异产生新个体优胜劣汰多方向搜索全局搜索能力强天然适合排列编码参数多容易早熟调试要花时间模拟退火单点出发以一定概率接受劣解随温度下降收敛实现简单局部搜索能力强单点搜索容易漏掉好区域调温度曲线很关键粒子群个体共享历史最优和全局最优更新位置和速度连续优化表现优秀对离散排列类问题需要额外映射处理 TSP 不自然蚁群算法模拟蚂蚁留信息素正反馈积累对图结构问题友好能并行搜索参数敏感收敛速度偏慢遗传算法最吸引人的地方在于“种群”。它手里同时保有一大堆候选路线而不是一条路走到黑。路线之间通过交叉操作交换片段这相当于在解空间里不断做有方向的重组比单点搜索更能跳脱局部陷阱。我自己的体感是第一次把遗传算法跑通后再去学模拟退火、蚁群算法理解成本会低非常多因为很多概念是相通的。2. 遗传算法为什么能啃 TSP核心机制与编码设计2.1 遗传算法的运行逻辑一句话版本与流程拆解遗传算法的根源是模仿生物进化中的“自然选择、优胜劣汰”。如果只记一句话那就是先随机生成一堆候选解算每个解的适应度然后把表现好的解挑出来让它们互相交叉、变异生成下一代再淘汰差的如此循环迭代。不少教材喜欢把它写成一堆术语其实落地拆解之后就是六步初始化种群随机生成 N 条路线N 就是种群大小。适应度评估给每条路线打分TSP 里分越低越好但遗传算法一般习惯“适应度越高越好”所以需要转换。选择按适应度挑出较优的个体作为父代。交叉把两个父代的路径片段组合生成两个新个体。变异对某些个体做微小扰动比如交换两个城市的位置维持种群多样性。精英保留与环境替换直接把每代最好的个体原封不动送到下一代避免优秀解被交叉变异破坏。这里的每个操作都不难但真正写代码的时候你就会发现每一步都藏着坑。最典型的就是“交叉”这一步处理不好整个算法会跑出大量非法路线。2.2 路径编码与适应度函数把路线变成染色体用遗传算法解决 TSP