企业官网建设流程全解析

做算法的人都清楚，旅行商问题（TSP）就像一块试金石。给定一堆城市坐标，找一条能串起所有城市且总距离最短的闭环路线，听起来简单，但城市数量一多，解空间爆炸式增长，精确算法很快就不够用了。这时候，模拟退火、蚁群、遗传、粒子群这四类元启发式算法就派上了用场，这也是我这次用Python把它们全部实现一遍并拿来跑TSP的核心原因。这篇文章不聊虚的，直接从建模、代码、调参到实测对比挨个拆开来讲，把我踩过的坑和实际结论都摊开给你看，希望能给你一份能直接照着用的“四算法TSP求解参考”。

我在做这个项目时，最初的想法很简单：把四种算法放到同一个Benchmark下，用相同的数据、相同的评价标准，真正对比出谁更适合TSP、各自的优劣势在哪里。为了不让结论只停留在概念层面，我做了完整的实验，包括多次运行取均值，记录最优解、平均解、收敛代数、耗时等。整个过程下来，收获真的比单学某一种算法要大得多，因为这四种算法的设计哲学、参数敏感度、收敛速度差异极大，放一起对比，你能直观地体会到什么叫“没有免费的午餐”。

1. 先把TSP建模这步做对：数据、编码与距离矩阵

1.1 城市坐标与距离矩阵：为什么预计算能节省大量时间

实验用的数据是我随机生成的，固定随机种子保证可复现。常见的做法是生成二维平面上的坐标点，城市数量根据实验需求调整，我用得最多的是30个城市和50个城市两组数据。

城市坐标生成用最简单的均匀分布：

import numpy as np import random # 生成城市坐标，固定随机种子保证可复现 def generate_cities(num_cities=30, seed=42): np.random.seed(seed) x = np.random.rand(num_cities) * 100 y = np.random.rand(num_cities) * 100 return list(zip(x, y))

拿到坐标之后，下一步就是计算距离矩阵。这个矩阵在后续所有算法中都会被高频访问，所以必须一次性算好，放在一个二维数组里，而不是每次用到时再临时算一遍距离。别看这一步简单，忽略它的话，四种算法跑下来，光是重复计算距离的时间开销就能让人怀疑人生。

# 计算距离矩阵 def compute_distance_matrix(cities): num = len(cities) dist_matrix = np.zeros((num, num)) for i in range(num): for j in range(num): dx = cities[i][0] - cities[j][0] dy = cities[i][1] - cities[j][1] dist_matrix[i][j] = np.sqrt(dx*dx + dy*dy) return dist_matrix

实际测试中，30个城市用上面的方式没问题。但城市数量达到几百上千时，这个双层循环效率就很低了，可以用numpy的广播机制一次性算完。不过为了代码可读性，这里先用最直观的写法，后面再谈优化。

1.2 解的表示方式：为什么TSP天然适合排列编码

一个TSP解的本质是城市访问顺序。打个比方，5个城市就是“先走3号、再走1号、再走4号……”这样一个排列。所以解的自然表示就是长度为N的列表，每个数字是一一对应的城市编号，不重复、不遗漏。

比如[0, 3, 1, 4, 2]就代表一条路径：从城市0出发，依次经过3、1、4、2，最后返回0。由于是闭合回路，起点位置无所谓，只要排列顺序不变，从哪个城市开始遍历表示的都是同一条回路。

为什么不用二进制编码？因为TSP的合法性约束太严格了——二进制编码很难保证交叉、变异之后仍然是一个合法的排列。比如用二进制编码，变异一个bit就可能导致城市编号重复或者缺失，修复起来非常麻烦。所以业界标准做法就是排列编码，后面遗传算法、蚁群算法、粒子群算法也全都沿用这种表示方式。

路径总距离的计算同样需要复用，不管哪种算法，最终都要靠这个函数评价优劣：

# 计算路径总距离 def path_distance(path, dist_matrix): total = 0 for i in range(len(path)): current = path[i] nxt = path[(i + 1) % len(path)] total += dist_matrix[current][nxt] return total

这个函数写得越高效越好，因为它在算法迭代过程中会被调用成千上万次。我在实现中都尽量用numpy向量化或者保持简洁循环，避免不必要的开销。

