TSP

Posted on | In |
Words count in article: 6.5k | Reading time ≈ 22

我与TSP

我第一次接触TSP还是在今年寒假数学建模的时候，通过GA算法求解30个城市的TSP问题。
1
当时用matlab实现的GA算法求解，看到这个动态搜索的结果我突然对这个问题产生了浓厚的兴趣，一直想要深入研究一下TSP问题，但中途总是被一些其他事情打断了。。。
幸好，在算法设计与实践课上，TSP这个老朋友又被多次提及，于是借着算法课读书汇报的契机，终于能对TSP问题做一次比较深入的了解，以下是我做的一点小小的总结笔记。

引言

TSP（Travelling salesman problem）问题是组合数学中一个古老而又困难的问题，已经被证明是一个NP难问题(即在P≠NP的假设下，找不到一个多项式时间算法来求解其最优解)。
由于TSP问题代表一类组合优化问题，在工程应用和现实生活中有着广泛应用，如计算机网络、电子地图、交通诱导、连锁店货物配送、航班着陆排序、电路板钻孔路线等。鉴于其重要的工程与理论价值，TSP常作为算法性能研究的典型算例[1]。

简介

TSP（Travelling salesman problem）问题 , 即旅行推销员问题，是指：若给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。


1
在1930年,TSP问题首次被形式化，并且是在最优化中研究最深入的问题之一。
许多优化方法都用它作为一个基准,甚至纯粹形式的TSP都有若干应用，如企划、物流、芯片制造。稍作修改，就是DNA测序等许多领域的一个子问题。在这些应用中，“城市”的概念用来表示客户、焊接点或DNA片段，而“距离”的概念表示旅行时间或成本或DNA片段之间的相似性度量。
甚至TSP还用在天文学中，观察很多源的天文学家希望减少在源之间转动望远镜的时间。


尽管问题在计算上很困难，但已经有了大量的启发式和精确方法，因此可以完全求解城市数量上万的实例，并且甚至能在误差0.05%范围内估计上百万个城市的问题$^{[1]}$。

TSP问题的求解算法很多，按照不同的标准可以有不同的分类，一般将求解 TSP问题的算法分为精确算法和近似算法。[2]

精确算法

蛮力法

思路：
找出所有可能的旅行路线，从中选取路径长度最短的哈密顿回路。


算法分析：
依次考察顶点集合的所有全排列，从中找出路径最短的简单回路，因此其时间下界是$Ω(n !) $


优点：
1）在时间允许的条件下，一定能够得到全局最优解。
2）结构简单，易于实现。
3）暂用内存较少。
缺点：
1）速度慢。
2）组合爆炸问题：当城市个数达到12的时候，需遍历479001600种路径，程序耗时以“小时”为单位。
3）不适用于大规模数据中，具体问题具体分析。

动态规划法

思路：
首先证明其满足最优性原理：
设$s, s_1, s_2, …,s_p,s$是从$s$出发的一条路径长度最短的简单回路，
假设从$s$到下一个城市$s_1$已经求出，则问题转化为求从$s_1$到$s$的最短路径，显然$s_1, s_2, …, s_p, s$一定构成一条从$s_1$到$s$的最短路径。
否则，设$s_1, r_1, r_2, …, r_q, s$是一条从$s_1$到$s$的最短路径且经过$n-1$个不同城市，则$s, s_1, r_1, r_2, …, r_q, s$将是一条从$s$出发的路径长度最短的简单回路且比$s, s_1, s_2, …, s_p, s$要短，从而导致矛盾。
所以，TSP问题满足最优性原理。


定义子问题：
对于图$G=(V, E)$，假设从顶点$i$出发，令$V′=V-i$，则$d(i, V′)$表示从顶点$i$出发经过$V′$中各个顶点一次且仅一次，最后回到出发点$i$的最短路径长度；
显然，初始子问题是$d(k, \lbrace \rbrace )$，即从顶点$i$出发只经过顶点$k$回到顶点$i$.
现在考虑原问题的一部分，$d(k, V’-\lbrace k\rbrace)$表示从顶点$k$出发经过$V’-\lbrace k\rbrace$中各个顶点一次且仅一次，最后回到出发点$i$的最短路径长度，则：
title
状态转移方程：
$$D[v1][V] = W[v1][vi] + min(D[vi][V - vi])$$


