旅行商问题[1] 是优化算法的试金石。 可以使用多种方法进行求解。比如下面是Will Campbell 利用遗传算法求解美国各州首府旅行商问题[2] 的动态过程。利用神经网络中的自组织映射网络(SOFM)，连续Hopfield网络也可以进行求解。
使用遗传算法求解旅行商问题
下面是利用自组织特征映射（SOFM）用于求解十个地点中间的旅行商问题的过程。在SOFM网络的竞争层采用首尾相连的一维拓扑结构，学习速率从0.3线性降低到0， 学习半径从2线性减小到0。200步训练过程网络对应的位置的演变过程如下图所示：
▲ 循环和增加噪声两种效果下的搜索结果
在上述搜索过程中，对于每个搜索节点增加了随机噪声和定向游动，提高了网络搜索的能力。
前面使用SOFM网络进行优化，应用的是自组织特征映射网络的“保序特性”，也就是网络的竞争层的神经元相互之间的拓扑结构与对应训练样本在数据空间中的分布上保持有相似的关系。
比如下面使用来自于三角形内均匀分布的数据点训练一维拓扑结构的SOFM，随着训练过程的收敛竞争网络中的神经元逐步扩展到数据所在的三角形。
下面显示的是二维拓扑结构的SOFM网络在来自于区间随机采样的数据训练下的收敛情况。
▲ 2D拓扑结构的SOFM的训练结果
下面是一次训练扭曲的分布结果：
▲ 发生扭曲的训练过程
上面的自组织特征映射网络是来自于对竞争算法（WTA：胜者为王）的改进。下面显示的是两个节点的竞争网络节点位置（红点）在五个训练样本（蓝点）作用下竞争的结果。
▲ 变学习速率的训练过程
简单的使用竞争算法，可以完成对于数据内部规律的学习。
比如下面是三个神经网络初始的位置。
▲ 三个神经元初始化后的情况
使用下面带有噪声的C，I，T字符进行训练。三个神经元便可以分别演化到C，I，T的平均结果。
▲ 添加噪声后的训练样本
经过100次竞争学习之后他们最终演变的形状。
▲ 竞争演变过程
在竞争的结果上，再增加一层映射，便可以去逼近函数。下面显示的是单相对偶传播网络（CPN）逼近Hermit函数的演变过程。
增加竞争神经元节点的个数，使用双向CPN可以进一步提高逼近函数的效果。
▲ 双向CPN函数逼近结果
对于神经网络，如果只是依靠竞争（无导师训练）所能够达到的精度会受到数据量和分布的影响。对于只有少数数据量的场景，只有竞争往往是无法达到很好的效果的，除非是一个天才。
适当引入导师信号可以在小样本下提高学习的效果。这就是学习矢量量化网络（LVQ）优势。下面是一个极端的例子，可以看到LVQ网络对于小样本下的学习能力是非常强的。
▲ LVQ训练过程
▲ LVQ训练中隐层节点演变过程
对于复杂的非线性映射，最有效的方式就是通过浅层网络的随机梯度下降，来获得较为可靠的训练结果。
下面是MATLAB中的Peaks二维函数。
▲ peaks函数图像
采集到一些离散的数据，对于有隐层网络进行训练。如果数据采集的足够多，分布的足够合理，可以很快获得其中的映射关系。
▲ 采集到的数据样本
下图显示了一个网络在训练过程中对应的输入输出关系演变过程。
▲ 神经网络输入输出对应函数曲面演变过程
END
作者：卓晴
原文链接：TsinghuaJoking
推荐阅读
更多IC设计技术干货请关注IC设计技术专栏。