2. 模拟退火算法：按物理退火的方式在解空间里找路

2.1 算法流程中的三个关键模块

模拟退火（Simulated Annealing，SA）是我最早实现的算法，也是理解所有启发式算法的最佳入口。它受金属退火过程的启发：金属慢慢降温，内部原子逐渐排列成低能量状态，如果降温过快，就会留下缺陷。同理，TSP求解过程中，可以用“温度”控制搜索行为。

SA的核心组成可以概括为三个模块：

• 初始解：通常随机生成一个排列作为起点。
• 邻域操作：对当前解做微小扰动，生成一个新解。最常用的是交换两个城市的位置，或者2-opt（反转路径的一段）。不同邻域操作对结果影响非常大。
• 接受准则：Metropolis准则，新解比当前解好就接受，差的话也有一定概率接受，这个概率跟当前温度负相关。正是因为“差解有时也能接受”，SA才不容易陷入局部最优。

邻域操作这里有个细节值得展开。交换两个位置（swap）是最简单的，但我实测下来，2-opt操作的效果明显更好。2-opt的原理是把路径中的一段倒序，它能让路径立刻消除交叉，这对TSP这种平面路径问题非常有效。代价就是每次生成新解要计算距离的次数稍多一点，但换来的是跳跃到更好解空间的概率大大增加。

模拟退火伪代码流程如下：

1. 设定初始温度T0，终止温度T_end，降温系数alpha
2. 随机生成初始解，计算路径距离
3. 对当前解做2-opt邻域扰动，得到新解
4. 计算距离差delta = new_dist - current_dist
5. 若delta < 0，接受新解；否则以概率exp(-delta/T)接受
6. 温度乘以alpha，降温
7. 重复3-6直到温度低于T_end

2.2 模拟退火的Python实现与参数选择

我写的完整核心代码大致如下：

def simulated_annealing(dist_matrix, init_temp=1000, end_temp=1e-3, alpha=0.99, max_iter_per_temp=200): num = len(dist_matrix) current_path = list(range(num)) random.shuffle(current_path) current_dist = path_distance(current_path, dist_matrix) best_path = current_path.copy() best_dist = current_dist temp = init_temp while temp > end_temp: for _ in range(max_iter_per_temp): # 2-opt操作：随机选两段，反转中间路径 i = random.randint(0, num - 2) j = random.randint(i + 1, num - 1) new_path = current_path.copy() new_path[i:j+1] = reversed(new_path[i:j+1]) new_dist = path_distance(new_path, dist_matrix) delta = new_dist - current_dist if delta < 0 or random.random() < np.exp(-delta / temp): current_path = new_path current_dist = new_dist if current_dist < best_dist: best_dist = current_dist best_path = current_path.copy() temp *= alpha return best_path, best_dist

参数不是随手填的，每个参数都有讲究：

• 初始温度T0：决定了算法初始阶段对差解的容忍程度。如果T0太小，一开始就变成“爬山”算法，很容易困在局部最优。怎么判断T0够不够？一个经验做法是，随机生成一些邻域扰动，统计差解的delta均值，然后让T0取这个均值的几倍到几十倍，确保初始接受率在0.8以上。
• 降温系数alpha：我推荐0.95到0.999之间。alpha越接近1，降温越慢，搜索越充分，但耗时也线性上升。30个城市用0.98就够，50个城市我更喜欢0.995。
• 终止温度：可以参考设成1e-3或者更小，其实更实用的终止条件是“连续若干代没改进就停机”，能省下不少计算资源。
• 每个温度点迭代次数：固定迭代次数是偷懒的做法，更聪明的是根据问题规模自适应，比如设成城市数量的5到10倍。

2.3 实测下来的几个感觉

30个城市数据，用上面的参数，SA几乎每一次运行都能找到非常接近已知最优的路径。速度很快，几十毫秒到几百毫秒就收敛了。

但SA有两个明显的弱点：第一，每次运行结果有随机性，同一组参数跑10次，最优解和平均解的差距波动会比较大；第二，温度变化率对结果影响太敏感，不同规模的问题可能需要重新调参。

