用 SOM 算法求解 TSP 问题 _小知识

旅行商问题 (TSP 问题) 是一个 NP-hard 问题，给定若干个城市，求旅行商从某个城市开始，遍历所有城市最终回到出发点的最短路径 (每个城市只经过一次) 。求 TSP 的最优解时间较长，本文介绍一种用 SOM 算法求 TSP 近似解的方法，SOM 是竞争神经网络，也称为自组织映射。

1.前言最近突然翻到读大学时一个小作业的代码，主要用 SOM 网络算法求 TSP 问题近似解。代码参考了论文《A simple learning algorithm for growing ring SOM and its application to TSP》，论文作者用了一种 RSOM 算法，与 SOM 不同，其初始神经元比较少，但是会在训练的过程中不断的增加新的神经元。
代码是用 matlab 编写的，地址：https://github.com/cc54294/SOM_TSP
代码的效果如下面的 gif 所示，分别是在 48、101、225、561 个城市上计算 TSP 的结果。在 48、101、225 个城市上的效果都比较好，但是在 561 个城市上的效果比较差。

文章插图
48 个城市 TSP 问题

文章插图
101 个城市 TSP 问题

文章插图
225 个城市 TSP 问题

文章插图
561 个城市 TSP 问题
2.TSP 问题TSP 问题称为旅行商问题，问题的定义：有一个旅行商需要访问 N 个城市，旅行商从一个城市出发，需要经过所有的 N 个城市且每个城市只经过一次，最后回到出发点，求最短的路径。如下图所示，从城市 A 出发，左侧为 TSP 问题的最短路径：

文章插图
TSP 问题
之前介绍过 Pointer Network，可用于求解 TSP 问题，不熟悉的童鞋可以参考一下之前的文章《指针网络 Pointer Network》。本文介绍另一种神经网络 SOM 用于求解 TSP 。
3.SOM 算法SOM 神经网络 (自组织映射 Self-Organizing Map)，是一种竞争型神经网络，通常用于无监督学习。一般的神经网络通过损失函数计算梯度进行优化，而 SOM 采用了竞争的策略。
对于每一个输入样本 x，SOM 会计算所有神经元与 x 的距离 (例如欧式距离)，选出获胜神经元 (也称为激活神经元，距离最近的)，然后优化获胜神经元附近的网络拓扑结构。常见 SOM 结构如下，包括输入层和输出层 (竞争层)：

文章插图
SOM 示意图
上面的图中，输入层的维度是 d (即每一个样本 x 维度是 d)，上面的二维网格中每一个圆点均是一个神经元，每个神经元都具有一个特征向量 w (维度也是 d) 。
神经元之间是具有拓扑结构的，常见的拓扑结构有矩形 (Rectangular) 和六边形 (Hexagonal) 的，如下：