论文信息
- 标题： Unsupervised Learning for Solving the Travelling Salesman Problem[1]
- 作者： Yimeng Min, Yiwei Bai, Carla P. Gomes
- 会议： NeurIPS 2023
- 在线资源： https://proceedings.neurips.cc/paper_files/paper/2023/hash/93b8618a9061f8a55825c13ecf28392b-Abstract-Conference.html
- 代码： https://github.com/yimengmin/UTSP
UTSP 算法
作者认为理想的 heatmap $\mathcal{H}\in[0,1]^{n\times n}$ 应该表示 TSP 的最优解，即一条长度最短的汉密尔顿环路，也就是：
- $\mathcal{H}$ 作为邻接矩阵表示的图内有且仅有一条汉密尔顿环路；
- $\mathcal{H}$ 表示的环路长度最短，即$$\min_\mathcal{H}\sum^n_{i=1}\sum^n_{j=1} \mathcal{H} _{ij}\cdot d _{ij}$$
为了让网络输出的 $\mathcal{H}$ 满足第一个条件，作者设计了 soft indicator matrix $\mathbb{T}\in[0,1]^{n\times n}$，$\mathbb{T}=[\mathbf p_1|\mathbf p_2|\cdots|\mathbf p_n]$ 是$n$个列向量组成的矩阵，满足各列和为$1$（$\sum_{j=1}^n p_{ij} = 1$），这个条件可以使用 Softmax 函数或者归一化满足，论文里使用了前者。
然后作者提出了 $\mathbb{T}\rightarrow\mathcal{H}$ transformation，以将 soft indicator $\mathbb{T}$ 转化为可以采样的 heatmap $\mathcal{H}$：$$\mathcal{H} = \sum_{i=1}^n \mathbf p_i\cdot \mathbf p_{i+1}^T + \mathbf p_n\cdot \mathbf p_1^T$$ 同时作者也证明了这样形成的 heatmap 中至少有一条汉密尔顿环路，这样就满足了第一个条件的一半（有一条）。
至于剩下的一半（不超过一条），作者使用设计的 loss 函数鼓励网络减少环路数量： $$\mathcal{L}=\lambda _1 \sum^n _{i=1}(\sum^n _{j=1}\mathbb{T} _{ij}-1)^2 + \lambda_2 \sum^n _{i=1}\mathcal{H} _{ii} + \sum^n _{i=1}\sum^n _{j=1} \mathcal{H} _{ij}\cdot d _{ij}$$ 其中第一项鼓励 $\mathbb T$ 每行的和接近 $1$；第二项惩罚 $\mathcal{H}$ 中的自环；第三项对应上面的第二个条件，即让图里所有边的加权和尽可能小。最理想的情况下前两项都是 $0$，$\mathcal L$等于TSP最优解的路径长度。UTSP 通过设置这样的 loss 函数，让神经网络输出的结果靠近理想的 heatmap。
此外，文章使用了 Scattering Attention GNN (SAG) 作为神经网络，在搜索前用 top-k 缩小搜索空间，并使用 Heat Map Guided Best-first Local Search 作为局部搜索方法。
优势与局限性
根据文章，UTSP 的优势是：
- 相比于有监督学习，UTSP 不需要有标注的数据，相比于强化学习，UTSP 的收敛速度更快（需要的样本数量更少）；
- UTSP 直接从 heatmap 计算 loss，省去了强化学习依赖采样获得 reward 的过程；
- 通过结构设计保证输出的heatmap含有汉密尔顿环路；
- 神经网络很轻量化（TSP100 仅需两层 45k 个参数）；
- 可以有效地减小搜索空间。
我认为 UTSP 的局限性是：
- 根据提供的实验数据，UTSP 即使有轻量化的网络，它生成 heatmap 需要的时间依然比 Att-GCRN[2] 要长（为什么呢？）；
- Soft indicator 是针对 TSP 的巧妙设计，只适用于解为汉密尔顿环的问题，并且 UTSP 需要针对问题精心设计 loss 函数，因此将 UTSP 迁移到别的组合优化问题时，相比于一些有监督学习和强化学习方法（分别可以通过有标签的数据和 reward 学习问题特征）需要更多工作。
几个问题：
- 在将边权重输入网络时，文章进行了预处理：$w_{ij}=e^{-d_{ij}/\tau}$，这样做除了将输入映射到 $(0,1]$ 之外，相比于直接输入 $w_{ij}=d_{ij}$ 还有什么作用嘛；
- 如果不采用 Soft indicator，实验结果会有多大变化。