我曾经在50个城市上直接用30个城市的最优参数，结果效果明显变差。后来把alpha从0.99改成0.995，多跑了接近一倍的迭代次数，才稳定下来。这让我意识到，SA看起来简单，但真正要发挥实力，调参还是得花功夫。

3. 遗传算法：交叉变异里的“排列魔咒”

3.1 为什么TSP的交叉操作不是随便做的

遗传算法（Genetic Algorithm，GA）的核心是模拟自然选择：一组候选解作为种群，用适应度筛选出更好的个体，通过交叉和变异产生下一代。

对于TSP，最头疼的问题在于：两个合法排列交叉之后，如果操作不当，生成的子代很可能是非法排列。举个简单的例子，父代A是[1, 2, 3, 4, 5]，父代B是[5, 3, 2, 1, 4]，如果按照传统单点交叉，把A的前半段和B的后半段拼起来，大概率会出现城市编号重复。

所以我最终选择的交叉策略是顺序交叉（Order Crossover，OX）。它的核心思想是：从父代A中选出一段连续子序列，保留在子代的相同位置；然后从父代B中按顺序取出尚未出现在子代里的城市，依次填入剩余位置。这样做的结果一定是一个合法排列，而且能最大程度保留父代中边的连续性。

顺序交叉的代码实现：

def order_crossover(p1, p2): num = len(p1) start = random.randint(0, num - 2) end = random.randint(start + 1, num - 1) child = [-1] * num child[start:end + 1] = p1[start:end + 1] pos = 0 for city in p2: if city not in child: while child[pos] != -1: pos += 1 child[pos] = city return child

这段代码里有个效率隐患：if city not in child在列表上做成员判断是O(n)复杂度，如果城市数量很大、种群规模也大，会拖慢速度。但30-50个城市完全无所谓，代码的可读性更重要。

3.2 选择、交叉、变异与精英保留策略

遗传算法的完整框架包括四步：选择、交叉、变异、环境选择。

选择我用的是锦标赛选择（Tournament Selection），每次随机挑3个个体，把适应度最好的那个选为父代。这样既保证了好的个体有更高概率被选中，又避免所有个体都被超级个体垄断，防止早熟。

变异操作我试过两种：交换变异（随机交换两个位置）和逆转变异（随机选一段倒序）。实测下来，逆转变异的搜索能力明显更强，原因和SA中2-opt优于交换是一样的——它能改变更长的路径结构，更容易消除路径交叉。

精英保留策略很重要，其实设计很简单：每次生成下一代之后，直接把上一代中路径最短的1到2个个体复制进新种群，避免最优解在交叉变异中丢失。没有这个机制，遗传算法经常最优解都快收敛了，又因为一次糟糕的变异让整个种群水平倒退好几代。

完整核心代码如下：

def genetic_algorithm(dist_matrix, pop_size=100, generations=500, elite_size=2): num = len(dist_matrix) # 初始化种群 population = [] for _ in range(pop_size): path = list(range(num)) random.shuffle(path) population.append(path) best_path = None best_dist = float('inf') for gen in range(generations): # 计算适应度（距离越小越好） distances = [path_distance(path, dist_matrix) for path in population] sorted_idx = np.argsort(distances) population = [population[i] for i in sorted_idx] if distances[sorted_idx[0]] < best_dist: best_dist = distances[sorted_idx[0]] best_path = population[0].copy() new_population = population[:elite_size] # 保留精英 while len(new_population) < pop_size: p1 = tournament_select(population, distances) p2 = tournament_select(population, distances) if random.random() < 0.9: child = order_crossover(p1, p2) else: child = p1.copy() # 变异 if random.random() < 0.1: i, j = random.sample(range(num), 2) child[i], child[j] = child[j], child[i] new_population.append(child) population = new_population return best_path, best_dist

3.3 遗传说起来简单，调起来也让人头疼

遗传算法的坑主要集中在两个地方：一是交叉率、变异率、种群大小的组合太多了，容易出现“差之毫厘谬以千里”的情况；二是很容易早熟收敛，也就是种群多样性快速丧失，所有个体都长得差不多，最终停在某个局部最优。

我的实测经验是，增大变异率可以在一定程度上对抗早熟，但变异率太高又会破坏已经积累的好解结构，变成随机搜索。折中方案是自适应变异率：迭代前期变异率稍高，探索解空间；后期逐渐降低，强化局部搜索。另外，种群规模不要太小，30个城市的实验我至少用100个个体，50个城市用200个个体效果更稳。

