旅行商问题算法浅析

摘 要：旅行商问题作为计算机学界一个经久不衰的热门话题。自被提出以来，便有着诸多算法来试图解决该问题或是得出接近精确解的答案。总体介绍了旅行商这一问题的背景以及建模，并且浅析了三种经典算法-LKH，遗传算法，蚁群算法，介绍了他们的原理以及改进。在此基础上，还指出了这三种算法在TSP问题领域的影响，展望了后续算法的发展，给出一个可能发展的新方向。

关键词：旅行商问题；LKH；遗传算法；蚁群算法

Analysis of some traveling salesman problem’s algorithms

Abstract:Traveling salesman problem is a hot topic in computer field. Since it was proposed, there have been many algorithms to try to solve this problem or get an answer that approximates the exact solution. This paper introduces the background and modeling of travel agent, and analyzes three classical algorithms -LKH, genetic algorithm, ant colony optimization, introduces their principle and improvement. The influence of these three algorithms on THE TSP problem field is also pointed out, and the future development of these algorithms is forecasted. A new direction of possible development is given.

Key word:Travel salesman problem; LKH; Genetic algorithm; Ant colony optimization

旅行商问题TSP（Traveling salesman problem）是组合优化领域著名的NP-hard问题之一，该问题的经典提法为：“一位旅行商要去各城市推销货物，从城市1出发，经其余各城市至少各一次，最后返回城市1，请问如何规划路线使得总行程最短。”该问题具有较为广泛普及的工程方面应用以及现实问题的背景；如印刷电路钻孔、安排飞机航线航路、建设公路高铁网络、设置网络通信节点、物流货物配送、超市货物上架等实际应用问题都可以转化为TSP问题来进行求解。因此，快速，高效的解决TSP问题是很有必要的。

在图论意义下，TSP问题即是在一个无向正权图中，寻找一个最小的Hamilton圈。当前，针对TSP问题的算法层出不穷，由于TSP问题是一个NP难问题，无法找出一个最优的完备多项式算法，例如：对于16个城市的旅行商问题，如果用穷举法来进行求解，那么需比较的可行解即有15!/2=653,837,184,000个。尽管到了现代，计算机的计算能力大大提升，而且有了一些指数级的计算方法可以用来解决旅行商问题；但由于它们在大规模问题上的失效，人们转而去寻求在可接受时间内得到可接受近似解的启发式算法，现有的解决TSP问题的启发式算法主要分为两类：第一类是简单启发式算法，如贪心算法、局部搜索算法（如2-OPT，3-OPT，LK，LKH）等；另一类是元启发式算法，包括模拟退火，遗传算法，蚁群算法，多级归约，人工免疫等。大部分算法是以局部搜索为基础，本文将浅析LKH，遗传算法与蚁群算法这三种经典算法。

通常TSP问题可以在无向赋权图上进行解决。设G=（V,E）为赋权图，V={1,2,3……n}为顶点集，E为边集，各顶点间距离为\(d_{ij}\)。已知\(d_{ij}\)>0，\(d_{ij}\)=+∞，i、j∈V，并设：

\(x_{ij}=\begin{cases} 1, & 边(i,j)在最优线路上 \\ 0, & 其他 \end{cases}\)

则旅行商问题的数学模型可以改写为如下的线性规划形式：

\(MinZ=\sum_{i\ne j}^{} d_{ij}x_{ij}\) \(s,t=\begin{cases} \sum_{j\ne i}^{} x_{ij}=1, & i\in V \\ \sum_{i\ne j}^{} x_{ij}=1, & j\in V \\ \sum_{i,j\in S}^{} x_{ij}\le |K|-1, & K\subset V \\ x_{ij}\in \{0,1\} & i,j\in V \end{cases}\)

这里K为V的所有非空子集，|K|为K的阶，即K中包含G的顶点数。前两个约束意味着对每个顶点而言，仅有一条边进，一条边出；后一约束则保证没有任何子回路解的产生。于是，满足上述约束条件的解则为一条Hamilton回路。