算法分析：
时间复杂度：
1
空间复杂度：
2 即$O (n·2^n)$
故一般除了很小规模的问题外, 几乎不予采用。

贪心法

  • 最近邻点策略

思路：
从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。


算法分析：
算法时间性能为$O(n^2)$，因为共进行$n-1$次贪心选择，每一次选择都需要查找满足贪心条件的最短边。
但是用最近邻点贪心策略求解TSP问题所得的结果不一定是最优解，当图中顶点个数较多并且各边的代价值分布比较均匀时，最近邻点策略可以给出较好的近似解，不过，这个近似解以何种程度近似于最优解，却难以保证。

  • 最短链接策略

思路：
每次在整个图的范围内选择最短边加入到解集合中，但是，要保证加入解集合中的边最终形成一个哈密顿回路。
因此，当从剩余边集$E’$中选择一条边$(u, v)$加入解集合$S$中，应满足以下条件：
① 边 $ (u, v)$ 是 边 集 $ E’$ 中 代 价 最 小 的 边；
② 边 $ (u, v) $加 入 解 集 合 $ S $ 后，$S$中不产生回路；
③ 边 $ ( u, v ) $加 入 解 集 合 $ S$ 后，$S$中不产生分枝。


算法分析：
共进行$n-1$次贪心选择，在每一次贪心选择中：
如果顺序查找$E′$中选取最短边$(u, v)$，则算法的时间性能是$O(n^2)$；
如果采用堆排序的方法将集合$E′$中的边建立堆，则可以将选取最短边的操作提高到$O(\log_2n)$，可以用并查集的操作考察两个顶点是否连通以及是否会产生分枝，其时间性能为$O(\log_2n)$，此时算法的时间性能为$O(n\log_2n)$.

回溯法

思路：
(1). 确定问题的解空间(用树表示);
(2). 确定问题的约束条件和边界条件;
(3). 深度优先搜索解空间幷根据约束条件和边界条件进行裁剪;


算法分析：
回溯法在包含问题的所有可能解的解空间树中，从根结点出发，按照深度优先的策略进行搜索，如果该结点满足问题的约束条件，则进入该子树继续进行搜索，否则将以该结点为根结点的子树进行剪枝。
回溯法的有效性往往体现在当问题规模$n$ 很大时，在搜索过程中对问题的解空间树实行大量剪枝。但是，对于具体的问题实例，很难预测回溯法的搜索行为，特别是很难估计出在搜索过程中所产生的结点数，这是分析回溯法的时间性能的主要困难。

分支限界法

思路：
1
2
3


算法分析：
分支限界法按广度优先策略搜索问题的解空间树；
在搜索过程中，对待处理的结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值（极大或极小）的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。
类比回溯法分析分支限界法的时间性能，在最坏情况下，时间复杂性为指数阶。但与回溯法不同的是，分支限界法首先扩展解空间树中的上层结点，并采用限界函数，有利于实行大范围剪枝，同时，根据限界函数不断调整搜索方向，选择最有可能取得最优解的子树优先进行搜索。
分支限界法的较高效率是以付出一定代价为基础的，其工作方式也造成了算法设计的复杂性。

线性规划法

1

近似算法

1

生成树算法

思路：
1

  1. 在图中任选一个顶点$v$;
  2. 采用$Prim$算法生成以顶点$v$为根结点的最小生成树$T$；
  3. 对生成树$T$从顶点$v$出发进行深度优先遍历，得到遍历序列$L$；
  4. 根据$L$得到图$G$的哈密顿回路；

算法分析：
title
title
title
所以算法的近似比为$2$.

遗传算法(GA)

遗传算法(Genetic Algorithm ，GA )是通过模拟生物进化过程来完成优化搜索的，由美国 J. Holland 教授提出的一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。它起源于达尔文的进化论，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不以梯度信息为基础。它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。作为一种全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及应用范围广等特点，使其成为21 世纪智能计算核心技术之一。

//GA相关参数
#define CITY_NUM 150                // TSP_城市个数  
#define GROUP_NUM 30                // 群体规模  
#define SON_NUM 32              // 产生儿子的个数  SON_NUM = GROUP_NUM + 2  
const double P_INHERIATANCE = 0.01; // 变异概率  
const double P_COPULATION = 0.8;    // 杂交概率  
const int ITERATION_NUM = 1500;     // 遗传次数(迭代次数)  
const double MAX_INT = 9999999.0;  

