Traveling Salesman Problem 问题和解决办法

TSP问题其实之前就学过,但是之前介绍的是递归贪心和动规的方法,这次看论文,看到了2-opt算法和蚁群算法,做一个简单的介绍。

TSP问题简单介绍

TSP(Traveling Salesman Problem),即旅行商问题或货郎担问题。假设有一个商人,需要去$n$个城市进行售卖,要求每个城市去且仅去一次,城市与城市之间的距离为确定值,最后返回出发城市,目标是求得一条最优路线,使得商人所走的路程最短。
这一个NP-hard问题,即在确定多项式时间内无法求解的问题。从图论的角度来看,这是在一个有权无向图中,找到一个回路,使得回路的权重值最小。

递归算法

这类问题最简单而且最粗暴的方法就是递归,即求得所有可能的路线,在所有路线中比较求得最短的路线。该算法的时间复杂度为$n!$,随着城市数目的增加,会产生组合爆炸的问题。

贪心算法

贪心算法是在当前情况下做出最好的选择,不考虑以后的结果。该算法求得的是一个局部最优的结果。该算法的算法流程如下:

  1. 随机选取一个城市作为出发城市。
  2. 选择下一个未到达并和当前城市距离最近的城市。如果还有未到达的城市则重复该步骤。
  3. 输出路线。

如果想要降低代码的查询时间,在城市数量不多时,可以使用一个二进制数代替数组,来保存城市是否被访问过。判断第$i$个城市是否到达过的代码如下:

if ((x>>(i-1))&1)==1

动态规划算法

和贪心算法不同,动态规划算法可以看作是从后向前推,动态规划算法可以求得全局最优解。假设一共有四个城市,具体计算公式如下:
$$
\begin{equation} dp[0]\{123\}=min\{C_{01}+dp[1]\{2,3\},C_{02}+dp[2]\{1,3\},C_{03}+dp[3]\{1,2\}\} \end{equation}
$$
其中$C_{01}$为第0个城市和第1个城市之间的距离,$dp[0]{123}$为从第0个城市出发,经过第1、2、3个城市的距离,$dp[3]{}$为第3个城市到第0个城市的距离。
在动态规划算法中,通常使用一个邻接矩阵保存城市之间的距离,并随着不断地迭代不断更新。

两元素优化算法

两元素优化算法,2-optimization(2-opt)算法,也可称为2-exchang算法,最早尤Croes在论文A Method for Solving Traveling-Salesman Problems中提出。这是一种基于交换的启发式算法,具有一定的随机性。该算法的算法流程如下:

  1. 选取一个可行解。
  2. 选择参数i和k.
  3. 保留路径中第i项之前不变,第k项之后不变,将第i项至第k项路径翻转,得到翻转后的路径。
  4. 计算翻转后的路线的距离,并和原路线距离比较,较小则保留翻转后的路线。并重复步骤2-3。
  5. 达到最大迭代次数时终止。

其中$i$和$k$可用循环随机生成,满足如下条件则结束循环:

if (k-i)>1
    break

通常在小规模的数据上,该算法的运行结果比蚁群算法效率高。

蚁群算法

蚁群算法,Ant Colony Optimization(ACO)算法的原型就是蚁群的工作原理,具体如下:

  1. 蚂蚁会在经过的路径留下信息素。
  2. 蚂蚁会倾向于选择信息素更高的路径,但是存在一定的错误率。
  3. 信息素会以一定的速率消散。

假设从A到B有两条路径一长一短,长路耗费时间长,短路耗费时间短。经过相同的时间,短路上的信息素会比长路浓,从而引得更多的蚂蚁选择这条路,这是一个自催化过程。这也意味着蚂蚁通常会聚集在较短的路径上。该算法的算法流程如下:

  1. 初始化参数。对相关的参数进行初始化,如蚁群的规模、信息素重要程度因子、启发因子重要程度因子、信息素挥发因子、信息素释放总量、最大迭代次数和迭代初始次数(1)。
  2. 构建解空间。将各个蚂蚁随机地置于不同的目标点,对每个蚂蚁计算其下一个待访问的目标点,直到所有蚂蚁访问完所有的目标点。
  3. 更新信息素。计算各个蚂蚁经过的路径长度,记录当前迭代次数中的最优解(最短路径)。同时对各个目标点连接路径上的信息素进行更新。
  4. 判断是否终止。若没有终止,清空蚂蚁经过路径的记录表,并返回第二步;否则终止计算,输出最优解。

其中选取下一个目标点的概率计算如下:
$$P_{ij}^k(t)=\begin{equation}
\left \{
\begin{aligned}
\frac{\tau_{ij}^\alpha,\eta_{ij}^\beta}{\sum_{t\in{N_k}},\tau_{it}^\alpha,\eta_{it}^\beta} && if\quad j\in{N_k} \\
0 && otherwise
\end{aligned}
\right.
\end{equation}$$

其中$i$为当前节点序号,$j$为可能选择的下一个节点序号, $\alpha$ 为信息素重要程度因子,$\eta_{ij}=\frac{1}{d_{ij}}$为启发因子,$d_{ij}$为$i$节点和$j$节点之间的距离,$\beta$  为启发因子的重要程度因子,$N_k$是第$k$只蚂蚁待访问的节点集合。
信息素更新公式如下:
$$\Delta\tau_{ij}^k=\begin{equation}
\left \{
\begin{aligned}
\frac{Q}{C^k} && 走了这条路 \\
0 && 没走这条路
\end{aligned}
\right.
\end{equation}$$

$$
\begin{equation} \tau_{ij}=(1-\rho)\tau_{ij}+\sum_{k=1}^m\Delta\tau_{ij}^k \end{equation}
$$

其中$Q$为信息素释放总量,为一常值,通常设置为1,$C^k$为第$k$只蚂蚁路径的总长度,$m$为蚁群的数量。

精英蚂蚁

在原来的基础上,选择走最短路径的蚂蚁为精英蚂蚁,重复更新它的信息素,具体如下:
$$
\begin{equation} \tau_{ij}=(1-\rho)\tau_{ij}+\sum_{k=1}^m\Delta\tau_{ij}^k+e\Delta\tau_{ij}^{best} \end{equation}
$$

其中$e$为精英蚂蚁信息素更新的系数,通常在0~1之间。