GA在30个城市上跑500代，需要的时间稍长于SA，但仍属于秒级以内。结果质量上，GA跟SA基本持平，但GA的优势在于并行性好，种群的天然结构非常适合多进程并行评估适应度。

4. 蚁群算法：正反馈机制带来的神奇效果

4.1 信息素与启发式信息的配合逻辑

蚁群算法（Ant Colony Optimization，ACO）是我做这个项目过程中觉得最“有意思”的算法。它的灵感来源是蚂蚁觅食：蚂蚁会在走过的路上留下信息素，后来的蚂蚁倾向于选择信息素浓度更高的路径，浓度越高的路径又被越多蚂蚁选择，形成正反馈。

在TSP里，每只蚂蚁从随机起点出发，按照概率选择下一个未访问的城市。选择概率由两部分构成：

• 信息素浓度 tau：边(i, j)上堆积的信息素越多，选择它的概率越高。
• 启发式信息 eta：距离越短，启发式信息越大，通常取1 / distance(i, j)。

两者结合的状态转移概率公式为：

P_ij = tau_ij^alpha * eta_ij^beta / Σ(tau_il^alpha * eta_il^beta)

其中alpha和beta分别控制信息素和距离的权重。这个公式是整个ACO的核心，理解它就能理解ACO为什么既能利用历史经验（信息素），又能保持贪婪性（启发式信息）。

4.2 蚁群算法核心代码实现

我在实现ACO时，最需要注意的是信息素的更新策略。信息素更新分两步：

1. 挥发：所有路径上的信息素按比例减少，避免信息素无限积累导致算法僵化。
2. 沉积：每只蚂蚁走完一条完整路径后，在它经过的边上沉积信息素，沉积量与路径总距离成反比。路径越短，沉积越多，这就让好路径的优势在正反馈中不断放大。

def ant_colony_optimization(dist_matrix, num_ants=50, alpha=1.5, beta=3.0, rho=0.5, Q=100, iterations=200): num = len(dist_matrix) tau = np.ones((num, num)) # 信息素矩阵 # 启发式信息矩阵，距离为0的点取一个小值避免除零 eta = 1.0 / (dist_matrix + 1e-10) np.fill_diagonal(eta, 0) best_path = None best_dist = float('inf') for it in range(iterations): all_paths = [] all_dists = [] for ant in range(num_ants): path = [] visited = [False] * num start = random.randint(0, num - 1) path.append(start) visited[start] = True for _ in range(num - 1): current = path[-1] candidates = [i for i in range(num) if not visited[i]] probs = [] for city in candidates: p = (tau[current][city] ** alpha) * (eta[current][city] ** beta) probs.append(p) probs = np.array(probs) / sum(probs) next_city = np.random.choice(candidates, p=probs) path.append(next_city) visited[next_city] = True all_paths.append(path) dist = path_distance(path, dist_matrix) all_dists.append(dist) if dist < best_dist: best_dist = dist best_path = path.copy() # 信息素挥发 tau *= (1 - rho) # 信息素沉积 for path, dist in zip(all_paths, all_dists): deposit = Q / dist for i in range(num - 1): tau[path[i]][path[i+1]] += deposit tau[path[-1]][path[0]] += deposit # 全局最优路径额外增强 if best_path: deposit_best = Q / best_dist for i in range(num - 1): tau[best_path[i]][best_path[i+1]] += deposit_best tau[best_path[-1]][best_path[0]] += deposit_best return best_path, best_dist

这里有个实现细节要注意：np.diag位置的信息素和eta必须置零或屏蔽，否则蚂蚁会倾向于在“同一个城市内部”徘徊，导致路径非法。另外，全局最优路径额外增强是我自己加的，实测效果是收敛速度提升明显，但也需要注意增强幅度不要过大，否则算法会过早锁定某条路径。

4.3 ACO参数敏感性远超前面几个算法

ACO的参数远比SA和GA多：蚂蚁数量、alpha、beta、rho、Q、迭代次数，全都影响最终结果。我的调参体会是，alpha、beta、rho这三个最核心。