typedef struct{  
    int vex_num, arc_num;           // 顶点数 边数  
    int vexs[CITY_NUM];         // 顶点向量  
    double arcs[CITY_NUM][CITY_NUM];    // 邻接矩阵  
}Graph;  

typedef struct{  
    double length_path;  
    int path[CITY_NUM];  
    double P_Reproduction;  
}TSP_solution;

思路：
步骤一、初始化参数；
步骤二、随机产生一组初始个体构成的初始种群，并评价每一个个体的适配值（路径长度决定）；
步骤三、判断算法的收敛准则是否满足（此处为迭代次数）。若满足输出搜索结果；否则执行[4-8]步骤；
步骤四、执行选择操作（随机选择两个种群个体），使用【轮盘赌选择】思想，每次按照概率大小随机返回当前群体中的某个个体的下标；
步骤五、按杂交概率const double P_COPULATION = 0.8;执行交叉操作；
步骤六、对子群Son_solution[]进行变异处理，产生随机数RateVariation，小于变异概率P_INHERIATANCE时，进行变异处理（随机交换两个城市的位置）；
步骤七、更新Son_solution[]的路程和概率Calc_Probablity(G, total_length)；
步骤八、采用“父子混合选择”更新群体（精英保留策略）； 步骤九、返回步骤（2）判断是否进行下一次迭代；


算法分析： 本算法的结束准则是根据指定了的迭代次数，当算法达到迭代次数时，算法结束，输出当前的最优解； 在根据适配值计算并选择的时候，记录下来的当前最优值，在变异后加入跟新的群体，保证新的迭代循环中TSP解越来越好（不会变差）；
在选择的一种操作是拿最优的K个替换最差的K个子个体，本例是按适配值选择，并使群体数目变少，当每次变异操作后，产生随机路径补充群体是群体数目不变，再次循环，一定程度上防止因初始群体的选择问题而陷入局部最优。

演示demo

蚁群算法(ACA)

蚁 群 算 法 (ACA，ant colony algorithm)是 由 意 大 利 学 者 Marco Dorigo等人于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径的行为而提出的一种仿生寻优算法。
参加寻径的蚂蚁通过留在链路上的信息素交互来选择新的路 由从而达到寻优的目的。
其基本特征是:本身是一个增强型学习系统，具有分布式的计算特性，具有很强的顽健性。
蚁群算法原理包括三个基本要点:
1)状态转移规则，即蚂蚁在访问一个结点后如何选择下一个结点;
2)信息素的全局更新规则，即当所有蚂蚁成功地完成一次寻径过程后如何选出使目标函数值最小的路由，用以完成全局信息素的更新;
3)信息素的局部更新规则，即对于单独的一只蚂蚁如何更新它所经过的路径上的信息素。
算法原理导出了蚁群算法所需的四个基本参数:
α为路径轨迹的相对重要性;
β为路径能见度的相对重要性;
ρ 为信息素的消逝因子;
Q 为寻径中开发最优解或探寻搜索空间的选择门限值。


