基于Hopfield网络的TSP路径优化研究

王 颖

（哈尔滨远东理工学院，黑龙江 哈尔滨 150025）

组合优化问题中的一个典型就是旅行商问题（TSP），其可能的城市数目N和路径数目呈指数型增长，由于计算量太大，常规方法无法求解出最优解，所以针对旅行商问题（TSP）寻找有效的近似求解算法具有非常重要的理论意义.另外，现今可以将很多实际应用问题进行简化处理，处理后的结果均可用旅行商问题（TSP）进行表示，因而对旅行商问题（TSP）求解方法的研究具有重要的应用价值.

1 求解TSP问题的Hop field网络设计

TSP问题是在一个城市集合｛Ac，Bc，Cc，……｝中找出一个最短路径，该路径必须经过并只经过每个城市一次，最终回到起点的路径的方法.Hopfield采取了换位矩阵的表示方法，从而将TSP问题映射为一个神经网络的动态过程，用N×N矩阵表示旅行商访问N个城市.[1]例如，有四个城市｛Ac，Bc，Cc，Dc｝，旅行商访问的路线是 Bc→Cc→Ac→Dc→Bc，则Hopfield网络输出所代表有效解用下面的二维矩阵表表1进行表示.

表1 四个城市的访问路线

表1中是一个4×4二维矩阵，矩阵中每行每列只有一个元素为1，其余均为0，否则路径是无效的.神经元（x,i）的输出用Vxi表示，神经元（x,i）的输入用Uxi表示.如果城市x在i位置上被访问，则Vxi=1，否则Vxi=0.

针对TSP问题，Hopfield宣言了如下形式的能量函数：

公式1.1中A，B，C，D是权值，dxy表示城市x到城市y之间的距离.[1]

公式1.1中，E的前三项用于约束问题，最后一项用于优化目标.E的第一项用于保证矩阵V的每一行1的个数>=0且<=1时E最小（即每个城市只去一次），E的第二项保证矩阵V的每一列1的个数>=0且<=1时E最小（即每次只访问一个城市），E的第三项保证矩阵V中的1的个数恰好为N时E最小.

在神经网络中引入Hopfield能量函数的概念，从而产生新的方法进行求解优化问题.但新方法在求解上仍然存在一些不足，如局部极小、不稳定等问题.为此，将TSP的能量函数定义为：

取式1.2，Hopfield网络的动态方程为：

2 采用Hopfield网络求解TSP问题的算法

采用Hopfield网络求解TSP问题的算法描述如下:

(1)设置初始值，t=0，A=1.5，D=1.0，μ=50；

(2)计算N个城市之间的距离dxy(x,y=1,2,…,N)；

(3)在0附近设置神经网络输入Uxi(t)的初始化数值；

(5)采用一阶欧拉法计算Uxi(t+1)

(6)为了保证收敛于正确解，即矩阵V每行每列只有一个元素为1，其余为0，应用Sigmoid函数计算Vxi(t)

Sigmoid函数的形状由μ>0值的大小决定；

(7)应用公式（1.2），计算能量函数 E；

(8)进行路径合法性的检查，根据迭代次数判断是否结束，如果结束，则终止，否则返回到第（4）步；

(9)输出并显示迭代次数、最优能量函数、最优路径、路径长度的值，同时给出能量函数随时间变化的曲线图.[3]

3 仿真实例

在TSP的Hopfield网络能量函数公式（1.2）中，取A=B=1.5，D=1.0.设置公式（1.4）离散的间隔时间为 =0.01，在[-0.001,+0.001]间选择网络输入Uxi(t)初始值的随机值，在公式（1.5）的Sigmoid函数中，取较大的μ，使Sigmoid函数比较陡峭，从而稳态时Vxi(t)能够趋于1或趋于0.

仿真中，取M=1时，对8个城市的路径进行优化，城市路径坐标为：

如果初始化的寻优路径有效，即路径矩阵中每行每列只有一个元素为1，其余均为0，则给出最后的优化路径，否则停止优化，需要重新运行优化程序.如果本次寻优路径有效，经过2000次迭代，最优能量函数为Final_E=1.4468，初始路程为Initial_Length=4.1419，最终路程为Final_Length=2.8937.

仿真中取M=2时，对20个城市的路径进行优化，城市路径坐标为：

如果初始化的寻优路径有效，即路径矩阵中每行每列只有一个元素为1，其余均为0，则给出最后的优化路径，否则停止优化，需要重新运行优化程序.如果本次寻优路径有效，经过2000次迭代，最优能量函数为Final_E=1.6744，初始路程为Initial_Length=10.0523，最终路程为Final_Length=3.3487.

由于随机性对网络输入Uxi(t)进行初始化的选择，初始化的寻优路径最终可能会导致无效，即路径矩阵中每行元素1的个数超过1个或每列元素中1的个数超过1个，如果矩阵中每行每列不仅仅只是一个元素1就表明寻优失败，即刻停止优化，需要重新运行优化程序.

以8个城市为例进行路径优化实验，仿真实验100次，最终达到收敛最优解的有90次以上.仿真结果如图1和图2所示，其中图1为初始路径及优化后的路径的比较，图2为能量函数随时间的变化过程.由仿真结果可见，能量函数E单调下降，E的最小点对应问题的最优解.[2]

图1 初始路径及优化后的路径（8个城市）

图2 能量函数随迭代次数的变化（8个城市）

以20个城市为例进行路径优化实验，仿真实验100次，最终达到收敛最优解的有90次以上.仿真结果如图3和图4所示，其中图3为初始路径及优化后的路径的比较，图4为能量函数随时间的变化过程.由仿真结果可见，能量函数E单调下降，E的最小点对应问题的最优解.[2]

图3 初始路径及优化后的路径（20个城市）

图4 能量函数随迭代次数的变化（20个城市）

4 小结

本文应用Hopfield网络解决了旅行商问题中的路径优化问题.对于旅行商路径优化问题提出了新的设计和算法，使路径更加优化，并通过计算机仿真得到了理想的结果.

〔1〕张弘.Hopfield神经网络在机器人路径规划中的应用[J].西安邮电学院学报，2009（5）.

〔2〕刘金琨.智能控制[M].北京：电子工业出版社，2005.

〔3〕张涛涛，吴俊林，张岩.基于Hopfield神经网络的WSN分布式拓扑[J].计算机与现代化，2010（1）.