• alpha（信息素权重）：alpha太小，蚂蚁基本靠距离做贪婪搜索，跟随机贪心差不多；alpha太大，信息素的正反馈过强，容易陷入局部最优。
• beta（启发式权重）：beta控制蚂蚁对短边的偏好程度，beta过大蚂蚁过于短视，beta过小又浪费了距离信息。
• rho（挥发系数）：rho越大信息素挥发越快，算法更倾向于探索新路径；rho越小，历史信息作用越大，算法更快集中到当前最优路径附近。

感官直觉上，rho=0.5是我试过比较均衡的值；alpha=1.5、beta=3.0在30城市数据集上表现最好。但这只是经验，换一个数据集很可能要重新微调。

ACO最让我惊艳的地方在于，随着迭代进行，信息素浓度会逐渐汇聚在最优路径的边上，你能看到信息素矩阵越来越“稀疏”，最终几乎只剩下一条最优路径上的值在增长。这种“进化般”的收敛过程非常有画面感。

不过ACO的时间开销也是最大的：每次迭代要同时模拟几十只蚂蚁构建路径，而每只蚂蚁都要做N-1次概率选择。城市数量增大时，计算量增长得特别快。30个城市问题不大，50个城市时我就明显感觉到耗时增长了。

5. 粒子群算法：连续优化算法怎么解离散问题

5.1 标准PSO是连续的，怎么改造才适合TSP

粒子群算法（Particle Swarm Optimization，PSO）原本是为连续优化问题设计的。粒子的“位置”是连续空间中的一个点，“速度”是连续向量，每个粒子根据自身历史最优位置（pbest）和群体全局最优位置（gbest）来更新自己的速度与位置。

但TSP的解是离散排列，没法直接套用x_new = x_old + v这套公式。常见的改造方式是把速度重新定义为“交换操作序列”。

打个比方，当前位置的路径是[1, 2, 3, 4]，如果你想变成目标路径[1, 3, 2, 4]，只需要执行一个交换操作：把位置2和3的元素对调。那么“速度”就可以定义为一系列交换操作的组合。

基于这个思路，我实现了交换序PSO：

• 粒子的位置：一个排列。
• 粒子的速度：一个由若干交换操作(i, j)组成的列表。
• 两个位置之差：从当前位置变换到目标位置所需的交换操作序列。
• 位置更新：对当前位置依次执行速度列表里的所有交换。

这样设计的好处是，PSO的更新公式仍然直观，只是把连续空间中的加减法替换成了“交换序列的组合”。

5.2 离散PSO的Python实现

交换操作的求法，有人可能觉得需要复杂的算法，其实很简单。把当前路径一步步变成目标路径，每发现一个位置对不上，就找到目标城市在当前位置的下标，做一次交换并记录：

# 求从path1到path2所需的交换操作序列 def get_swap_ops(path1, path2): ops = [] tmp = path1.copy() for i in range(len(path1)): if tmp[i] != path2[i]: j = tmp.index(path2[i]) tmp[i], tmp[j] = tmp[j], tmp[i] ops.append((i, j)) return ops

然后PSO的更新流程是这样：

def particle_swarm_optimization(dist_matrix, pop_size=50, max_iter=300, w=0.8, c1=0.6, c2=0.6): num = len(dist_matrix) particles = [] velocities = [] # 初始化粒子与速度 for _ in range(pop_size): path = list(range(num)) random.shuffle(path) particles.append(path) velocities.append([]) # 空速度，即无交换操作 pbest = [p.copy() for p in particles] pbest_dist = [path_distance(p, dist_matrix) for p in particles] gbest = particles[np.argmin(pbest_dist)].copy() gbest_dist = min(pbest_dist) for it in range(max_iter): for i in range(pop_size): # 速度更新：保留部分旧操作 + 学习pbest + 学习gbest new_vel = [] for op in velocities[i]: if random.random() < w: new_vel.append(op) ops_pbest = get_swap_ops(particles[i], pbest[i]) for op in ops_pbest: if random.random() < c1: new_vel.append(op) ops_gbest = get_swap_ops(particles[i], gbest) for op in ops_gbest: if random.random() < c2: new_vel.append(op) velocities[i] = new_vel # 位置更新：依次执行交换操作 for i_idx, j_idx in velocities[i]: particles[i][i_idx], particles[i][j_idx] = particles[i][j_idx], particles[i][i_idx] dist = path_distance(particles[i], dist_matrix) if dist < pbest_dist[i]: pbest[i] = particles[i].copy() pbest_dist[i] = dist if dist < gbest_dist: gbest_dist = dist gbest = particles[i].copy() return gbest, gbest_dist

