第5章-Hopfield神经网络与联想记忆.doc

第5章 Hopfield神经网络与联想记忆前面介绍了前向网络及其学习算法，对于所介绍的前向网络，从学习的观点来看，它是一个强有力的学习系统，系统结构简单、易于编程；从系统的观点来看，它是一个静态非线性映射，通过简单非线性处理单元的复合映射可获得复杂系统的非线性处理能力；从计算的观点来看，它并不是一强有力系统，缺乏丰富的动力学行为。反馈神经网络是一个反馈动力学系统，具有更强的计算能力。1982年美国物理学家J. Hopfield提出的单层全互连含有对称突触连接的反馈网络是最典型的反馈网络模型。Hopfield 用能量函数的思想形成了一种新的计算方法，阐明了神经网络与动力学的关系，并用非线性动力学的方法来研究这种神经网络的特性，建立了神经网络稳定性判据，并指出信息存储在网络中神经元之间的连接上，形成了所谓的Hopfield网络，称之为离散Hopfield网络。而且Hopfield还将该反馈网络同统计物理中的Ising模型相类比，把磁旋的向上和向下方向看成神经元的激活和抑制两种状态，把磁旋的的相互作用看成神经元的突触权值。这种类推为大量的物理学理论和许多的物理学家进入神经网络领域铺平了道路。1984年，Hopfield设计与研制了Hopfield网络模型的电路，指出神经元可以用运算放大器来实现，所有神经元的连接可用电子线路来模拟，称之为连续Hopfield网络。用该电路Hopfield成功的解决了旅行商（TSP）计算难题（优化问题）。Hopfield网络是神经网络发展历史上的一个重要的里程碑。把神经网络看作一种非线性的动力学系统，并特别注意其稳定性研究的学科，被称为神经动力学（Neurodynamics）。Hopfield神经网络可看作一种非线性的动力学系统，所以为了方便介绍Hopfield神经网络，本章首先简单介绍神经动力学。前面介绍的单层前向网络和多层前向网络，其思路均是先介绍网络模型再介绍相应的学习算法。本章的思路有所不同，因为Hopfield网络的权值严格来说不是通过学习来得到的，而是根据网络的用途设计出来的，当然可采用某些学习规则对权值进行微调。Hopfield网络最著名的用途就是联想记忆和最优化计算。本章首先介绍神经动力学的基本概念，接着讨论离散Hopfield网络和连续Hopfield网络模型，再通过联想记忆问题介绍Hopfield网络权值的设计方法，而Hopfield网络用于最优化计算将通过仿真实例加以介绍。5.1神经动力学1989年Hirsch把神经网络看作一种非线性的动力学系统，称为神经动力学。神经动力学分为确定性神经动力学和统计性神经动力学。确定性神经动力学将神经网络作为确定性行为，在数学上用非线性微分方程的集合来描述系统的行为，方程解为确定的解。统计性神经动力学将神经网络看成被噪声所扰动，在数学上采用随机性的非线性微分方程来描述系统的行为，方程的解用概率表示。动力学系统是状态随时间变化的系统。令v1(t), v2(t), , vN(t)表示非线性动力学系统的状态变量，其中t是独立的连续时间变量，N为系统状态变量的维数。大型的非线性动力学系统的动力特性可用下面的微分方程表示：（5.1）其中，函数是包含自变量的非线性函数。为了表述方便，可将这些状态变量表示为一个维的向量，称为系统的状态向量。（5.1）式可用向量表示为：（5.2）N维向量所处的空间中称为状态空间，状态空间通常指的是欧氏空间，当然也可以是其子空间，或是类似圆、球、圆环和其他可微形式的非欧氏空间。如果一个非线性动力系统的向量函数隐含地依赖于时间t，则此系统称为自治系统，否则不是自治的。考虑（5.2）式状态空间描述的动力系统，如果下列等式成立：（5.3）则称矢量为系统的稳态或平衡态。在包含平衡态的自治非线性动力学系统中，稳定性和收敛性的定义如下（Cook,1986）： 定义1 平衡态在满足下列条件时是一致稳定的，对任意的正数，存在正数，当时，对所有的，均有。定义2 若平衡态是收敛的，存在正数满足，则当时，。定义3 若平衡态是稳定的、收敛的，则该平衡态被称为渐进稳定。定义4 若平衡态是稳定的，且当时间趋向于无穷大时，所有的系统轨线均收敛于，则此平衡态是渐进稳定的或全局渐进稳定的。定义了动力稳定系统中平衡态的稳定性和渐进稳定性，下一步就是证明稳定性。1892年Lyapunov提出了由关于稳定性概念的基本理论，被称为Lyapunov直接方法。该方法被广泛应用于非线性、线性系统和时变、时不变系统的稳定性研究。在含有状态向量V和平衡态的非线性自治动力系统中，Lyapunov定理描述了状态空间等式（5.2）的稳定性和渐进稳定性，其定理如下：定理1 若在平衡态的小邻域内存在有界正函数E(V)，该函数对时间的导数在区域中是有界非正函数，则是稳定的。定理2 若在平衡态的小邻域内存在有界正函数E(V)，该函数对时间的导数在区域中是有界负函数，则是渐进稳定的。满足上述条件的标量函数E(V)称为平衡态的Lyapunov函数。这些定理要求Lyapunov函数E(V)是有界正函数，这样的函数定义如下：函数E(V)在状态空间中是有界正函数，则对所有的满足下列条件：（1）函数E(V)关于状态向量V中的每个元素是连续偏导的；（2）（3） if 若E(V)是Lyapunov函数，由定理1可知，如果（5.4）式成立，则平衡态是稳定的： for （5.4）其中是的小邻域。而且根据定理2可知，如果（5.5）式成立，则平衡态是渐进稳定的， for （5.5）以上简单介绍了有关神经动力学的基本概念，详细内容请见参文的相关章节。5.2离散Hopfield神经网络1982年Hopfield提出离散的Hopfield网络同前向神经网络相比，在网络结构、学习算法和运行规则上都有很大的不同。5.2.1离散Hopfield网络模型离散Hopfield网络是单层全互连的，其表现形式可为图5.1所示的两种形式。图5.1 Hopfield神经网络结构神经元可取二值0/1或-1/1，其中的任意神经元i与j间的突触权值为Wij，神经元之间联接是对称的，即Wij= Wji，神经元自身无联接,即Wii=0。虽然神经元自身无联接，但每个神经元都同其它的神经元相连，即每个神经元都将其输出通过突触权值传递给其它的神经元，同时每个神经元又都接收其它神经元传来的信息，这样对于每个神经元来说，其输出信号经过其它神经元后又有可能反馈给自己，所以Hopfield网络是一种反馈神经网络。Hopfield网络中有个n神经元，其中任意神经元i的输入用ui表示，输出用vi表示，它们都是时间的函数，其中vi(t)也称为神经元i在t时刻的状态。（5.6）式（5.6）中的bi表示神经元i的阈值或偏差。相应神经元i的输出或状态为：（5.7）其中的激励函数f ()可取阶跃函数u(t)或符号函数Sgn(t)。如取符号函数，则Hopfield网络的神经元的输出vi(t+1)取离散值1或-1，即： （5.8）5.2.2离散Hopfield网络的运行规则Hopfield网络按动力学方式运行，其工作过程为状态的演化过程，即从初始状态按“能量”（Lyapunov函数）减小的方向进行演化，直到达到稳定状态，稳定状态即为网络的输出。Hopfield网络的工作方式主要有两种形式：（1）串行（异步）工作方式：在任一时刻t，只有某一神经元i（随机的或确定的选择）依上式变化，而其他神经元的状态不变。（2）并行（同步）工作方式：在任一时刻t，部分神经元或全部神经元的状态同时改变。下面以串行（异步）工作方式为例说明Hopfield网络的运行步骤：第一步：对网络进行初始化；第二步：从网络中随机选取一个神经元i；第三步：按公式（5.6）求出该神经元i的输入ui(t)；第四步：按公式（5.7）求出该神经元i的输出vi(t+1)，此时网络中的其它神经元的输出保持不变；第五步：判断网络是否达到稳定状态，若达到稳定状态或满足给定条件，则结束；否则转到第二步继续运行。这里网络的稳定状态定义为：若网络从某一时刻以后，状态不再发生变化，则称网络处于稳定状态。 （5.9）Hopfield网络存在稳定状态，则要求Hopfield网络模型满足如下条件：网络为对称连接，即wij= wji；神经元自身无联接即wii=0。这样Hopfield网络的突触权值矩阵W为零对角对称矩阵。在满足以上参数条件下，Hopfield网络“能量函数” （Lyapunov函数）的“能量”在网络运行过程中应不断地降低，最后达到稳定的平衡状态。Hopfield网络的“能量函数” 定义为：（5.10）Hopfield反馈网络是一个非线性动力学系统，Hopfield网络按动力学方式运行，即按“能量函数”减小的方向进行演化，直到达到稳定状态。因而式（5.10）所定义的“能量函数”值应单调减小。为说明这一问题，可考虑网络中的任意神经元i，其能量函数为： （5.11）从t时刻至t+1时刻的能量变化量为：由（5.8）式可得： 因为神经元i为网络中的任意神经元，而网络中的所有神经元都按同一规则进行状态更新，所以网络的能量变化量应小于等于零，即：（5.12）所以在满足参数条件下，Hopfield网络状态是向着能量函数减小的方向演化。由于能量函数有界，所以系统必然会趋于稳定状态，该稳定状态即为Hopfield网络的输出。能量函数的变化曲线如图5.2所示，曲线含有全局最小点和局部最小点。将这些极值点作为记忆状态，可将Hopfield网络用于联想记忆；将能量函数作为代价函数，全局最小点看成最优解，则Hopfield网络可用于最优化计算。图5.2 能量函数局部极小值图示5.3 连续Hopfield神经网络 1984年Hopfield采用模拟电子线路实现了Hopfield网络，该网络中神经元的激励函数为连续函数，所以该网络也被称为连续Hopfield网络。在连续Hopfield网络中，网络的输入、输出均为模拟量，各神经元采用并行（同步）工作方式。利用这一特征Hopfield将该网络应用于优化问题的求解上，并成功地解决了TSP问题。 5.3.1连续Hopfield网络模型连续Hopfield神经网络结构如图5.3所示。图5.3 连续Hopfield神经网络模型从图5.3可见Hopfield神经网络中的每个神经元都是由运算放大器及其相关的电路组成，其中任意一个运算放大器i（或神经元i）都有两组输入：第一组是恒定的外部输入，用Ii表示，这相当于放大器的电流输入；第二组是来自其它运算放大器的反馈连接，如：其中的另一任意运算放大器j（或神经元j），用wij表示，这相当于神经元i与神经元j之间的联接权值。ui表示运算放大器i的输入电压，vi表示运算放大器i的输出电压，它们之间的关系为：（5.13）其中的激励函数f ()常取Sigmoid型函数中双曲线正切函数，即： （5.14）其中的为曲线在原点的斜率，即： （5.15）因此，称为运算放大器i（或神经元i）的增益。激励函数f ()的反函数为f -1 () 为：（5.16）连续Hopfield网络的激励函数及反函数，或连续Hopfield网络中运算放大器的输入/输出关系如图5.4所示。图5.4 激励函数及反函数波形对于图5.3所示的连续Hopfield神经网络模型，根据基尔霍夫电流定律有：（5.17）其中的。设 则（5.17）为： （5.18）与离散Hopfield神经网络相同，连续Hopfield网络的突触权值是对称的，且无自反馈，即：wij = wji wii = 0 。对于连续Hopfield神经网络模型其能量（Lyapunov）函数定义如下：（5.19）5.3.2连续Hopfield网络稳定性分析为证明该能量函数E是单调下降的，可求式（5.19）时间t的微分，即：（5.20）将式（5.18）代入（5.20）式可得： （5.21）因为f -1 (vi)为单调增函数，所以，又，因而有：（5.22）由于能量函数E是有界的，因此，连续Hopfield网络模型是稳定的。连续Hopfield网络模型对生物神经元模型做了大量的简化，但仍突出了生物系统神经计算的主要特性，如：（1） 连续Hopfield网络的神经元作为I/O变换，其传输特性具有Sigmoid特性；（2） 具有时空整合作用；（3） 在神经元之间存在着大量的兴奋性和抑制性联接，这种联接主要是通过反馈来实现；（4） 具有既代表产生动作电位的神经元，又有代表按渐进方式工作的神经元。即保留了动态和非线性两个最重要的计算特性。5.4联想记忆 联想记忆(Associative Memory，AM)是神经网络理论的一个重要组成部分，也是神经网络用于智能控制、模式识别与人工智能等领域的一个重要功能。它主要利用神经网络的良好容错性，能使不完整的、污损的、畸变的输入样本恢复成完整的原型，适于识别、分类等用途。Hopfield网络模拟了生物神经网络的记忆功能，也常常被称为联想记忆网络。5.4.1 联想记忆的基本概念人类具有联想的功能，可以从一种事物联系到与其相关的事物或其它事物。人工神经网络是对生物神经网络的模拟也具有联想的功能。人工神经网络的联想就是指系统在给定一组刺激信号的作用下，该系统能联系出与之相对应的信号。联想是以记忆为前提的，即首先信息存储起来，再按某种方式或规则将相关信息取出。联想记忆的过程就是信息的存取过程。数字计算机的信息存取方式是按地址存取方式（Addressable Memory），即一组信息对应着一定的存储单元。神经网络信息的存取（或记忆与联想）是以基于内容的存取原理为基础的，记忆地址通过记忆内容的部分描述来识别。所以这里所谓的联想记忆也称为基于内容的存取（Content-addressed memory），信息被分布于生物记忆的内容之中，而不是某个确定的地址。联想记忆网络是通过神经元之间的权重学习规则来调整神经元间的权重，从而得到各事物间的联系。各神经元间的权重共同表现为神经网络的联想记忆功能。因此，联想记忆的神经网络是由实触权重和连接结构来对信息进行记忆。这种分布式能存贮较多的模式和能够在一定的程度上恢复残缺的不完整信息。因而，他可以应用在图像复原/模式识别等领域。其具有两个比较突出的优点：l 信息的存贮是按内容存贮记忆的(content addressable memory CAM)，而传统的计算机是基于地址存贮的。l 信息的存贮是分布的，而不是集中的。1. 联想记忆的分类 从作用方式来看联想记忆分为线性联想与非线性联想。 从状态来看又可以分为静态联想与动态联想。但在通常情况下，人们把联想记忆分为自联想与异联想。Hopfield网络属于自联想。(1) 自联想记忆(Auto-Associative Memory)自联想能将网络中输入模式映射到存贮在网络中不同模式中的一种。联想记忆网络不仅能将输入模式映射为自己所存贮的模式，而且还能对具有缺省/噪音的输入模式有一定的容错能力。设在学习过程中给联想记忆网络存入M个样本：Xi i =1, 2, , M。若给联想记忆网络加以输入X = Xm+V，其中Xm是M个学习样本之一，V是偏差项（可代表噪声、缺损与畸变等），通过自联想联想记忆网络的输出为Xm，即使之复原（比如，破损照片完整照片）。一般情况下，自联想的输入与输出模式具有相同的维数。（2）异联想记忆(hetero-associative memory)最早的异联想网络模型是Kosko的双向联想记忆神经网络。异联想网络在受到具有一定噪音的输入模式激发时，能通过状态的演化联想到原来样本的模式对。假定两组模式对之间有一定对应关系， ( 如：某人照片某人姓名)，i =1, 2, , M。若给联想记忆网络加以输入X = Xm+V，比如X为某人的破损照片，通过异联想联想记忆网络的输出为Y，即得到某人的姓名。异联想的输入模式维数与输出模式一般不相等。异联想可以由自联想通过映射得到。2. 联想记忆的工作过程联想记忆的工作过程分为两个阶段一是记忆阶段，也称为存储阶段或学习阶段；二是联想阶段，也称为恢复阶段或回忆阶段。（1）记忆阶段在记忆阶段就是通过设计或学习网络的权值，使网络具有若干个稳定的平衡状态，这些稳定的平衡状态也称为吸引子（Attractor），吸引子有一定的吸引域（Basin of Attraction）)。吸引子的吸引域就是能够稳定该吸引子的所有初始状态的集合，吸引域的大小用吸引半径来描述，吸引半径可定义为：吸引域中所含所有状态之间的最大距离或吸引子所能吸引状态的最大距离，如图5.5所示。图5.5 吸引子与吸引域示意图吸引子也就是联想记忆网络能量函数的极值点，如图5.6所示。记忆过程就是将要记忆和存储的模式设计或训练成网络吸引子的过程。（2）联想阶段联想过程就是给定输入模式，联想记忆网络通过动力学的演化过程达到稳定状态，即收敛到吸引子，回忆起已存储模式的过程。简化的联想过程如图5.7示意。吸引子的数量代表着联想记忆网络的记忆容量（Memory Capacity）或存储容量（Storage Capacity），存储容量就是在一定的联想出错概率容限下，网络中存储互不干扰样本的最大数目，存储容量与联想记忆的允许误差、网络结构、学习方式以及网络的设计参数有关。简单来说，一定的网络其吸引子越多，则网络的存储容量就越大。吸引子具有一定的吸引域，吸引域是衡量网络容错性的指标，吸引域越大网络的容错性能越好，或者说网络的联想能力就越强。图5.6 联想记忆网络的能量函数图5.7 联想过程简化示意图5.4.2 Hopfield联想记忆网络如前所述，Hopfield网络是一神经动力学系统，具有稳定的平衡状态，即存在着吸引子，因而Hopfield网络具有联想记忆功能。将Hopfield网络作为联想记忆网络需要设计或训练网络的权值，使吸引子存储记忆模式。比如，现在欲存储m个n维的记忆模式，那么就要设计网络的权值使这个m模式正好是网络能量函数的m个极小值。常用的设计或学习算法有：外积法（Outer Product Method）、投影学习法（Projection Learning Rule）、伪逆法（Pseudo Inverse Method）以及特征结构法（Eigen Structure Method）等。现考虑5.3节所介绍的离散Hopfield网络的联想记忆功能。设网络有N个神经元，每个神经元均取1或-1二值，则网络共有2N个状态，这2N个状态构成离散状态空间。设在网络中存储m个n维的记忆模式（mn）：（5.23）采用外积法设计网络的权值使这m个模式是网络2n个状态空间中的m个稳定状态，即： （5.24）其中的作为调节比例的常量，这里取N = n。考虑到离散Hopfield网络的权值满足如下条件：wij= wji； wii=0，则有：（5.25）将（5.25）式用矩阵形式表示，则有：（5.26）其中I为nn单位矩阵。以上是离散Hopfield网络的存储记忆过程，下面再看其联想回忆过程。从所记忆的m个模式中任选设一模式Ul，经过编码可使其元素取值为1和-1。设离散Hopfield网络中神经元的偏差均为零。将模式Ul加到该离散Hopfield网络，假定记忆模式矢量彼此是正交的（这是个特例，容易检验），则网络的状态为： （5.27） （5.28）状态的演化为：，可见网络稳定在模式Ul。例如，对于两个记忆模式和(这是一个记忆模式矢量非正交的例子)，按公式（5.25）设计网络权值为：可见该权值满足离散Hopfield网络的条件。现将作为网络的输入，则有：可见状态为网络的稳定状态，即网络记住了该状态。同样，对状态向量而言，有：可见状态也为网络的稳定状态，即网络也记住了该状态。5.4.3Hopfield联想记忆网络的运行步骤第一步：设定记忆模式。将欲存储的模式进行编码，得到取值为1和-1的记忆模式（mn）：；第二步：设计网络的权值。 ，其中是神经元j到i突触权值，一旦计算完毕，突触权值将保持不变；第三步：初始化网络状态。将欲识别模式设为网络状态的初始状态，即：，是网络中任意神经元i在t=0时刻的状态；第四步：迭代收敛。根据下列公式随机地更新某一神经元的状态 ，t = t+1反复迭代直至网络中所有神经元的状态不变为止，假设此时的t=T；第五步：网络输出。这时的网络状态（稳定状态），即为网络的输出y=vi (T)。以上的第一步和第二步是联想记忆网络记忆过程，第三步至第五步所组成的迭代过程是联想记忆网络的联想过程。对于以上所介绍的Hopfield联想记忆网络，需要做几点说明：（1） 以上所介绍的Hopfield联想记忆网络的激励函数为符号函数，即神经元的状态取1和-1的情况。对于联想记忆网络的激励函数为阶跃函数，即神经元的状态取1和0时，相应的公式有所变化。设在网络中存储m个n维的记忆模式（m Ptest=1 -1; -1 1; Ttest=simuhop(Ptest，W，B,3)Ttest = 1 -1 -1 1如果想知道所设计的网络对任意输入矢量的收敛结果，可以进行测试。一般运行次数越多，收敛情况越好。如图5.9所示是对某一随机输入矢量的收敛曲线，图5.10是对25个随机输入矢量的收敛曲线。图5.8 目标平衡点位置图图5.9 某一随机输入矢量的收敛过程图5.10 网络任意输入矢量的收敛过程【例5.3】观察不稳定平衡点。同例5.2的网络，网络存储的平衡点不变。我们已经知道，用任意的随机输入矢量去对网络进行测试时，在若干次循环后均能够使其收敛到所设计的平衡点上。然而这些并不能保证网络没有其他的平衡点，让我们尝试一下。例如，取所给目标矢量连线的垂直平分线上的点作为输入矢量： P=-1 -0.5 0 0.5 1.0; -1 -0.5 0 0.5 1.0可以采用循环程序来观察每一次循环以后网络的输出值。能够看到所有的输出最终趋于原点。它是一个不稳定的平衡点，因为任何一个不在以（-1,-1）到(1,1)点所连成的垂直平分线上的点作为网络的初始输入矢量，经过循环都将最终收敛到所设计的稳定平衡点上。 图5.11 不稳定平衡点的收敛走向图5.11是矢量P循环5次的收敛过程，最终都趋于原点，其输出如下：Output Vectors:AA = 1.0e-003 * -0.5531 -0.2765 0 0.2765 0.5531 -0.5531 -0.2765 0 0.2765 0.5531【例5.4】含有三个神经元的Hopfield网络的设计实例.网络所要存储的目标平衡点为一个列矢量T： T=1 1; -1 1;-1 -1解：网络的目标存储点如图5.12所示。图5.12 目标平衡点位置图用目标矢量作为网络输入来测试其是否被存储到网络中，网络运行后输出确实为目标矢量。网络能够使其收敛到自己本身。如图5.13所示是对某一随机输入矢量的收敛曲线，图5.14是对25个随机输入矢量的收敛曲线。但是，网络存在不稳定平衡点。我们尝试一下，例如，取所给目标矢量连线的平分面上的点作为输入矢量： P=-1 -1 -0.5 1 1 0; 0 0 0 0 0.01 -0.2;-1 1 0.5 -1.01 -1 0图5.13 某一随机输入矢量收敛过程图5.15是矢量P循环40次的收敛过程，前4个矢量全部收敛到不稳定平衡点（1 0 -1）上。然而，即使第5个和第6个矢量起始于很接近不稳定平衡点，它们仍然能够以自己的方式逐步趋于所设计的平衡点。其输出如下：Output Vectors:AA = 1 1 1 1 1 1 0 0 0 0 1 -1-1 -1 -1 -1 -1 -1图5.14 网络任意输入矢量收敛过程图5.15 三维空间不稳定的平衡点【例5.5】伪稳定平衡点（网络的伪状态）。设计一个存储下面4组5神经元平衡点的神经网络： T= 1 1 -1 1; -1 1 1 -1; -1 -1 -1 1; 1 1 1 1; -1 -1 1 1 可以重复使用前面的程序，执行程序以后，通过网络的设计结果，验证网络可以证实它们确实能够收敛到自己本身。然后，我们向网络输入随机初始矢量。结论是，偶尔有些状态稳定到伪渐近稳定点上。此网络除了所设计的平衡点外，还有另外两个伪稳定点（伪状态）。【例5.6】Hopfield网络用于求解TSP问题 Hopfield网络除了在模式识别方面有重要应用外，对于解决组合优化问题它也有许多用途。组合优化问题，就是在给定的约束条件下，求出使目标函数极小（或极大）的变量组合问题。将Hopfield网络应用于求解组合优化问题，就是把目标函数转化为网络的能量函数，把问题的变量对应于网络的状态。当网络的能量函数收敛于极小值时，网络的状态就对应于问题的最优解。由于神经网络的计算量不随维数的增加而发生指数性的剧增，所以对于优化问题的快速计算特别有效。为了说明这个问题，这里给出最有代表性的组合优化实例，也就是所谓的“旅行商最优化路径问题”，简称TSP（Traveling Salesman Problem）。80年代正是因为Hopfield用其连续型Hopfield网络成功的求解了这个具有相当难度地组合优化问题，才使人工神经网络重新被重视起来。TSP（Traveling Salesman Problem，TSP）问题也被称为“旅行商最优路径问题”。其命题与问题如下：命题：假定有个城市它们之间的相互距离分别为。问题是寻找一条闭合路经，此路径历经每个城市且仅经过一次，返回起始城市。要求此路径长度最短。问题：给定，可能存在闭合路径数目为。为求，按传统的求解方式利用搜索法，需要找出全部路径之组合。随着的增加，计算量急剧增加，利用计算机也难以解决。目前对这一问题已有许多种其它的解法。但当城市数比较大时，会产生所谓“组合爆炸”问题，需要很长的时间去求解。对于一n城市的TSP问题，存在可能的不同的路径有(n-1)/2条，当N较大时，其数量是惊人的。计算每一条路径都要求出n个距离之和，这样各可能路径及其距离之和的计算量将正比于n!/2。表5.1给出了用每秒可进行数亿次运算的Cray计算机搜索TSP问题所需的时间。尽管如此，这里还没有涉及到计算所需的巨大存储空间。从而可见用搜索法求解较大的TSP问题是不现实的。表5.1 TSP问题的计算量城市数n7152050100200加法量2.51036.510111.210181.51064510157110374搜索时间2.510-5秒1.8小时350年51048年10142年10358年1985年Hopfield和Tank用Hopfield网络求解n=30的TSP问题，使用900个神经元组成的网络在0.2s就得到了30个城市的旅行商次优解，从而开创了神经优化的新途径。用其它方法很难做到这一点。TSP问题，实际上不要求得到严格的最优解，如果用人脑进行比较，是比较容易判断的。TSP问题属于人工智能问题，可用ANN解决。下面来看一看对这个问题的具体求解方法。构造NN模型，即矩阵，如55，如果把矩阵的每个元素对应于神经网络的中的每个神经元，则这个问题可用55=25个神经元组成的Hopfield网络来求解。 城市次序 1 2 3 4 5 A 0 1 0 0 0 B 0 0 0 1 0 C 1 0 0 0 0 D 0 0 0 0 1 E 0 0 1 0 0。这是一个置换矩阵，满足如下条件：1） 一个城市只能被访问一次，即每行只有一个“1”，其余元素为“0”；2） 一次只能访问一个城市，即每列只有一个“1”，其余元素为“0”；3） 共有n个城市，即矩阵的全部元素中“1”之总和为。对应于置换矩阵，为把问题的约束条件和最优化条件的要求分解出来，置换矩阵必须满足上述条件。然后把问题的目标函数转化为能量函数，并将问题的变量对应于网络的状态。解决这个问题有一定的复杂性，需要一定的技巧。利用 个神经元组成Hopfield人工神经网络：1） 各神经元的状态对应于置换矩阵中的各元素值（1或0）；2） 神经元之间的突触连接强度对应于各城市的距离；3） 期望网络演变的最终结果给出最优解，所对应的路径顺序；4） 各城市距离信息将通过