江苏龙网

  1. 主页 > 生活百科 > >

用 SOM 算法求解 TSP 问题( 二 )

SOM 算法求解


  • RSOM 输出层的神经元拓扑结构是环形的 。
  • 输出层神经元个数不是固定的，会随着训练不断增加神经元 。
RSOM 的结构如下所示：
用 SOM 算法求解 TSP 问题

文章插图
RSOM 示意图
RSOM 训练时的超参数包括：Tint (每更新 Tint 次，就在输出层插入一个新的神经元)，Tmax (最大的训练次数)，N(t) (t 时刻神经元的总个数)，Ci(t) (t 时刻神经元 i 获胜的次数) 。RSOM 训练过程如下：
  • 随机初始化 N(0) 个神经元，所有神经元的计数 Ci(0) = 0 。
  • 对于一个输入 x，使用欧氏距离找出获胜神经元 I 。
  • 更新神经元 I 及其邻居节点的特征向量 。

用 SOM 算法求解 TSP 问题

文章插图
更新获胜神经元及其邻居的特征向量
  • 获胜神经元的计数器 CI(t) 加 1，其邻居不用加 。
  • 如果更新了 Tint 次，则需要增加一个新的节点，新的节点在获胜神经元和其邻居之间添加 。获胜神经元 I 有左右两个邻居 (因为环形的)，选择距离远的邻居 f，并在 I 和 f 中间添加新神经元 r 。新神经元 r 的特征向量是 I 和 f 特征向量的均值，同时修改新神经元 r 和获胜神经元 I 的计数器：

用 SOM 算法求解 TSP 问题

文章插图
【用 SOM 算法求解 TSP 问题】新神经元 r 的特征向量和计数器值
通过上面的步骤即可训练 RSOM 网络，在求解 TSP 问题时，输入样本 x 就是城市的坐标 (一般是 2 维，包含 x，y)，每个神经元的特征向量维度也是 2 。训练时每个城市都会找出一个获胜神经元，然后把该神经元及其邻居都拉向城市的坐标 。可以理解为有个橡皮筋，每个城市把橡皮筋往自己的方向拉，最终橡皮筋上的不同点会固定到不同的城市中，如下图所示 。
用 SOM 算法求解 TSP 问题

文章插图
RSOM 求解 TSP 示意图
上图中的黑色点代表城市，白色点代表神经元，红色点代表获胜神经元 。
5.参考文献A simple learning algorithm for growing ring SOM and its Application to TSP




推荐阅读


上一篇：已婚女人梦见猪头 人头 已婚女人梦见猪头什么意思

下一篇：怀孕做梦梦见打死蛇是什么意思 孕妇梦见蛇被打死预示着什么