这个实现的更新逻辑有点概率采样每个信息源的味道。w控制旧速度的惯性，c1和c2控制对自身历史最优和全局最优的学习力度。从代码复杂度看，离散PSO比GA和ACO都要轻巧，但实际效果需要注意观察。

5.3 PSO对TSP的真实效果如何

坦率地讲，在30个城市的数据集上，离散PSO的综合表现不如SA、GA和ACO。它找到的最优解距离前几个算法有明显差距，而且收敛速度也没有体现优势。原因也不难理解：速度被离散化成交换序列之后，信息的连续性大打折扣，粒子在排列空间中的“飞行”效率远不如连续空间中那么优雅。

但PSO也有它的可取之处：代码实现极其简洁，而且粒子数量少的情况下计算开销很小。我试过把PSO作为其他算法的后处理精修工具：先用GA快速求一个较好解，再用PSO在这个解附近做局部搜索，效果比单独跑PSO好很多。

如果你的目标只是求解TSP，PSO可能不是首选；但如果你想理解“连续优化算法如何离散化适配组合优化”这类方法论问题，PSO的交换序玩法值得研究。

6. 四种算法横向对比与选型建议

6.1 统一实验设置

为了让对比结论公平，我把四种算法跑在同一份30城市数据集上，每种算法分别运行10次，记录最优解、平均解、平均耗时和收敛趋势。参数设定如下表：

6.2 对比结果表

10次运行的统计结果整理如下：

在30城市这个规模下，单纯比较“谁最优”其实差距不大，但我跑10次之后，SA和ACO的最优、平均表现确实更好。GA的稳定性最强，粒子群相对最弱。

一个更有意思的观察是收敛曲线：SA的温度衰减天然决定了它“前期猛探索、后期细精搜”；GA的收敛曲线比较平缓，偶尔会有跳跃式改进；ACO的收敛曲线前期极慢，一旦某条路径积累了信息素优势，会出现断崖式下降；PSO的收敛曲线则很不稳定，经常前几轮有快速提升，之后就卡住了。

6.3 什么时候该用哪个算法

如果让我给出实用建议，我会这样分场景推荐：

• 快速验证一个TSP实例，优先用模拟退火。它实现最简单、调参最直观、结果可接受。尤其是问题规模不大时，SA往往是你花最少时间得到能用解的选择。
• 想要稳定可复现的结果，遗传算法更稳妥。种群机制天然对抗随机性，多次运行的结果方差小。适合需要报告数据、做实验分析的场景。
• 问题规模中等偏大且你有调参耐心，蚁群算法值得投入。它的信息素正反馈机制在路径类问题上潜力很大，但参数敏感，要花时间微调。
• 对离散PSO，我的建议是把它当辅助工具，不太建议作为主力求解器。用它做局部精修或教学演示还不错。

还有一个跨算法通吃的思路：把多种算法串成两阶段方案。例如先用遗传算法跑几代得到一个较优区域，再切到模拟退火做邻域细分。这种“混合算法”在很多实际问题中比单一算法鲁棒得多，我在后半程实验里尝到了不少甜头。

7. 我踩过的坑和一些改进建议

7.1 随机种子和结果复现

这个坑最基础，但最坑人。不固定随机种子的话，你跑出来的结果每次都不一样，哪怕只是调试一个参数，也很难判断到底是参数导致的差异还是运气导致的差异。我的做法是在每次实验前设置random.seed(42)和np.random.seed(42)，同时把城市数据也放到固定种子下生成。这样至少保证同一台机器、同一份数据下可以复现结果。

7.2 2-opt局部搜索是万金油

在我跑的四种算法里，几乎所有算法的最终结果都能通过一个简单的2-opt局部搜索再提升几个百分点。原理很简单：检查路径中有没有“交叉”的边，把交叉的边解开，路径长度必然下降。这个操作和具体算法无关，完全可以作为所有算法收尾时的“画龙点睛”。