LKH算法是LK算法的一种改良算法。LKH算法主要在候选集的建立，边的搜索与交换等方面进行了改良。

基础的LK算法主要有四个步骤，分别是： Step1：根据一定的规则选出候选顶点集，人为的规定该顶点只能与候选集中的顶点相连。 Step2：产生初始路线。 Step3：对每一个顶点进行r-opt交换，直至无法改进当前解为止。 Step4：输出当前解作为结果。

图2-1 LK算法步骤

Fig.2-1 LK algorithm steps

LK算法是一种经典的改进算法。该算法由一个初始可行解出发，每一次从路径中选出r条边，如果可以通过交换的方式来减少路径的长度，则进行交换。否则再另选r条边进行相同的操作。

1.候选集的建立 候选集是指在搜索过程中，人为地限定与某一顶点相连的顶点集。显然，候选集越小，搜索所需时间越少，同样错过最佳解的概率也就越大。一般LK算法会选择权值最小的r条边来构成候选集。这种方法虽然思路简单，但对r值的要求很高，在大规模的数据量下，会造成大量的时间浪费。 LKH算法改进了这一点，依托于a-nearness的大小来进行计算，而a-nearness的计算依赖于顶点带罚值的最小权1生成树。a-nearness的计算公式为：a(i,j)=L(T(i,j))-L(T)，其中L(T)为将顶点i,j相连后生成的最小权1生成树的权值，而L(T)则代表最小权1生成树的权值，将每一个顶点与其相邻的顶点的a-nearness算出来，并排序选出最小的前r个，即可组成新的候选集。 2.边的搜索与交换 LK算法在边的搜索与交换过程中一般采取的是以顺序3-opt交换为根本，辅以一些非顺序的4-opt交换，在维持较高计算效果的同时，尽可能地压缩时间成本，保证收益最大化。而LKH算法在此处也做出了改进，以顺序的5-opt为主，辅以一些非顺序的2-opt与3-opt，来达到4-opt的效果。不过由于5-opt的时间成本过高，所以必须按照上面的方法来选择候选集，才可以降低5-opt的时间成本。利用这种方法，LKH算法成功大大降低了错过最优解的情况。

LKH算法是目前解决TSP问题精度很高的近似算法，还有相关研究在对LKH算法做进一步扩展，例如将此算法与精确算法进行结合，先用LKH算法解决问题，再将此解作为上界，利用整数规划的方式求解原问题。由于LKH算法得出的解极为优秀，大大缩短了后续步骤的时间，这也使得其解决了Sweden24978。相信还会有更多更有效的算法会与LKH相结合，进一步得出快速解决TSP问题的方法。

这是一种寻求全局最优解而不需要任何初始化信息的高效优化方法[1],它基于生物学的自然选择原理和自然遗传机制模拟生命的进化,这种完全异于传统思想的搜索和优化方法自John Holland(1995)提出以来,获得了广泛的应用[2]，其中解决属于组合优化领域的TSP问题也是其重要的应用。

这个算法中要用到各种进化和遗传学的概念。这些概念如下[3]： 1)个体(Individual) 指染色体带有特征的实体。 2)串(String) 它是个体(Individual)的形式，在算法中为二进制，并且对应于遗传学中的染色体(Chromosome)。 3)基因(Gene) 基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1 这4个元素分别称为基因。其值称为等位基因(Allele)。 4)种群(Population) 染色体带有特征的个体的集合称为种群。该集合内个体数称为群体的大小。有时个体的集合也称为个体群。 5)基因特征值(Gene Feature) 在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011 中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。 6)串结构空间\(s^s\)在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。 7)参数空间\(r^s\)这是串空间的物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。 8)非线性 它对应遗传学中的异位显性(Epistasis)。 9)适应度(Fitness) 表示某一个体对于环境的适应程度。 10)复制(Reproduction) 细胞在分裂时，遗传物质 DNA 通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因。 11)交叉(Crossover) 有性生物在繁殖下一代时两个同源染色体之间通过交叉而重组，亦即在两个染色体的某一相同位置处 DNA 被切断，其前后两串分别交叉组合形成两个新的染色体。这个过程又称基因重组recombination，俗称“杂交”。 12)变异(Mutation) 在细胞进行复制时可能以很小的概率产生某些复制差错，从而使 DNA 发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。 13)编码(Coding) DNA 中遗传信息在一个长链上按一定的模式排列，也即进行了遗传编码。遗传编码可以看作从表现型到遗传子型的映射。 14)解码(Decoding) 从遗传子型到表现型的映射。

