6.2 TSP问题的CHNN求解

本书的做法是将TSP的合法解映射为一个置换矩阵，并给出相应的能量函数。同时，将满足置换矩阵要求的能量函数最小值与TSP问题的最优解相对应。

6.2.1 求解方法一

使用一个n×n神经网络，用神经元的状态来表示某一城市在某一条有效路径中的位置。例如，神经元x _i 的状态用v _xi 表示：

其中，x∈{l,2,…,n}表示第x个城市C _x ，而i∈{l,2,…,n}表示城市C _x 在路径中的第i个位置。

由此可见，n×n矩阵V可以表示n个城市TSP问题的一次有效路径，即V矩阵可以唯一地确定对于所有城市的访问次序。

按照CHNN的求解思路首先构造能量函数，构造的能量函数为：

其中，

d _xy ：城市x到城市y的距离，A＞0，B＞0，C＞0，D＞0均为常数；

E ₁ (t)：行约束条件，当每行只有一个1时达到最小值0；

E ₂ (t)：列约束条件，当每列只有一个1时达到最小值0；

E ₃ (t)：总数约束条件，当矩阵V的元素和为n时达到最小值0；

E ₄ (t)：距离约束条件，若城市x出现在i位置，则与之相邻的城市y只能出现在i - 1或i+1位置，此时距离d _xy 才有效，当TSP问题达到最优解时E ₄ (t)取最小值。

显然，直接按上式计算E(t)十分复杂。为此，本节推导了一种计算E(t)的快速算法，即结论1。

结论1： TSP问题方法一中CHNN的能量函数可表示为如下形式：

其中，

suma(●)：对矩阵中所有元素求和；

||●|| _F ：矩阵的Frobenius范数；

⊙：矩阵与矩阵的点积；

d：n×n的距离矩阵，由d _xy 组成；

V：n×n的状态矩阵，由v _xi (t)组成；

V(:,[2:n,1])和V(:,[n,1:n])分别表示矩阵V的第[2→n,1]列与第[n,1→n-1]列所组成的矩阵。

显然，相比于E(t)的循环求和形式，E(t)的矩阵求和形式结构更加简单，编程理解更加方便，运行速度也更快。

根据CHNN的性质2可得到CHNN的动力学方程为：

令C _zk =1，z,k=1,…,n，则有：

从上式可以看出，CHNN的动力学方程表达式仍然十分复杂。

结论2： TSP问题方法一中CHNN的动力学方程可表示为如下矩阵形式：

其中，

U：n×n的CHNN输入节点矩阵，由u _zk (t)组成；

sum(●,1)与sum(●,2)：矩阵●按列求和与按行求和得到的向量；

其他符号的含义同结论1。

根据CHNN的性质1，随着CHNN的运行，能量函数E(t)将最终收敛于最终解。

6.2.2 求解方法二

6.2.1小节中，能量函数的第三项仅在网络输出全为0时起约束作用，否则前两项已经保证了第三项成立。若前两项做修改，那第三项完全可省去，于是，TSP的能量函数简化为：

根据CHNN的性质2，可得到CHNN的动力学方程为：

同样，以上CHNN的表达式过于复杂，为了简化运算，本节推导了结论3与结论4。

结论3： TSP问题方法二中CHNN的能量函数可表示为如下矩阵形式：

结论4： TSP问题方法二中CHNN的动力学方程可表示为如下矩阵形式：

结论3与结论4中的参数与符号的意义同结论1与结论2中的一样。

6.2.3 旅游线路周游规划的MATLAB实现方法

许多旅游胜地拥有十分丰富的旅游资源。以西安市为例，西安市及其周边地区划分的十大旅游区共有景点177个，其中仅西安市就有大小景点60多个，面对如此众多的旅游景点，作为一名有客观条件约束的游客，如果不能够合理地安排自己的行程和正确地选择合适的旅游路线，无疑会给游客自身带来不必要的浪费。因此，本节以旅游线路周游为例来说明Hopfield神经网络在TSP问题中的应用。景点的坐标如图6-1所示。

CHNN在旅游线路周游规划应用中的MATLAB源代码如下。

Step 1： 得到各景点的坐标及各点间的距离。

Step 2： 初始化优化前的路径，从仿真的结果来看，网络初始对仿真结果的影响极大，并不是每一次仿真都能够得到一个较好的结果。因此，本节提供了两种代码。一种是已经设置好的初值；一种是随机初值，读者可以观察随机初值对CHNN运行的影响。初始化的旅游线路如图6-2所示。

Step 3： 采用方法一解决TSP问题，微分方程采用一阶欧位法，能量函数随时间变化的情况如图6-3所示，可见能量函数的变化很不稳定。

Step 4： 采用方法二解决TSP问题，微分方程采用一阶欧拉法，但与本节的方法二略有不同，该CHNN的能量为：

动力学方程为：

V= ϕ (U)

该方法可参见文献《Hopfield神经网络在TSP问题中的应用》（作者：兰兆青，中北大学硕士论文），许多CHNN解决TSP问题的程序都以此为模型，实际运行效果也不错，但笔者算得的模型与此不同（见结论3，结论4），在此将该模型的源代码列出，供读者学习比较。

Step 5： 定义为方法三，采用方法二（即结论3与结论4）解决TSP问题。为了提高求解精度，微分方程采用龙格库塔法，由于龙格库塔法的代码比较长，本文不在此列出。方法二与方法三的能量函数随时间变化的情况如图6-4所示。

Step 6： 比较三种方法的优劣，并判断路径的有效性，结果如图6-5所示。