def two_opt_improve(path, dist_matrix): improved = True n = len(path) best_path = path.copy() best_dist = path_distance(best_path, dist_matrix) while improved: improved = False for i in range(n - 1): for j in range(i + 2, n): if j - i == 1: continue new_path = best_path.copy() new_path[i+1:j+1] = reversed(new_path[i+1:j+1]) new_dist = path_distance(new_path, dist_matrix) if new_dist < best_dist - 1e-9: best_path = new_path best_dist = new_dist improved = True if not improved: break return best_path, best_dist

注意循环里的j - i == 1是用来跳过相邻边，因为反转相邻边没有意义。2-opt本身也是TSP算法中经典的局部搜索之一，单独拿来跑已经能取得不错的结果，跟元启发式算法配合更是如虎添翼。

7.3 提升性能的几条实操建议

第一，距离矩阵用numpy二维数组而不是Python列表嵌套，访问速度差别明显。在算法内部频繁调用距离值时，这种优化会直接体现在整体运行时间上。

第二，能向量化的地方尽量向量化。蚁群算法中计算所有候选城市的概率probs时可以写成向量乘法，比逐个for循环快好几个数量级。

第三，种群或粒子群算法天然适合并行化。遗传算法中每个个体的适应度评估互相独立，可以直接用Python的multiprocessing.Pool.map来并行评估。我一度觉得GA跑得慢，改成并行之后时间直接砍到三分之一。

第四，关于蚁群算法，信息素矩阵更新时尽量在矩阵层面操作，而不是用逐边更新的循环。tau *= (1 - rho)这种写法比遍历每条边分别乘(1 - rho)快得多。

7.4 实验结果可视化的价值

我强烈建议在项目里加一个简单的可视化模块，把城市位置和最优路径画出来。有时候数据表格说明不了的问题，一张图就清楚了。比如蚁群算法跑出来的路径是不是存在明显交叉，SA是否陷入了一个很差的路径形态，画出来一眼就能看出问题。

用matplotlib画图很简单：

import matplotlib.pyplot as plt def plot_path(cities, path, title="TSP Path"): xs = [cities[city][0] for city in path] + [cities[path[0]][0]] ys = [cities[city][1] for city in path] + [cities[path[0]][1]] plt.figure(figsize=(6, 6)) plt.plot(xs, ys, 'o-', linewidth=1) for idx, city in enumerate(path): plt.text(cities[city][0], cities[city][1], str(city)) plt.title(title) plt.show()

可视化不只是为了“好看”，它能帮你快速验证算法是否出现了路径交叉、重复访问城市这类隐性bug。我记得有次蚁群算法跑出“最短路径”，结果画出来一看居然有一段重复走了同一条边，就是因为我在信息素更新时忘记屏蔽自环导致的。没有图的话，这种问题单看距离数值很难察觉。

7.5 扩展思考：如果城市数量继续增大怎么办

30个城市只是热身，50个城市已经能明显感受到四种算法的差异，但如果把城市推到200个、500个，情况又会完全不同。SA会变得很慢，GA的种群规模需要大幅增加，ACO的信息素矩阵会变得巨大且迭代次数需求暴增，离散PSO在解空间中的表现可能更差。

这时候需要考虑的就不只是算法本身，而是数据结构、并行加速、甚至引入更复杂的邻域搜索框架。我在实验后程跑了200个城市的测试集，SA加上2-opt局部优化勉强能出结果，但纯ACO就跑得非常吃力。这个现象本身也很能说明问题：没有哪种算法能通吃所有规模，实际问题里的算法选型永远是个工程权衡。

我个人在实际操作中最深的体会是：把这四种算法放在一起实现的收获，远远大于单独学某一种算法。对比过程中你会看到不同算法如何用自己的方式处理“探索与利用”这个永恒矛盾——SA靠温度控制，GA靠种群多样性和选择压力，ACO靠信息素正反馈，PSO靠个体与群体的信息共享。理解了这一层，当你面对一个全新的优化问题时，选型和改造的思路就会畅通很多。如果这篇文章能帮你在自己的TSP实验里少踩几个坑，那就是它最大的价值了。