主要计算过程如下[4]： Step 1: 确定编码机制，生成初始种群。解决 TSP问题通常采用城市序号对路径进行编码，按照访问城市的顺序排列组成编码。 Step 2: 计算种群中每个个体的适应度值。TSP求解是要寻找使目标函数最小的个体，因此选择适应度函数

设置常数D, 防止路径值过大而导致适应度函数倒数接近于0。可以看出, 巡游路径越小, 适应度值越大。 Step 3: 选择算子。通常采用精英个体保存策略和赌轮选择算子, 即适应度最高的个体一定被选择。

通过随机数r所在的区间范围选择遗传个体。 Step 4: 交叉算子。由交叉概率选择若干父体并进行配对, 按照交叉算法的规则生成新个体, 常用的规范方法有单点交叉、部分映射交叉、循环交叉等. Step 5: 变异算子。为了保持种群个体的多样性，防止陷入局部最优，需要按照某一变异概率pm随机确定变异个体，并实行相应变异操作，通常采用逆序 变异算子。 Step 6: 迭代终止条件。若满足预定的终止条件(达到最大迭代次数)，则停止迭代，所得的路径认为是满意的路径；否则，转至 Step 2，计算新一代种群中每个个体的适应度值。 以上步骤如图3-1所示：

图3-1 简单遗传算法步骤

Fig.3-1 Simple genetic algorithm steps

TSP的一个纪录是由遗传算法 (GA) 得到的：永田裕一(2006) [5]的EAX-GA（edge assembly crossover - Genetic Algorithm）解出了十万个节点的TSP已知最好的路线。简单遗传算法往往存在收敛速度慢、易陷入局部最优和优化精度低等明显不足，所以一般认为 GA 在复杂的大型实际问题中的效果仅仅是“聊胜于无”，如何在提高算法收敛速度的同时确保种群多样性，使寻优结果接近最优解是遗传算法不断改进的目标[6]，而永田裕一基于Lin-Kernighan的局部搜索设计了有效的交叉算子改进了遗传算法使其时至今日仍旧十分先进[7]。 近年仍有不少国内学者在研究遗传算法的改进算法以研究TSP问题[8]，或者与其他算法相结合，例如与模拟退火算法结合[9]，与蚁群算法结合[10]。可见遗传算法在TSP领域仍充满活力。

蚁群算法，相对于遗传算法是一种比较新的算法，最早是由意大利学者Colorni A., Dorigo M. 等于1991年提出。它是一种仿生学算法，其来源于自然界中蚂蚁觅食的行为。由于蚂蚁自身具有的一些生物学特点以及行为方式，在觅食过程中蚁群总是能找到一条最优的路径。 受此启发的蚁群算法是一种群智能算法，它是由一群无智能或有轻微智能的个体（Agent）通过相互协作而表现出智能行为，从而为求解复杂问题提供了一个新的可能性。而其最早的应用则是用来求解旅行商（TSP）问题。

蚁群个体之间通过信息素间接进行信息交流, 由简单的蚂蚁个体组成的集体能够完成单个蚂蚁难以完成的一些复杂工作。基本蚁群算法的数学模型通过对n个城市的经典TSP问题分析给出。 1）n个城市的经典TSP问题, 是人工蚂蚁从n个城市任选一个为起始城市, 开始随机访问下个城市且对其余城市仅访问一次, 最终回到起始城市, 最终目的是寻找一条最短的访问路线。人工蚂蚁在寻优过程中, 依据不同路径上信息量以及启发式信息等来计算状态转移概率。计算概率的公式如（1）式。

