第22卷第1期 齐 齐 哈 尔 大 学 学 报 Vol.22,No.1 2006年1月 Journal of Qiqihar University Jan.,2006
基于神经网络求解TSP 问题的研究
王艳春1 王 新2
（1.齐齐哈尔大学通信与电子工程学院，齐齐哈尔161006；2.齐齐哈尔市信息产业局，齐齐哈尔 161006）
摘 要：描述了Hopfield 神经网络和TSP 问题，研究了用连续Hopfield 神经网络求解TSP 问题的方法。
关 键 词：神经网络；TSP；能量参数；反馈网络
中图分类号：TP393.1 文献标识码：A 文章编号：1007-984X(2006)01-0065-03
TSP 问题是典型的NP（Nondeterministic Polynomid）完全问题，所有的NP 完备性问题在数学上都等价于TSP 问题，因此研究求解TSP 问题的新方法具有十分重要的意义，本文讨论了用Hopfield 神经网络求解TSP 问题的方法。
1 Hopfield 神经网络模型
Hopfield 神经网络是最典型的反馈神经网络。从系统的观点看，它是一个非线性动力学系统；从计算角度看，它比前向神经网络具有更强的计算能力。该系统可分为连续型和离散型两种。下面从神经元输入输出关系，运动方程和网络能量函数三个方面的数学描述来描述这两种模型。
1.1 离散Hopfield 神经网络的描述
离散神经网络是离散时间系统。离散模型中每个神经元的输入u i 和输出v i 满足阶跃函数
v i =step(u i ) （1）
整个网络的状态矢量 v (t )∈{1,0}n ,这样t 时刻节点i 即第i 个神经元的
状态v i (t )的下一状态可由下式确定：
v i (t +1)= ???≥其它（ 00) 1t H i （2） 其中，H i (t )=∑=?n 1j i j ij θ(t)v w 为第j 个神经元对第i 个神经元的输入连接
强度，θi 为第i 个神经元的阈值，如图1所示。
式（2）即为离散Hopfield 网络的运动方程，所对应的神经网络能
量函数为：
∑∑∑+?=≠=i i j n 1i i i j i j i v θv v w E 21 (3)
如果网络工作在串行模式，w 的对角元素非负（包括对角元素为0情况），则式（2）总是收敛于稳定状态。
1.2 连续Hopfield 神经网络描述
连续Hopfield 神经网络中第i 个神经元输出电压v i 与输入电压u i 之间的非线性关系可以表示为：
V i =f i (u i )=2
1 [1+tanh (0u λu i )] (4) 其中u o 为基准值。当u o ?0时f i 成为硬限幅函数。
收稿日期：2005--08—20 作者简介：王艳春，女，1972年生，讲师，主要从事计算机通信的研究。
?66? 齐 齐 哈 尔 大 学 学 报 2006年N 个神经元相互作用的动力学性质可以用下面的微分方程描述 ?????=++?=∑=)
(/d d 1j j i n j j j i i i i i u f v I v w R u t u c （5） 其中R i 和C i 并联，用来模拟生物神经元输出的时间常数；W ij 模拟生物神经元之间互连的突触特性。
Hopfield 连续神经网络能量函数：
∑∑∑∫∑===?=??=N j N k j i ij N i i i v N i i v v w I V dv v f R E i 11110121)(1 （6）
2 基于Hopfield 网络的TSP 问题
2.1 TSP 问题描述
组合优化问题是从可行解集中求出最优解的问题。本文讨论的TSP 问题就是典型的组合优化问题。TSP 问题总是可以描述为：有N 个城市，它们之间的距离已知，有一个旅行商从某一城市出发走遍所有城市，每个城市只能经过一次，最后回到原处，应如何选择路径使得他走过的路程最短。用数学语言可以描述为：设有限个城市集合C ={C 1，C 2，…，C n }每个城市之间的距离为d (C i ，C j )∈Z +,其中C i ,C j ∈C (1≤i ,j ≤N)求使 min{∑?=1
1N i d (c ΠC I ,c ΠC i +1)+d (c Π（N ）,c Π（1））}的城市序列{c Π（1）,c Π（2），…,c Π（N ）}。
其中Π(1)，Π(2)，…,Π(N )是1，2，…，N 的一个全排列。对于N 个城市的TSP 问题，存在的不同路径有（N -1）！/2条，当N 很大时，这个数量就是惊人的。用Hopfield 神经网络求解快而有效。
2.2 基于连续Hopfield 网络的TSP 问题
TSP 可表示为如下优化问题：
∑∑∑≠?++=x x y i i y i y i x xy v v v d l )(21min 1,1,
(7) 其中L 为路径总长度，V xi =1时，V y , i+1+ V y , i-1与V y,i-1只能有一个为“1”，另一个为“0”，表明y 城与x 城路径顺序邻接，d xy 表示x 与y 城的距离。目标函数为:
∑∑∑∑∑∑∑∑?++=≠≠x i xi i x x y i y xi x i i j yj xy N v C v v B v v A E )(222 2 +)(21,1,?+≠+∑∑∑i y i y i x x x y i y x v v v d D
（8） 其中第一项和第2项在各行（列）只有一个为1时达最小，第3项是当矩阵有n 个1时最小，第4项是总路径，式中A ，B ，C ，D 是不同的常数。相应于式（8）的神经网络动态方程为 : ???
????+==+??????=????=∑∑∑∑∑?+≠≠]tanh 1[21)()()(d d 01,1,)u u (u f v v v d D N v C v B v A u v E u t u i x i x i x y i y i y xy x i xi x y i y i j xj xi i x xi i x ττ （9） 选择适当的参数A ，B ，C ，D 和u o ，按（9）式迭代到直到收敛。TSP 中V xi 值要求为0或1，但用连续型Hopfield 网络时V xi 在[0,1]变化，只要收敛到状态符合要求即可。
3 TSP 问题映射为一个Hopfield 神经网络动力系统的步骤
1）将TSP 问题的每一条可能路径用一个置换矩阵表示，并给出相应的距离表示式。
2）将TSP 问题的置换矩阵集合与由N 个神经元构成的神经元阵列相应，每条路径对应的置换矩阵的各元素与相应的神经元稳态输出相应。
3）找出一个反映TSP 的约束优化问题的能量函数E 。
4）求出使E 取最小值的神经网络连接权值矩阵和偏置参数。
第1期 基于神经网络求解TSP问题的研究 ?67?
由此设计的神经网络即可用于相应的TSP问题求解，网络的稳态输出就是TSP问题的局域优化解，同时也是相应的能量函数E的最小值。网络的搜索时间即是网络达到稳定态的时间。
4 结束语
通过仿真实验已证明，用Hopfield神经网络求解TSP问题比已有的启发式算法更优，表现为公式规范清晰，计算快而有效。当然，由于用连续Hopfield神经网络求解TSP时，能量函数存在大量的局部极小值，迭代过程并不能保证收敛到全局极小，这还有待我们对神经网络算法进行进一步的研究优化。
参 考 文 献
[1] 王朝，宣国荣.人工神经网络求解TSP问题的新方法.计算机应用与软件，2001;(4)
[2] 程 明, 刘 琴.神经网络TSP问题仿真分析.郑州大学学报，2004;(1)
[3] 阎平凡.人工神经网络与模拟进化计算.北京：清化大学出版社，2000；（11）
Research of TSP problem based on Hopfield Neural Networks
WANG Yan-chun1WANG Xin2
(1.College of Communication and Electronic Engineering,Qiqihar University,Qiqihar 161006；
2. Qiqihar Information industry bureau,Qiqihar 161006)
Abstract：This paper discusses Hopfield Neural Networks and TSP probem ,and then researches method of the TSP problem based on Hopfield Neural Networks.
Key works：Hopfield neural networks；energy function; TSP; feedback neural Network