《基于 Hopfield 神经网络模型求解 TSP 问题的算法.doc》由会员分享，可在线阅读，更多相关《基于 Hopfield 神经网络模型求解 TSP 问题的算法.doc（3页珍藏版）》请在三一办公上搜索。
1、精品论文推荐基于 Hopfield 神经网络模型求解 TSP 问题的算法于慧，徐慧 辽宁工程技术大学理学院，辽宁阜新（123000） E-mail: yuhui7843293*摘要：本文给出了一种基于 Hopfield 神经网络模型求解 TSP 问题的算法。Hopfield 网络 是一种网状网络，网络中的每个神经元都可以和其他神经元双向连接。这种连接方式使得网络中每个神经元的输出都能反馈到同一层次的其他神经元，因此，它是一种反馈网络。根据 网络节点的状态，Hopfield 网络可分为离散的和连续的两种类型。离散的网络，其节点状态仅取 0,1(或+1，-1)两个值；而连续的网络，其节点状态可以取
2、区间0,1上任何值。Hopfield神经网络在联想记忆、组合优化和机器人控制等方面有重要的应用。其中 Hopfield 网络用于 优化计算是最常见的。Hopfield 网络的能量函数是一个多维神经元状态的标量函数，在网络收敛的稳定点上的能量函数最小。因此，设计网络权值 W 和输入，将优化问题中的目标函数、约束条件与能量函数联系起来，那么能量函数的极小点也是目标函数满足约束条件的极 小点,所以 Hopfield 网络也可用于求解优化计算问题关键词：Hopfield 神经网络；神经元；能量函数1.TSP 问题的描述TSP 问题是一类较难解决的组合优化问题，可以这样描述这个问题：给定 n 个城市A,
3、 B, C,. ,若两城市间距离分别为 DAB , DAC ,., DBC ,则求出从任一城市出发，访问每城市一- 3 -次的最 短访 问路 线。 如果 A, B, C, D, FD = DAB + DBC + DCD + DDF + DFA2.TSP 问题的实例分析为被访 问的 城市 ，则总 的路 径长 度为 为了便于说明问题，可将 N 个神经元的输出排成一个方阵。例如 5 城市 (A, B, C, D, E )的TSP 问题神经网络的一种状态，列入下表 1：表 1 5 个神经元的输出情况12345A01000B00010C10000D00001E00100上面的描述称之为换位矩阵，它表示了
4、这样一条路径：C A E B D路径总长度为D = D CA+ D AE+ D EB+ D BD+ D DC 。显然，在一条可表示解的有效线路上，任何城市所占据的位置不能多于1个，而在任何 一个位置上也只能容纳一个城市。也就是说，在描述一条有效线路的输出状态中，换位矩阵 每一行每一列只能有一个为“1”，其余都为“0”。若含有 n 个城市需用 N 个神经元的输出排成一个方阵。即所需神经元数 N 为N = n 2对于 n 个城市的 TSP 问题，各种可能方案的数目为(n 1)!2。这表明 TSP 问题的计算时间随城市数目 n 的增加而曾指数增长，因此，TSP 问题是 NP 完全问题1。3.构造能量
5、函数利用 Hopfield 神经网络求解优化问题，必须考虑： (1)构造系统的能量函数； (2)提供一种方法来解释输出状态是如何表示问题的解2 。为了解决 TSP 问题，必须设计这样的网络，使其计算能量的极小点对应于最佳路径。 也就是说，由计算能量找到的极小状态必须构成换位阵，并且路径最短。基于上述考虑，能量函数为ABC E = 2 VxiVxj + 2 VxiV yi + 2 Vxi n xi j iix x y xi在这里 A, B, C 均大于零。当且仅当换位阵的每一行不多于一个1时，上式的第一项为0 ；当且仅当矩阵的每一列不多于一个1时，第二项为 0 ；当且仅当矩阵中1的个数为 n 时
6、， 第三项为 0 3 。因此这三项保证了所得路径的有效性。为了保证路径最短，必须加入有关路 径长度的信息，即必须使下式为极小:2ij1 D (Vxyxyd xyVxiy ,i +1+ Vy ,i 1 )ijxyx y x iij若 A, B, C, D 充分大，则所有的极小点都表示一个有效路径，此时 E 值就是路径长度， 并且对应 E 的最小点4。E 的连接矩阵可设计为Txi , yi= A xy(1 ) B(1 ) C Dd (j ,i +1+ j ,i 1 )ij其中 ， A xy(1 ) 为行约 束； B(1 ) 为列约 束； C 为全局 约束； Dd xy (j ,i +1+ j ,i
7、 1)为路径长度约束。1,i = jij = 0,i j外加激励 I xi = cn 。 E 的前 3 项适应于一般的 TSP 问题，而第 4 项与具体的某一特征TSP 问题有关。1将 ij = 0,i =,i jj 和 I xi= cn 代入c i ( ) = V(t ) i ( ) + Idu t idtnu tij jRij =1Vi (t ) = gui (t )i,i = 1,2,., n并取神经元的作用函数选为双曲正切函数即可求解 TSP 问题的网络方程5。dui= u xi AVxj BV yi C Vxy n D(Vd xyy ,i +1+ Vy ,i 1 )dtj iy x
8、xyy1 u xi Vxi = g (u xi ) =1 + tanh2u4.结语 0 本文选择了 TSP 问题表达方式，进而使神经元的输出与问题的解相对应。设计了能量函数，使其最小值点对应于问题的最佳解。基于 Hopfield 神经网络模型求解 TSP 问题的算 法可以解决现实生活中许多评价问题，具有很高的实效性。参考文献1 是秀丽. 浅谈应用文中的模糊语言J. 应用写作, 20032 郭嗣琮，陈刚.信息科学中的软计算方法M. 沈阳: 东北大学出版社, 2001 3 陈国权. 模糊集合、语言变量及模糊逻辑M. 北京: 科学出版社, 19824 陈世权. 模糊决策分析D.贵阳: 贵州科学技术出
9、版社, 19905 陈永义. ，综合评判的数学模型D.模糊数学, 1983Arithmetic of Using Hopfield Neural Network to Solve the TSP QuestionYuhui, XuhuiScience of College, Liaoning Technical University, Liaoning, Fuxin (123000)AbstractThis article gave one kind to solve the TSP question based on the Hopfield neural network model the
10、 algorithm. Its a mesh network. In this network, each of the network elements andother elements can be two-way connections. This approach allo ws the network to connect each neuron output can be fed back to the same level of other neurons. As a result, its a feedback network. According to the networ
11、k node status, Hopfield network can be divided into discrete and continuous two types. In discrete network, the node status only take two values:0 or 1 ( or+1,-1 ); in continuous network, the node status can take on any value range fro m 0,1. Hopfield neural network in the associative memory, the co
12、mbination of robots and optimizethe control of important applications. Hopfield network optimization for which the calculation is the most common. Hopfield network is a multi-dimensional energy function of neurons of the state of scalar function in the stability of the network convergence point of m
13、inimum energy function. As a result, network design and weight W input, optimize the problem in theobjective function and constraints linked to the energy function, then the energy function of avery small point is the objective function to meet the constraints of a very small point, theHopfield network can also be used Optimization to solve the problemKeyword: Hopfield neural network; neurons; energy function
