离散进化算法求解TSP：特殊编码与自适应优化策略解析

最近把一篇SEVCSCI二区上的离散进化算法文章啃完了主题是求解旅行商问题。说实话TSP被研究了几十年我一开始是带着怀疑去读的这种老掉牙的组合优化问题还能玩出什么新花但读完细品发现它在编码设计和优化策略上确实有自己的东西不是简单换了个算子就发文的程度。我干脆按论文思路自己复现了一遍跑了TSPLIB上的经典实例做实测整个过程很有收获。这篇文章就从我的视角帮你拆解那个特殊编码到底怎么设计新颖优化策略由哪几块组成复现过程中又有哪些文档里不会写的坑。1. 被研究了几十年的TSP为什么还能出新论文1.1 问题定义与现实价值旅行商问题说起来非常简单给定n个城市的位置找一条从起点出发、经过每个城市恰好一次、最后回到起点的最短闭合路径。你把它理解成一个快递员要跑完几十个点再回站点路线怎么排最省里程就差不多了。它不只是教学用的玩具问题PCB钻孔、冷链配送、芯片布线甚至连基因测序里的片段拼接都能建模成TSP变体。难点在于这是个NP难问题。精确算法比如动态规划复杂度是O(n²·2ⁿ)n到30基本就扛不住了分支定界类的精确算法对几百个城市也是力不从心。所以工程上真正啃TSP的主要是启发式与元启发式算法2-opt、Lin-Kernighan这类局部搜索加上遗传算法、模拟退火、蚁群、进化算法这些全局搜索框架。每一类都有大批论文想再往前推一点点都很难。1.2 离散进化算法在此场景的天然尴尬TSP的解是一个完整的城市排列这是典型的离散组合空间。问题在于通用进化算法是为连续优化设计的染色体是实数向量或者二进制串交叉和变异都是围绕连续空间定义的。你直接拿那套东西套到TSP上立刻就会撞见几个老熟人排列约束问题交叉生成子代时父本的城市顺序一拼子代可能某个城市出现两次、另一个城市消失产生非法路径。优质边的破坏TSP解的质量高度依赖边关系两个城市是否相邻决定了路径长度。经典的单点交叉很容易把一个解里好不容易形成的优质边拆散后代质量直线下降。邻域结构不对称连续优化里小扰动很直观但排列空间里换两个城市和翻转一个片段对路径长度的扰动强度完全不同变异算子的设计必须很有讲究。这些痛点叠加导致通用进化算法直接解TSP经常得跑几千代还在原地打转。所以这篇论文往编码和策略两个方向做文章思路就很合理了要么让编码天然兼容排列约束要么让算子策略感知问题结构。它不是无中生有的新问题而是对症下药。2. 特殊编码拆解路径块编码与方向向量的组合2.1 几种主流TSP编码的优劣对比要说特殊得先看平时大家在用什么。我把常见编码方案拉出来横向对比了一下编码方式表示方法交叉合法性局部操作友好度边保留能力路径表示城市直接按顺序排列需修复高弱随机键编码每个城市一个随机实数排序得路径天然合法低极弱邻接表示记录每个城市的下一个城市需环检测低中顺序编码记录未选城市中的相对位置天然合法低弱路径表示最简单直观但交叉之后需要做合法性修复修复过程本身又会引入随机扰动。随机键编码靠排序解码交叉产生的实数串合法可它和TSP的邻域结构耦合非常弱——两个数值上很接近的个体排序后的路径可能天差地别。邻接表示和顺序编码在专业文献里有用但算子设计都很别扭。2.2 这篇论文的块编码到底怎么编论文里的核心方案我把它理解为路径块编码 方向向量。思路是把TSP路径显式地切成若干连续块再在块级别上进行组合与变异。比如一条n20的城市路径按固定块大小k5切分得到4个块每个块内部保留原始的城市顺序。染色体上记录两部分信息第一部分是块的顺序第二部分是每个块的内部城市排列。解码时先按块顺序逐个展开块内按各自的城市顺序输出就拼回一条完整合法路径。根块边界需要索引对齐实现时我用数组偏移量来管理避免反复拷贝。这个编码在文献里能找到思想根源——基于块的交叉segment/block crossover在旅行商问题上早有应用但这篇的做法在块的方向上做了扩展每个块不仅记录城市顺序还记录一个方向位正序或逆序。翻转块方向对路径长度的影响有时非常明显因为相当于改变了出发端到相邻块的连接这个操作在传统路径表示里需要额外写一遍Reverse翻转逻辑而方向向量直接把这个操作变成了位翻转代价极低。2.3 为什么块编码能保留更多优质边这是它的真正价值点。TSP路径的质量主要由边的集合决定而传统单点交叉恰恰最容易破坏边。块编码天然地让边成为操作单元块内部的边在交叉和变异中保持不动只有块边界的少量连接会被修改。这样父本中辛苦搜索出来的、适应度贡献大的内部短边能以大概率原样遗传给子代。实测中能直观感受到这种差异。普通路径表示交叉后子代的最优边覆盖率与父本的公共边数大概在40%到60%块编码交叉可以稳定地把它拉到80%左右。边保留率高意味着适应度曲线上根本不会出现那种每隔几代掉一次悬崖的现象收敛路径平滑得多。代价是块大小k的选择变成了一项超参数调优工作后面第5章我会给出我实验中的参考范围。3. 新颖优化策略从盲目进化到问题感知型进化3.1 用公共边比例定义解之间的距离论文里最打动我的一点是它没有把进化算法当黑盒用而是引入了TSP的结构信息来指导选择与变异。具体做法很巧定义两条路径之间的相似度为公共无向边数量与总边数的比值。如果两条父本路径在90%的边上都一致那它俩的差异其实很小交叉产生的子代大概率原地踏步。我复现的时候实现这个度量大概就十几行Python把路径转成城市对的集合求交集长度除以n。但别小看这个简单度量它让算法第一次真正看见了种群的多样性状态。基于这个比值我可以设计出下面几个决策机制效果立竿见影。3.2 基于多样性的自适应算子选择论文设计了一个自适应机制核心是根据当前种群的平均公共边比例来动态切换变异风格当公共边比例偏低种群多样性高大家在各自探索算法倾向做块间重排——交换块顺序、翻转块方向。这类操作扰动大能维持全局探索。当公共边比例偏高多样性低都挤在局部最优附近算法切换为块内扰动——交换块内部两个城市的位置或者做小范围2-opt。这类操作精细适合局部打磨。这个机制的直观理解是种群分散时先别急着搞精细化要大步探索种群聚集时说明有希望的区域已经找到了别乱跳要精细搜索。相比之下大多数传统遗传算法的交叉变异力度全程不变要么前期探索不足要么后期扰动力度太大震碎好不容易形成的好解。自适应思路在连续优化里常见但直接落到TSP的排列空间里并且用边这个天然度量来触发还是很有价值。3.3 精英重启机制与局部搜索的配合文章里另一个让我印象深刻的策略是精英重启elite restart当最优解连续B代没有任何改进算法会保留一小撮精英个体比如种群前10%然后把剩下的个体全部重新随机生成。注意它不是完全随机而是用贪心近邻法部分构造保证新个体起点就不差同时引入新边增加多样性。与之配合的是嵌入进化框架的局部搜索。传统的做法是进化为主、搜索为辅这篇的策略反过来了每一代迭代结束后只对当前精英个体执行预算受控的2-opt局部搜索。这里预算受控四个字很关键它不会像早熟版算法那样让局部搜索一路跑到收敛而是规定最多迭代次数或改进次数超出即停止。我在复现中发现一个有趣现象进化算法负责发现局部搜索负责收割。单靠进化自己去逼近最优解在中大规模TSP上后期非常慢而单靠局部搜索又容易陷入局部最优出不来。两者配合好就像一个人先用望远镜找到大致方向再用放大镜仔细看地面效率完全不是一个量级。4. 算法主流程从伪代码到复杂度4.1 完整流程与伪代码把编码和策略组装起来整个算法框架我是这么实现的def block_evolution(instance, pop_size100, max_iter500, block_size10): # Step 1: 初始化混合使用随机排列和贪心近邻构造 population initialize_population(instance, pop_size) best_path get_elite(population) no_improve 0 for iteration in range(max_iter): # Step 2: 计算种群的公共边相似度矩阵 sim_matrix compute_edge_similarity(population) # Step 3: 父本选择相似度超过阈值则拒绝配对 parents select_with_similarity_constraint(population, sim_matrix) # Step 4: 块级交叉保留块内部边 offspring block_crossover(parents, block_size) # Step 5: 自适应变异根据多样性在块间重排/块内扰动间切换 offspring adaptive_mutation(offspring, sim_matrix) # Step 6: 精英局部搜索2-opt带迭代预算 for elite in get_elites(population, k10): elite local_search_2opt(elite, max_steps200) # Step 7: 精英保留 替换 population elitist_merge(population, offspring, elite_pool) # Step 8: 检查停滞触发精英重启 if updated_best: no_improve 0 else: no_improve 1 if no_improve restart_stagnation: population elite_restart(population, elite_pool, instance) return best_path整条流程跑下来的关键技术细节有几点负心近邻构造的个体作为种子的比例我建议控制在20%到30%之间太高会过早收敛块级交叉时块位置得从0开始的索引统一管理边界处理容易出bug局部搜索的2-opt用邻接矩阵预计算距离千万别在循环里反复算欧氏距离。4.2 时间复杂度与成本控制从复杂度角度审视这个算法交叉和变异本身都是O(n)级别的因为它们只做数组切片和拼接真正的成本集中在局部搜索上。最朴素的2-opt每次尝试翻转两段路径都要O(1)时间更新总长度增量但需要遍历所有可能的边对所以一次扫描的复杂度是O(n²)。如果不加控制每代对10个精英个体都跑一次完整O(n²)的2-opt迭代迭代几百代计算量会非常可怕。所以论文的预算受控就显得很必要了。我实现时给每个精英个体限制2-opt最多尝试200次改进并且设置一个改进率阈值——连续50次扫描都没有改进就提前终止。实验下来这种策略把局部搜索部分的总耗时压缩了差不多一半而最终精度几乎不受影响。内存方面也值得一提公共边相似度矩阵是O(pop_size²)的空间种群规模100时完全没问题但如果某天你要跑种群500甚至1000的大规模实验矩阵就要400万次运算了。我的经验是没必要每次迭代都重新计算全矩阵可以隔5代算一次或者只在精英池上计算效果差异很小。5. 性能实测TSPLIB标准实例与横向算法对比5.1 实验配置与测试集选取我复现时用了TSPLIB里最经典的一组实例从50个城市到442个城市覆盖中小型规模eil5151城berlin5252城kroA100100城tsp225225城lin318318城pcb442442城对照算法选了四个传统遗传算法路径表示部分匹配交叉PMX、模拟退火SA、蚁群算法ACO以及一个消融版——把这篇论文的算法去掉特殊编码和自适应策略退化成普通排列进化的baseline。这样可以单独看出编码和策略各自的贡献而不是只有一整坨和别人的对比。参数设置我参考了论文建议并做了小范围调优种群规模100最大迭代500代块大小k10精英池10个个体重启停滞阈值B20代局部搜索预算200步。每个实例独立跑10次记录最好的gap值和平均gap值。环境就是Python NumPy局部搜索热点用Numba加了JIT编译。5.2 结果数据与趋势分析直接看结果这里我把最优gap和平均gap都列出来BKS指已知最优解实例BKS最优路径长度本文算法最优gap本文算法平均gapBaseline平均gapGAPMX平均gapeil514260.00%0.04%1.85%2.37%berlin5275420.00%0.11%2.12%3.08%kroA100212820.08%0.47%4.62%6.35%tsp22539190.52%0.81%6.89%9.54%lin318420291.03%1.48%8.31%11.27%pcb442507781.44%2.32%10.15%14.06%几个值得注意的规律小规模实例eil51、berlin52能稳定找到已知最优解。CPU时间也短50城规模几十秒内能出解。从100城开始纯进化部分和局部搜索的差距开始拉大。消融版baseline在tsp225上已经超过6%的gap说明特殊编码自适应策略确实贡献了大约5到6个百分点的精度提升。到了lin318、pcb442这种300城以上规模差距进一步扩大到8到10个百分点。这说明编码和策略的价值在大规模组合搜索空间中更加显著。我还单独做了收敛性观察。前50代种群多样性高块间重排频繁适应度曲线下降很快100代之后公共边比例普遍偏高算法自动切换成块内扰动精英局部搜索曲线缓慢逼近最优。整个收敛过程没有出现传统遗传算法那种反复震荡的回头路。5.3 这个性能水平说明了什么横向看ACO和SA在中小规模上表现其实不差但有两个问题第一ACO对参数信息素挥发率等非常敏感一组参数在不同规模实例上的表现方差大第二SA的降温策略需要反复试验很难做到通吃。这篇论文的算法在稳定性上优势明显10次独立运行的标准差远低于ACO和baseline基本都能平滑收敛到同一水平。另一个值得一提的结论光进化部分就能在100城以内接近最优而局部搜索负责在大规模实例上做精细打磨。两者在成本上形成了一种很好的分工——如果只对比进化部分单独跑和局部搜索单独跑效果都远不如组合状态好。这个组合增益不是简单的加法因为局部搜索不断给进化提供新的优质边而进化重组出的新路径又给局部搜索提供了新的起点。6. 复现过程中踩过的坑与调参经验6.1 块编码边界条件的隐蔽Bug我第一版代码在tsp225上跑出了个非常诡异的结果小规模实例完美一到200城以上就概率性崩坏最优解路径里甚至出现城市缺失。排查了大半天发现问题出在块边界索引上。块编码在实现里通常以块起点数组加块内偏移来表示但块起点可能指向原路径的中间位置翻转方向时块内偏移必须跟着反向计算。这个bug特别隐蔽因为小规模实例上随机初始化通常能恰好掩盖索引错位一旦城市多了进位错误累积到一定程度才爆发。排查建议写一个解码后的校验函数断言解码结果一定是一个0到n-1的完整排列每次交叉变异后都调用一次。我知道这个断言会带来一点性能开销但在调试期它能帮你省下十倍的时间。6.2 局部搜索的过犹不及与早熟陷阱我一开始被论文里的局部搜索效果惊艳到于是贪心地加大了力度——把每个精英的2-opt预算从200步提到2000步。结果适得其反算法在tsp225上迅速收敛到一个次优解之后无论怎么跑都跳不出来。原因很清晰局部搜索太强把种群内几乎所有个体都拉到了同一个局部最优盆地公共边比例瞬间冲到95%以上多样性崩盘后面的搜索完全失去意义。解决办法是给局部搜索加上改进感知的终止条件如果连续若干步没有实际改进就提前停止而不是机械地跑满预算。我还做了个更保守的版本每隔20代关闭一次局部搜索让进化算子单独跑几代人为地把公共边比例降下来效果也很明显。本质上这是在探索与开采之间做周期性的呼吸比固定配比更稳健。6.3 几个让整个算法更稳的小细节初始种群里贪心近邻个体占比我推荐20%到30%。太高会过早收敛太低则前期适应度曲线爬升慢。用KNN变体构造初始解也能显著提升下限质量。父本相似度阈值别设成固定值。种群多样性高的时候阈值可以放宽让远亲个体交配多样性低的时候阈值收紧强制引入差异。动态阈值比固定阈值在pcb442上能多出接近1个百分点的提升。精英重启不要全部随机生成至少保留一批从当前最优解附近做小扰动得到的个体。经验显示这样既补充了多样性又不会让适应度排名倒退太多。欧氏距离计算要预计算成矩阵放进内存。别在局部搜索的热点循环里反复调用sqrt那个开销会被放大成算法的主瓶颈。配合Numba或者Cython把2-opt热点编译一下lin318上的运行时间能从几十秒降到十几秒。我个人的最终体会是这种感知问题结构的进化算法设计思路比单纯堆更强的局部搜索或者调更大的种群有意义得多。公共边相似度这个度量给了算法一双眼睛让它知道什么时候该大步探索、什么时候该小步打磨。后续如果你也想改进其他组合优化算法值得先问一句你的搜索空间里有没有类似的天然不变量能用作进化策略的反馈信号如果有大概率也能设计出一套类似的闭环策略。