由于最基本的蚁群算法是由每一只蚂蚁进行移动，并由它自己决定自己的禁忌表，同时只有自己在移动，因此该算法的终止条件有两个，即周游计数器达到最大，或者所有的蚂蚁都走同一路线，即停滞状态。由于停滞状态的可能性，导致基本的蚁群算法可能无法有效的解决TSP问题。

相遇算法基本思路是将一只蚂蚁的一次周游改为两只蚂蚁分头进行。当这两只蚂蚁在路途中相遇，将这两只蚂蚁的周游路线组合成一次周游路径，即得到一次循环的结果。 该算法的大致思想是让两只蚂蚁在同一城市出发，两只蚂蚁共用一个禁忌表。第一只蚂蚁前进后，第二只蚂蚁不得走禁忌表中和第一只蚂蚁走过的城市。相比于仅用一只蚂蚁的算法，该改进方式有两次选择下一城市的机会。 实践证明，相遇算法在最好值，最差值，偏差和平均值四方面都优于基础算法。但是由于本质上没有改变，因此只是在一定程度上改善了蚁群算法的性能。

这种方法概括来说是用粒子群算法的一个粒子来表示蚁群算法的一组参数，通过求解参数坐标来寻找最优值。在寻找过程是中以蚁群算法中的路径长度判断优劣。这种改进方式是一种全局异步和经营策略相结合的信息素更新方式，合理确定了迭代代数。 与传统算法相比，在解的质量相差较小时,可以缩短搜索时间，在同一时间尺度下,可求得质量较高的解，在处理较大规模TSP时优越性更为明显。

旅行商问题作为在计算机学界的一个热门话题，自被提出以来，人们一直在尝试去解决或者得出一个接近精确解的答案。人们相继提出了线性规划等直接解决的算法，或是解决此类NP-hard问题的启发式算法。本文总体介绍了旅行商问题，并且浅析了三种经典算法-LKH、遗传算法、蚁群算法。由这三种算法可以看出，人们一直未曾放弃去找出一个更好的算法来求解TSP。还可以看出，对于现在的计算机领域，算法与算法之间，学科与学科之间都存在着一个相互交叉融合的趋势。相信在未来，会出现更好更精确的算法来解决TSP。

参考文献： [1] 任子武, 伞冶. 自适应遗传算法的改进及其在系统辨识中应用研究[J]. 系统仿真学报, 2006, 18(1): 41-43. [2]黄厚生. 求解旅行商问题的新方法研究[D].天津大学,2005. [3]王银年. 遗传算法的研究与应用[D].江南大学,2009. [4]于莹莹,陈燕,李桃迎.改进的遗传算法求解旅行商问题[J].控制与决策,2014,29(08):1483-1488.DOI:10.13195/j.kzyjc.2013.0598. [5] Yuichi Nagata. New EAX Crossover for Large TSP Instances[J].Parallel Problem Solving from nature - PPSN IX, pp 372-381.2006. [6] 库克. 迷茫的旅行商:一个无处不在的计算机算法问题 (隋春宁 译)[M], 人民邮电出版社, 2013. [7]石利平.改进型遗传算法求解TSP问题[J].实验技术与管理,2014,31(07):61-64.DOI:10.16791/j.cnki.sjg.2014.07.018. [8]刘锦. 混合遗传算法和模拟退火算法在TSP中的应用研究[D].华南理工大学,2014. [9]陶丽华,马振楠,史朋涛,王瑞峰.基于TSP问题的动态蚁群遗传算法[J].机械设计与制造,2019(12):147-149+154.DOI:10.19356/j.cnki.1001-3997.2019.12.037. [10]李悦乔. 求解动态多目标TSP问题的一种基于LKH的算法研究[D].中国地质大学,2007. [11]肖艳秋,焦建强,乔东平,杜江恒,周坤.蚁群算法的基本原理及应用综述[J].轻工科技,2018,34(03):69-72. [12]吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报,2001(12):1328-1333. [13]李擎,张超,陈鹏,尹怡欣.一种基于粒子群参数优化的改进蚁群算法[J].控制与决策,2013,28(06):873-878+883.DOI:10.13195/j.cd.2013.06.75.liq.016.