神经网络算法.docx

神经网络解决TSP问题

题目：基于HopHeld网络算法的TSP问题的分析与实现

学号：

名：

一、预备知识

1、 TSP问题

旅行商问题，简称TSP,即给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为：给定图G=（V，A），其中V为顶点集，A为各顶点相互连接组成的边集，设D=（dij）是由顶点i和顶点j之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短距离。

旅行商问题可分为如下两类：

（1） 对称旅行商问题（d^dji，n〔，j=1，2,3,…，n）;

（2） 非对称旅行商问题（d|j气，甲j=1，2，3，…，n）。

非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。

若对于城市V={v，v，v，…，v}的一个访问顺序为T={t，t，t，…，t，…，

1 2 3 1 2 3 ?

t}，其中t.EV（i=1，2,3,…，n），且记t+1=t，则旅行商问题的数学模型为：

n i n1

ri

minL=。?/..。

仕|

TSP是一个典型的组合优化问题，并且是一个NP完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优化算法的间接比较标准。因此，快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。

2、 Hopfield网络

Hopfield网络是一种互连型网络的一种，它引入类似于Lyapunov函数的能量函数概念，把神经网络的拓扑结构（用连接权矩阵表示）与所求问题（用目标函数描述）相对应，并将其转换为神经网动力学系统的演化问题。其演变过程是一个非线性动力学系统，可以用一组非线性差分议程描述（离散型）或微分方程（连续型）来描述。系统的稳定性可用所谓的“能量函数”进行分析。在满足条件的情况下，某种

“能量函数”的能量在网络运行过程中不断地减少，最后趋于稳定的平衡状态。

因为人工神经网络的变换函数是一个有界函数，故系统的状态不会发生发散现象。目前，人工神经网络经常利用渐进稳定点来解决某些问题。如果把系统的稳定点视为一个记忆的话，那么从初态朝这个稳定点的演变过程就是一个寻找记忆的过程。如果把系统的稳定点视为一个能量函数的极小点，而把能量函数视为一个优化问题的目标函数，那么从初态朝这个稳定点的演变过程就是一个求解该优化问题的过程。因此，Hop^eld神经网络的演变过程是一个计算联想记忆或求解优化问题的过程。实际上，它的解决并不需要真的去计算，而是通过构成反馈神经网络，适当地设计其连接权和输入就可以达到这个目的。

二、HopField神经网络分析

1、离散型HopField神经网络

Hopfield最早提出的网络是二值神经网络，神经元的输出只取1和0两个值，也称为离散Hopfield网络。在离散Hopfield网络中，采用的神经元是二值神经元，输出的离散值1和0分别表示神经元处于激活和抑制状态。

离散Hopfield神经网络是离散时间系统，它可以用一个加权无向图表示，图的每一边都有一个权值，图的每个节点都有一个阈值，网络的阶数相应于图中的节点数。

Hopfield网络的基本结构如图1所示，这种网络是一种单层网络，令网络由n个单元组成，N1，N2，…，N表示n个神经元，这些神经元既是输入单元，也是输出单元，其转移特性函数为f，f，...，f，门限值（阈值）为0，0，...，0。

1 2 n 1 2 n

图1Hopfield网络结构图

对于离散型Hopfield网络，各节点一般选取同样的转移函数，且为符号函数，即：

f⑴=匕⑴=…=fn(x)=sgn(x) (式1.1)

为了分析方便，选取各节点的门限值(即阈值)全部为0，即：

0=0=…=0=0 (式1.2)

同时，x=(x,x，…,x),xe{-1,+1}n为网络的输入；y=(yy，…,y),ye{-1,+1}?

1 2 n 12 n

为网络的输出；馅)=(v(),v2(t),???,vn(t)),v(t)={-1,+1}n为网络在t时刻的状态，其中te(0,1,2…)为离散时间变量；七为从七到气的连接权值，Hopfield神经网络是对称的，即有

w=w,i,je(1,2,3,…,n) (式1.3)

整个网络所有n个节点之间的连接强度用矩阵W表示，显然W为nXn方阵。

由图1可见Hopfield网络为一层结构的反馈网络，能处理双极型离散数据(即输入x￡{-l，+1})，及二进制数据(x￡{0，1})。当网络经过训练后，可以认为网络处于等待工作状态，而对网络给定初始