做算法的人都清楚旅行商问题TSP就像一块试金石。给定一堆城市坐标找一条能串起所有城市且总距离最短的闭环路线听起来简单但城市数量一多解空间爆炸式增长精确算法很快就不够用了。这时候模拟退火、蚁群、遗传、粒子群这四类元启发式算法就派上了用场这也是我这次用Python把它们全部实现一遍并拿来跑TSP的核心原因。这篇文章不聊虚的直接从建模、代码、调参到实测对比挨个拆开来讲把我踩过的坑和实际结论都摊开给你看希望能给你一份能直接照着用的“四算法TSP求解参考”。我在做这个项目时最初的想法很简单把四种算法放到同一个Benchmark下用相同的数据、相同的评价标准真正对比出谁更适合TSP、各自的优劣势在哪里。为了不让结论只停留在概念层面我做了完整的实验包括多次运行取均值记录最优解、平均解、收敛代数、耗时等。整个过程下来收获真的比单学某一种算法要大得多因为这四种算法的设计哲学、参数敏感度、收敛速度差异极大放一起对比你能直观地体会到什么叫“没有免费的午餐”。1. 先把TSP建模这步做对数据、编码与距离矩阵1.1 城市坐标与距离矩阵为什么预计算能节省大量时间实验用的数据是我随机生成的固定随机种子保证可复现。常见的做法是生成二维平面上的坐标点城市数量根据实验需求调整我用得最多的是30个城市和50个城市两组数据。城市坐标生成用最简单的均匀分布import numpy as np import random # 生成城市坐标固定随机种子保证可复现 def generate_cities(num_cities30, seed42): 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 AnnealingSA是我最早实现的算法也是理解所有启发式算法的最佳入口。它受金属退火过程的启发金属慢慢降温内部原子逐渐排列成低能量状态如果降温过快就会留下缺陷。同理TSP求解过程中可以用“温度”控制搜索行为。SA的核心组成可以概括为三个模块初始解通常随机生成一个排列作为起点。邻域操作对当前解做微小扰动生成一个新解。最常用的是交换两个城市的位置或者2-opt反转路径的一段。不同邻域操作对结果影响非常大。接受准则Metropolis准则新解比当前解好就接受差的话也有一定概率接受这个概率跟当前温度负相关。正是因为“差解有时也能接受”SA才不容易陷入局部最优。邻域操作这里有个细节值得展开。交换两个位置swap是最简单的但我实测下来2-opt操作的效果明显更好。2-opt的原理是把路径中的一段倒序它能让路径立刻消除交叉这对TSP这种平面路径问题非常有效。代价就是每次生成新解要计算距离的次数稍多一点但换来的是跳跃到更好解空间的概率大大增加。模拟退火伪代码流程如下设定初始温度T0终止温度T_end降温系数alpha随机生成初始解计算路径距离对当前解做2-opt邻域扰动得到新解计算距离差delta new_dist - current_dist若delta 0接受新解否则以概率exp(-delta/T)接受温度乘以alpha降温重复3-6直到温度低于T_end2.2 模拟退火的Python实现与参数选择我写的完整核心代码大致如下def simulated_annealing(dist_matrix, init_temp1000, end_temp1e-3, alpha0.99, max_iter_per_temp200): 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:j1] reversed(new_path[i:j1]) 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 AlgorithmGA的核心是模拟自然选择一组候选解作为种群用适应度筛选出更好的个体通过交叉和变异产生下一代。对于TSP最头疼的问题在于两个合法排列交叉之后如果操作不当生成的子代很可能是非法排列。举个简单的例子父代A是[1, 2, 3, 4, 5]父代B是[5, 3, 2, 1, 4]如果按照传统单点交叉把A的前半段和B的后半段拼起来大概率会出现城市编号重复。所以我最终选择的交叉策略是顺序交叉Order CrossoverOX。它的核心思想是从父代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_size100, generations500, elite_size2): 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_dist3.3 遗传说起来简单调起来也让人头疼遗传算法的坑主要集中在两个地方一是交叉率、变异率、种群大小的组合太多了容易出现“差之毫厘谬以千里”的情况二是很容易早熟收敛也就是种群多样性快速丧失所有个体都长得差不多最终停在某个局部最优。我的实测经验是增大变异率可以在一定程度上对抗早熟但变异率太高又会破坏已经积累的好解结构变成随机搜索。折中方案是自适应变异率迭代前期变异率稍高探索解空间后期逐渐降低强化局部搜索。另外种群规模不要太小30个城市的实验我至少用100个个体50个城市用200个个体效果更稳。GA在30个城市上跑500代需要的时间稍长于SA但仍属于秒级以内。结果质量上GA跟SA基本持平但GA的优势在于并行性好种群的天然结构非常适合多进程并行评估适应度。4. 蚁群算法正反馈机制带来的神奇效果4.1 信息素与启发式信息的配合逻辑蚁群算法Ant Colony OptimizationACO是我做这个项目过程中觉得最“有意思”的算法。它的灵感来源是蚂蚁觅食蚂蚁会在走过的路上留下信息素后来的蚂蚁倾向于选择信息素浓度更高的路径浓度越高的路径又被越多蚂蚁选择形成正反馈。在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时最需要注意的是信息素的更新策略。信息素更新分两步挥发所有路径上的信息素按比例减少避免信息素无限积累导致算法僵化。沉积每只蚂蚁走完一条完整路径后在它经过的边上沉积信息素沉积量与路径总距离成反比。路径越短沉积越多这就让好路径的优势在正反馈中不断放大。def ant_colony_optimization(dist_matrix, num_ants50, alpha1.5, beta3.0, rho0.5, Q100, iterations200): 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, pprobs) 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[i1]] 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[i1]] 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越小历史信息作用越大算法更快集中到当前最优路径附近。感官直觉上rho0.5是我试过比较均衡的值alpha1.5、beta3.0在30城市数据集上表现最好。但这只是经验换一个数据集很可能要重新微调。ACO最让我惊艳的地方在于随着迭代进行信息素浓度会逐渐汇聚在最优路径的边上你能看到信息素矩阵越来越“稀疏”最终几乎只剩下一条最优路径上的值在增长。这种“进化般”的收敛过程非常有画面感。不过ACO的时间开销也是最大的每次迭代要同时模拟几十只蚂蚁构建路径而每只蚂蚁都要做N-1次概率选择。城市数量增大时计算量增长得特别快。30个城市问题不大50个城市时我就明显感觉到耗时增长了。5. 粒子群算法连续优化算法怎么解离散问题5.1 标准PSO是连续的怎么改造才适合TSP粒子群算法Particle Swarm OptimizationPSO原本是为连续优化问题设计的。粒子的“位置”是连续空间中的一个点“速度”是连续向量每个粒子根据自身历史最优位置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_size50, max_iter300, w0.8, c10.6, c20.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好很多。如果你的目标只是求解TSPPSO可能不是首选但如果你想理解“连续优化算法如何离散化适配组合优化”这类方法论问题PSO的交换序玩法值得研究。6. 四种算法横向对比与选型建议6.1 统一实验设置为了让对比结论公平我把四种算法跑在同一份30城市数据集上每种算法分别运行10次记录最优解、平均解、平均耗时和收敛趋势。参数设定如下表算法主要参数迭代/种群设计模拟退火初始温度1000降温系数0.99终止温度1e-3每个温度点200次邻域搜索遗传算法种群100交叉率0.9变异率0.1精英数2500代蚁群算法蚂蚁50alpha1.5beta3.0rho0.5200轮迭代粒子群粒子50w0.8c10.6c20.6300轮迭代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[i1:j1] reversed(new_path[i1:j1]) 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, titleTSP 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-, linewidth1) 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实验里少踩几个坑那就是它最大的价值了。
