如何用自组织映射 解决旅行商问题

前言

自组织映射（SOM）是一种无监督学习的神经网络，用来解决旅行商问题（TSP）时，二维城市坐标是神经网络的输入，城市空间位置关系是神经网络要学习的模式，一个环形的神经元结构是神经网络的输出。

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

旅行商问题(Travelling Salesman Problem，TSP)是计算机科学的经典难题，即在地图上给定一系列城市和各城市之间的距离，求解遍历这些城市的最短路径。虽然旅行商问题很容易描述，但它是一个 NP-完全问题。这意味着，城市越多，解题困难就越大，而且这类问题没有通用解法。因此，目前认为任何次优解都是足够好的，多数情况下现在还没法验证返回的解是否是最优解。

为了解这个问题，我们可以尝试改善自组织映射（Self-Organizing Maps，SOM）技术。下面我们首先了解一下自组织映射，再来看它如何应用于旅行商问题的解决。

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

1.认识自组织映射

1.1自组织映射基本原理

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

在 SOM 中，促使周围神经元兴奋的范围叫做“优胜邻域”。在优胜邻域内，作用强弱与距离的关系可以简化成高斯函数

SOM 有输入和输出两层神经网络，输出层通常是一个二维的神经元网格（本文是一维的环形结构）。从输入层输入的数据代表着真实世界的模式（Pattern），SOM 的训练目标是把输入数据的模式映射到输出层中。在训练中，输出层神经元的权值向量会被更新，输出层神经元在训练中逐渐学到输入数据背后的模式。对旅行商问题而言，二维城市坐标是网络的输入向量，城市空间位置关系是 SOM 要学习的模式，而网络的输出是一个环形的神经元结构。

1.2神经元权值向量的更新

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

n(t+1)表示更新后的神经元

n(t)表示更新前的神经元

h表示获胜神经元对近邻神经元作用强弱的邻域分布

Δ表示该神经元与其附近获胜神经元之间的距离。

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

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

1.3利用自组织映射解决旅行商问题

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

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

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

2.参数衰减与算法收敛

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

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

α是学习率

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

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

γ(α)是学习率的衰减率

γ(h)是邻域值的衰减率

我们需要为 SOM 设置初始学习率及其衰减率、初始优胜邻域及其衰减率，然后按上述步骤运行，学习率和优胜邻域值都随着迭代次数增加而不断减小，最终收敛。

上面的 SOM 方法，无论是表达式、收敛方法还是搜索方式，都与 Q-Learning 的相似。Teuvo Kohonen 本人开发的学习矢量量化技术（Learning Vector Quantization）在功能上也与之类似。学习矢量量化是一种有监督学习的算法，用于分类问题。

最后，要让 SOM 生成路径，只需要将一个城市和它的获胜神经元相连，从任意一点开始，按获胜神经元的顺序对城市排序。如果几个城市映射到同一个神经元，那是因为 SOM 没有考虑到穿越这些城市的顺序。更进一步，原因可能是总距离和穿越顺序的相关性不够，也可能是因为精确度不够。此时，对于这些城市，就需要考虑各种可能的排序。

3.检验 SOM 的效果

3.1数据格式与来源

本项目采用了滑铁卢大学在“全国旅行商问题（ National Traveling Salesman Problem instances）”项目中的案例数据，包括城市位置和目前已知的最优路径，可以用来评价用 SOM 生成路径的效果。城市数据是通用的 TSPLIB 格式，可以在文末链接中找到。

3.2评价指标和初始参数

我们使用下列指标作为检验：

寻找路线所花费的时间

解决方案的效果，以百分比表示：如果机器得到路线的长度是给定最优路线的1.1倍，我们就认为 SOM 方案的效果与最优方案相差10%

评估过程中所用的参数根据 Brocki(2010)的工作做了调整：

SOM 网络规模（神经元数量）是城市总数的8倍

初始学习率α为0.8，衰减率为0.99997

初始优胜邻域值h为城市总数，衰减率为0.9997

在“全国旅行商问题”项目中，已知下面四个国家的城市数量和最优路线长度：

卡塔尔，194座城市，已知最优路线长9352

乌拉圭，734座城市，已知最优路线长79114

芬兰，10639座城市，已知最优路线长520527

意大利，16862座城市，已知最优路线长557315

3.3实验结果

当某些变量衰减到有效阈值以下，模型会停止执行。尽管可以为每个实例找到更细粒度的参数，我们还是使用了统一的方法对这些实例进行测试。下面的评估结果是每个实例5次试验后的平均值：

用 SOM 走遍乌拉圭：分别迭代100次，6000次，17000次的训练结果

这个方法实现的结果不错，我们能够用400秒训练时间获得一个接近最优的解，总体上可以接受。还有像类似于乌拉圭这样，能够在25秒内找到一条穿越734个城市的路线，总长度仅仅比给定的最优路线多7.5%。

3.4评论

用 SOM 走遍意大利：分别迭代100次，8000次，20000次的训练结果

只经过了部分测试，我们就能发现，自组织映射技术的这一应用很有趣，在一些实例中效果令人印象深刻。本文的亮点是把 SOM-TSP 解决方案使用 Python 来实现。

我们将在后续文章中介绍本文 SOM 方法的 Python 实现，你也可以在 github 仓库中先睹为快。

参考资料：

1.本项目 github 仓库地址：https://github.com/DiegoVicen/som-tsp

2.Teuvo Kohonen 的自组织映射论文：https://pdfs.semanticscholar.org/45e6/c7492d01228a33c295557a0b491ec2b4e20e.pdf

3.加拿大滑铁卢大学的 TSP 实例数据库：http://www.math.uwaterloo.ca/tsp/world/countries.html

本文由集智小仙女编译整理，内容有增补

原文地址：https://diego.codes/post/som-tsp/

关注集智AI学园公众号

获取更多更有趣的AI教程吧！

搜索微信公众号：swarmAI

学园网站：campus.swarma.org

商务合作｜zhangqian@swarma.org

投稿转载｜wangjiannan@swarma.org