思路：
1，随机生成距离矩阵
2，信息素递减（只有较近的信息素才能影响这一步）
3，对于每一只蚂蚁，随机生成起点，标记起点为访问过
进入循环（寻找城市数量-1次）(起点已经有了）
4，寻找周围城市的最大信息素
5，随机生成0~1的数如果小于bugp(蚂蚁正常选择）则从最大信息素城市中找一个作为下一个
6, 标记这个点被访问过
修改信息素，修改方式为原来信息素+Q/这条路径长度（Q为1个常数)
7，输出最优解。


算法分析：
正反馈：
单个的蚂蚁为了避免自己迷路，它在爬行时，同时也会释放一种特殊的分泌物——信息素（Pheromone），而且它也能觉察到一定范围内的其它蚂蚁所分泌的信息素，并由此影响它自己的行为。当一条路上的信息素越来越多（当然，随着时间的推移会逐渐减弱），后来的蚂蚁选择这条路径的概率也就越来越大，从而进一步增加了该路径的信息素浓度，这种选择过程称为蚂蚁的自催化过程。
多样性：
同时为了保证蚂蚁在觅食的时候不至走进死胡同而无限循环，蚂蚁在寻找路径的过程中，需要有一定的随机性，虽然在觅食的过程中会根据信息素的浓度去觅食，但是有时候也有判断不准，环境影响等其他很多种情况，还有最终要的一点就是当前信息素浓度大的路径并不一定是最短的路径，需要不断的去修正，多样性保证了系统的创新能力。
正是这两点小心翼翼的巧妙结合才使得蚁群的智能行为涌现出来。

模拟退火算法（SAA）

模拟退火算法（Simulated annealing algorithm，SAA）在处理全局优化、离散变量优化等困难问题中，具有传统优化算法无可比拟的优势。模拟退火算法的思想最早由Metorpolis等提出的。其出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性。模拟退火法是一种通用的优化算法，其物理退火过程由以下三部分组成：
1）加温过程：其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将熔为液体，从而消除系统原先存在的非均匀状态。
2）等温过程：对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡状态。
3）冷却过程：使粒子热运动减弱，系统能量下降，得到晶体结构。其中，加温过程对应算法的设定初温，等温过程对应算法的Metropolis抽样过程，冷却过程对应控制参数的下降。这里能量的变化就是目标函数，我们要得到的最优解就是能量最低态。其中Metropolis准则是SA算法收敛于全局最优解的关键所在，Metropoli、准则以一定的概率接受恶化解，这样就使算法跳离局部最优的陷阱。


思路：
1


算法分析：
模拟退火算法用Metropolis算法产生组合优化问题解的序列。并由Metropolis准则对应的转移概率P：
1
确定是否接受从当前解$i$ 到新解$j$ 的转移。式中$t ∈R+$ 表示控制参数。开始让$t$ 取较大的值，在进行足够多的转移后，缓慢减小$t$ 的值（初始温度乘以退火系数，如 $0.98$ 等），如此重复直至满足某个停止准则时算法终止。
模拟退火算法依据Metropolis准则接受新解，除接受优化解外，还在一个限定范围内接受恶化解。开始时$t$值较大，可能接受较差的恶化解，随着$t$值的减小，只能接受较好的恶化解；当$t$值趋于零值时，就不再接受任何恶化解。这就使得算法可以跳出局部最优陷阱。在算法执行期间，随着控制参数$t$值的减小，算法返回某个整体最优解得概率单调增大，返回某个非最优解的概率单调减小。

神经网络算法

自组织映射（Self-Organizing Maps，SOM）

基本原理：
自组织映射（Self-Organizing Maps，SOM）由芬兰学者 Teuvo Kohonen 提出，是一种无监督的聚类方法。
受人类大脑神经元的自组织和侧抑制现象启发，不同外部刺激引起大脑皮层各个区域的反应是不同的；类似地，自组织映射在接受外界输入的模式时，会分为不同的应对区域，各区域对输入模式有着不同的响应。这种分区对应是在训练中逐渐学到的，是一个自组织的过程。
另一方面，生物神经元之间存在侧抑制现象，临近的神经元相互激励，较远的神经元相互抑制。响应最强的神经元即获胜神经元，以它为中心，会形成一个区域，距离中心越远激励越弱。


1


在 SOM 中，促使周围神经元兴奋的范围叫做“优胜邻域”。在优胜邻域内，作用强弱与距离的关系可以简化成高斯函数。
SOM 有输入和输出两层神经网络，输出层通常是一个二维的神经元网格（本文是一维的环形结构）。从输入层输入的数据代表着真实世界的模式（Pattern），SOM 的训练目标是把输入数据的模式映射到输出层中。在训练中，输出层神经元的权值向量会被更新，输出层神经元在训练中逐渐学到输入数据背后的模式。
对旅行商问题而言，
二维城市坐标是网络的输入向量，
城市空间位置关系是 SOM 要学习的模式，
而网络的输出是一个环形的神经元结构。


1
SOM 自组织映射的结构：
输入层、全连接（权值矩阵）、输出层（特征映射）

神经元权值向量的更新：
在每次训练中，首先要根据各神经元权值向量与输入向量的相似度，选出获胜神经元。然后更新获胜神经元周围神经元的权值向量，使其逼近获胜神经元的权值向量和输入层的输入向量。输出层中神经元权值向量的更新方式是：


1
$n(t+1)$ 表示更新后的神经元
$n(t)$ 表示更新前的神经元
$h$ 表示获胜神经元对近邻神经元作用强弱的邻域分布
$Δ$ 表示该神经元与其附近获胜神经元之间的距离。


获胜神经元的优胜邻域内的神经元称为近邻神经元（neighborhood）。
获胜神经元对其近邻神经元的作用在距离 $Δ$ 上接近正态分布，这与实际相符，在本例中用高斯函数表示。
优胜邻域就像一个气泡，在它半径范围内的神经元会得到更新，而优胜邻域之外的神经元不会被更新。


1


输出层神经元是二维网格排列时，优胜邻域像一个气泡，邻域内的神经元权值向量获得更新。

利用自组织映射解决旅行商问题:
上式明确了神经元从 $t$ 时刻到 $t+1$ 时刻是如何更新的，关键是确认谁是获胜神经元。我们用欧几里得距离测量相似度，即神经元权值向量与输入向量之间的欧氏距离。欧氏距离最小的神经元就是权值向量最接近输入向量的那个，我们就将其设为获胜神经元。当我们输入的数据是城市坐标位置时，获胜神经元所表示的位置与地图中城市的位置最相近。


每次训练，获胜神经元及其近邻神经元的权值向量都会更新，经过多次反复的竞争与更新，神经网络最终学到输入数据的模式（城市的空间关系），并以神经元权值向量的形式保存下来。体现在地图中，就是神经元的位置不断靠近城市，最终与之重合。


1


在训练过程中，神经元（圆形）不断向城市（方形）靠近，最后得到符合要求的路径。

参数衰减与算法收敛:
利用自组织映射解决旅行商问题，最重要的就是调整优胜邻域。本文把 SOM 输出层的神经元排成一个环状阵列，每个节点只和它前后两个神经元产生竞争。稍作修改，SOM 的输出就会在邻域函数作用下，像有弹性的圆环一样，在不断靠近城市的同时，尽量控制总长，最终得到一个解。


本文 SOM 技术的主要思想是不断调整优胜邻域，但算法在时间上不会自动收敛。为了保证算法的收敛性，我们要设置一个学习率 α，用它来控制算法的探索。为了让算法的探索足够充分，我们还要用让邻域值和学习率都随时间衰减。学习率不断衰减会使得计算过程过程收敛。邻域值不断衰减会使得距离城市较远的神经元也能参与探索。考虑使算法收敛，SOM 输出层神经元的权值更新可表示为：


1


$α$ 是学习率
$g$ 是获胜神经元的优胜邻域，它是以获胜神经元为中心，以更新前的优胜邻域 $h$ 为标准差的高斯函数


学习率和优胜邻域随时间衰减可以表示为：
1


$γ(α)$ 是学习率的衰减率
$γ(h)$ 是邻域值的衰减率


我们需要为 SOM 设置初始学习率及其衰减率、初始优胜邻域及其衰减率，然后按上述步骤运行，学习率和优胜邻域值都随着迭代次数增加而不断减小，最终收敛。
最后，要让 SOM 生成路径，只需要将一个城市和它的获胜神经元相连，从任意一点开始，按获胜神经元的顺序对城市排序。如果几个城市映射到同一个神经元，那是因为 SOM 没有考虑到穿越这些城市的顺序。更进一步，原因可能是总距离和穿越顺序的相关性不够，也可能是因为精确度不够。此时，对于这些城市，就需要考虑各种可能的排序。

1
自组织映射训练过程可视化：多次迭代训练，最终收敛为一条走完乌拉圭734个城市的路径。

演示demo

参考文献及参考链接：
[1]. DAI San, CHEN Gongyang, ZHOU Yuncai. Algorithms Comparison of the Traveling Salesman Problem. 2013
[2]. MA Liang.Algorithmic Review on the Traveling Salesman Problem [J]. Mathematics in Practice and Theory，2000，30
(2):156-165.
TSP_旅行商问题 - 遗传算法（四）
蚁群算法解决TSP问题
TSP_旅行商问题 - 模拟退火算法（三）
如何用自组织映射 (SOM) 解决旅行商问题 (TSP)