第5章Hopfield神经网络











1982年，美国加州理工学院的生物物理学家Hopfield教授提出了一种模拟人脑联想记忆功能的单层反馈神经网络，后来人们将这种反馈网络称为Hopfield网络。1984年，Hopfield和Tank用模拟电子线路实现了Hopfield网络，并用它成功地求解了旅行商问题。

 5.1Hopfield神经网络概述
Hopfield神经网络(Hopfield Neural Network)是一种具有反馈连接结构的递归神经网络，输入信息经过Hopfield神经网络处理后，计算得到的输出会反馈到输入端，从而对下一时刻的系统状态产生影响，在计算过程中Hopfield神经网络的反馈过程会一直反复进行，直至停止输入。Hopfield神经网络是由单层神经元互相完全连接构成的反馈神经网络，其结构如图51所示，网络的全连接结构使得其在进行计算时，每个神经元既是输入也是输出，即每个神经元接收其他所有神经元传递的信息。网络的反馈结构使得神经网络每一时刻的计算都与神经网络前一时刻的计算相关。


图51Hopfield神经网络结构图

Hopfield神经网络循环递归的网络迭代过程使得网络最终可以达到稳定状态，因此可以引入能量函数的概念，采用能量函数的形式描述网络收敛的过程，即用能量函数达到极小值的计算过程描述网络收敛到稳态的过程。能量函数的应用为神经网络运行的状态是否达到稳态提供了可靠的判断依据。递归神经网络的网络状态与时序相关，随着网络的迭代最终能达到稳定状态，这是与前向网络比较明显的区别之一，但递归神经网络收敛结果与网络参数的选取有很强的相关性，合理的网络参数是递归神经网络正常工作的基础。
Hopfield神经网络模型有离散型和连续型两种，离散型适用于联想记忆，连续型适合处理优化问题。

 5.2离散型Hopfield神经网络
Hopfield神经网络作为一种全连接型的神经网络，曾经为神经网络的发展开辟了新的研究途径。它利用与层次型神经网络不同的结构特征和学习方法，模拟生物神经网络的记忆机理，获得了令人满意的结果。离散型Hopfield神经网络(Discrete Hopfield Neural Network, DHNN)是Hopfield最早提出的单层反馈网络，其网络结构中神经元的输出只有“1”和“-1”两种取值，分别表示神经元激活和抑制状态。
5.2.1离散型Hopfield神经网络结构及工作方式
离散型Hopfield神经网络的网络结构如图52所示。




图52离散型Hopfield神经网络的网络结构


由图52可以看出离散型Hopfield神经网络中的每个神经元xj(j=1,2,…,n)都是彼此连接的，神经元的阈值为θj(j=1,2,…,n)，连接网络中的交叉点表示的是连接的权值用wij(i,j=1,2,…,n)表示。离散型Hopfield神经网络中的神经元都是二值输出神经元，即神经元根据权值对输入进行累加求和，经过非线性映射将输入映射为输出“1”或“-1”。
离散型Hopfield神经网络的单个神经元结构如图53所示。




图53离散型Hopfield神经网络的单个神经元结构



离散型Hopfield神经网络中的神经元采用经典感知机模型进行信息计算且每个神经元的功能都相同，其输出值称为状态，用xj(j=1,2,…,n)表示，wij表示神经元i与神经元j之间的连接权值，神经元的非线性映射由激活函数f(·)表示，每个神经元均有一个阈值θj(j=1,2,…,n)。n个神经元的状态集合构成的离散型Hopfield神经网络的状态，如式(51)所示。
X=［x1,x2,…,xn］T(51)
网络的输入即网络的初始状态如式(52)所示。
X(0)=［x1(0),x2(0),…,xn(0)］T(52)
神经元j的净输入sj与输出xj分别如式(53)和式(54)所示。
sj=∑ni=1xiwij-θj(53)

xj=f(sj)=sgn(sj)=1，sj>0

-1，sj≤0(54)
当网络中各个神经元的状态改变时，网络的状态也会随之改变，网络稳定的标志是网络中每个神经元的状态都不再改变，此时的稳定状态就是该网络的输出。
Hopfield网络的工作方式主要有两种形式： 
串行(异步)工作方式： 在任一时刻t，只有某一神经元(随机的或确定的)的状态发生变化，而其他神经元的状态不变。
并行(同步)工作方式： 在任一时刻t，部分神经元或全部神经元的状态同时改变。
1) 串行(异步)工作方式
离散型Hopfield神经网络串行工作时，神经网络按照预先设定的顺序或随机选定的方式每次激活一个神经元进行状态调整，而其他神经元保持不变，神经元状态调整计算过程如式(55)所示。
xj(t+1)=sgn(sj(t)),j=i

sj(t),j≠i，i,j=1,2,…,n(55)
2) 并行(同步)工作方式
离散型Hopfield神经网络并行工作时，神经网络中的神经元同时进行状态调整，神经元状态调整计算过程如式(56)所示。

xj(t+1)=sgn(sj(t))，j=1,2,…,n(56)
经过迭代更新，一个离散型Hopfield神经网络就会逐渐达到稳定状态，判断稳定的依据如式(57)所示。
xj(t+1)=xj(t)=f(sj(t))，j=1,2,…,n(57)
从初始状态开始，网络沿能量递减的方向进行不断演化并最终趋于稳定。离散型Hopfield神经网络的运行流程如下： 



(1) 初始化网络状态。
(2) 从网络中随机选取一个神经元i。
(3) 按照式(53)计算神经元i在t时刻的净输入si(t)。
(4) 按照式(54)计算神经元i在t+1时刻的输出xi(t+1)，除i之外的其他神经元状态保持不变。
(5) 使用式(57)判断网络是否达到稳定状态，若未达到则跳转到(2)继续向下执行； 若已达到稳定状态则停止网络运行。
离散型Hopfield神经网络的运行流程如例51所示。




【例51】一个三个结点的离散型Hopfield神经网络的初始状态为X(0)=(-1,-1,-1)，权值矩阵W和阈值 θ如下所示，求解该网络的稳定状态。
W=0-0.50.5
-0.500.6
0.50.60θ=-0.1
0
0
解： 
t=0： 神经网络初始状态为X(0)=(-1,-1,-1)。
t=1： 选取结点1，则结点1的状态变化如下。
x1(1)=sgn［-1×0+(-1)×(-0.5)+(-1)×0.5-(-0.1)］=sgn(0.1)=1，此时网络状态为X(1)=(1,-1,-1)。
t=2： 选取结点2，则结点2的状态变化如下。
x2(2)=sgn［1×(-0.5)+(-1)×0+(-1)×0.6-0］=sgn(-1.1)=-1，此时网络状态为X(2)=(1,-1,-1)。
t=3： 选取结点3，则结点3的状态变化如下。
x3(3)=sgn［1×0.5+(-1)×0.6+(-1)×0-0］=sgn(-0.1)=-1，此时网络状态为X(3)=(1,-1,-1)。
t=4： 选取结点1，则结点1的状态变化如下。
x1(4)=sgn［1×0+(-1)×(-0.5)+(-1)×0.5-(-0.1)］=sgn(0.1)=1，此时网络状态为X(4)=(1,-1,-1)。
t=5： 选取结点2，则结点2的状态变化如下。
x2(5)=sgn［1×(-0.5)+(-1)×0+(-1)×0.6-0］=sgn(-1.1)=-1，此时网络状态为X(5)=(1,-1,-1)。
t=6： 选取结点3，则结点3的状态变化如下。
x2(6)=sgn［1×0.5+(-1)×0.6+(-1)×0-0］=sgn(-0.1)=-1，此时网络状态为X(6)=(1,-1,-1)。
至此各神经元输出已经不再改变，故判定网络已经进入稳定状态(1,-1,-1)。
5.2.2离散型Hopfield神经网络的吸引子与能量函数
Hopfield神经网络有一个显著特点，就是加入了“能量函数”的概念，同时将神经网络与动力学之间的关系进行了阐述。网络的吸引子(attractor or fixedpoint)是指网络达到稳定时的状态X。吸引子能够决定一个动力学系统的最终行为，它同时能够作为信息的分布存储记忆和神经优化计算的基础。若把需要记忆的样本信息存储于不同的吸引子，当输入含有部分信息的样本时，网络的演变过程就是从部分信息中还原全部信息的过程，即实现联想记忆。
如果网络的状态X满足X=f(WX-T)，则称X为网络的吸引子。在一个Hopfield网络中，通常有多个吸引子，每个吸引子为一个能量的局部最优点。
离散型Hopfield神经网络实质上是一个离散的非线性动力学系统，网络从初态X(0)经过有限次的迭代达到X(t)=X(t+1)状态，则表示网络已处于稳定状态，这种稳定状态也称为吸引子。反馈网络的相图通常如图54所示。



图54反馈网络的3种相图


如图54(a)所示，网络逐渐迭代到稳定状态。如图54(b)所示，网络处于不稳定状态，但由于离散型Hopfield神经网络状态只有1和-1两种情况，因此网络只会出现在限幅内的自持振荡，通常也将此种网络称为有限环网络。如图54(c)所示，网络状态的轨迹在某个确定的范围内变迁，既不重复也不停止，状态运动轨迹不会发散到无穷远，这种现象称为混沌。由于离散型Hopfield神经网络状态是有限的，因此不存在混沌现象。
(1) 对于离散型Hopfield神经网络，若按照异步方式调整网络状态，对于任意初态离散Hopfield神经网络，网络都最终收敛到一个吸引子。能量函数如式(58)所示。
E(t)=-12∑ni=1∑nj=1wijxixj+∑ni=1θixi

=-12XT(t)WX(t)+XT(t)T(58)
设网络能量函数的改变量为ΔE，网络状态的改变量为ΔX，如式(59)所示。
ΔE(t)=E(t+1)-E(t)

ΔX(t)=X(t+1)-X(t)(59)
因此： 
ΔE(t)=E(t+1)-E(t)

=-12［X(t)+ΔX(t)］TW［X(t)+ΔX(t)］+［X(t)+ΔX(t)］TT-
-12XT(t)WX(t)+XT(t)T

=-ΔXT(t)WX(t)-12ΔXT(t)WΔX(t)+ΔXT(t)T

=-ΔXT(t)［WX(t)-T］-12ΔXT(t)WΔX(t)(510)
由于网络状态异步更新，即第t个时刻只有一个神经元j调整状态，将ΔX(t)=［0,0,…,0,Δxj(t),0，…,0］T代入式(510)，可得式(511)。
ΔE(t)=-Δxj(t)∑ni=1(wij-Tj)-12Δx2j(t)wjj(511)
对于离散型Hopfield神经网络来说，W为对称矩阵，神经元之间不存在自反馈，即Wjj=0，因此式(511)可以简化为式(512)。
ΔE(t)=-Δxj(t)sj(t)(512)
由于离散型Hopfield神经网络状态包括1和-1两种，因此式(512)可能会出现以下情况： 
情况一： xj(t)=-1，xj(t+1)=1，则由状态变化公式(59)得Δxj(t)=2,由sj(t)≥0，由能量变化量式(512)得ΔE(t)≤0。
情况二： xj(t)=1，xj(t+1)=-1，故Δxj(t)=-2，sj(t)＜0，得ΔE(t)＜0。
情况三： xj(t)=xj(t+1)，故Δxj(t)=0，所以有ΔE(t)=0。
综合三种情况可得ΔE(t)≤0,即网络的演变过程中能量一直处于非递增状态，又由于离散型Hopfield神经网络中结点状态只有1或-1两种情况，能量函数E(t)拥有下界，因此网络会收敛到ΔE(t)=0。
(2) 对于离散型Hopfield神经网络，若按照同步方式调整网络状态，且连接权矩阵W为非负定对称阵，则对于任意初态，网络都最终收敛到一个吸引子。如式(513)所示。
ΔE(t)=E(t+1)-E(t)

=ΔXT(t)［WX(t)-T］-12ΔXT(t)WΔX(t)

=-ΔXT(t)sj(t)-12ΔXT(t)WΔX(t)

=-∑nj=1Δxj(t)sj(t)-12ΔXT(t)WΔX(t)(513)
由于-Δxj(t)sj(t)≤0，W为非负定对称阵，因此ΔE(t)≤0，即网络最终会收敛到常数，对应的稳定状态称为网络的一个吸引子。
通过上述分析可以看出,如果连接权值矩阵W设计不能满足非负定对称阵的要求，网络就会发生振荡。异步工作方式相比同步工作方式更好的稳定性，但没有并行处理能力。
1. 吸引子的性质
性质1： 若X是一个网络的吸引子，且阈值为0，在sgn(0)处有xj(t+1)=xj(t),则-X也是该网络的一个吸引子。
证明： 因为X是吸引子，则X=f(WX)，从而有式(514)。
f［W(-X)］=f［-WX］=-f［WX］=-X(514)
性质2： 若Xa是网络的一个吸引子，Wii=0，且sgn(0)=1，则与Xa的海明距离dH(Xa,Xb)=1的Xb一定不是吸引子。
证明： 两个向量的海明距离dH(Xa,Xb)是指两个向量中不同元素的个数。设Xa1≠Xb1,Xaj=Xbj； j=1,2,3,…,n。因为W11=0，由吸引子的定义可得式(515)。
Xa1=f∑ni=2WiiXai-T1=f∑ni=2WiiXbi-T1(515)
由于Xa1≠Xb1，因此可得式(516)。
Xb1≠f∑ni=2WiiXbi-T1(516)
故可得Xb不是该网络的吸引子。
2.  吸引域的基本概念
大量的样本存在缺损或包含噪声的情况，当离散型Hopfield神经网络想要实现正确的联想记忆，就要求当样本状态脱离吸引子一定范围后，应该有能力调整回原状态，吸引子的这种吸引范围称为吸引域。
定义51设Xa为吸引子，若从X到Xa存在一条路径可达，则称X弱吸引到Xa，若对集合X={X1,X2,…,Xn}均有X弱吸引到Xa，则称集合X为Xa的弱吸引域； 若从X到Xa迭代中每条路径均可达，则称X强吸引到Xa，若对集合X={X1,X2,…,Xn}均有X强吸引到Xa，则称集合X为Xa的强吸引域。
【例52】在离散型Hopfield神经网络中，n=4； Tj=0； j=1,2,3,4； 向量Xa、Xb和权值矩阵W分别为式(517)所示。
Xa=1
1
1
1,Xb=-1
-1
-1
-1,W=0222
2022
2202
2220(517)
尝试探讨Xa,Xb是否为该网络的吸引子，并验证其是否具有联想记忆能力。
解： 由吸引子定义式(514)可得式(518)。
f(WXa)=f6
6
6
6=sgn(6)
sgn(6)
sgn(6)
sgn(6)=1
1
1
1=Xa(518)
因此，Xa是网络的吸引子，根据吸引子性质Xb=-Xa，所以，Xb也是网络的吸引子。
验证离散型Hopfield神经网络的联想记忆能力： 
设有样本X1=-1
1
1
1,X2=1
-1
-1
-1, X3=1
1
-1
-1，当离散型Hopfield神经网络以异步方式工作时Xa、Xb两个吸引子对三个样本的吸引能力。
设离散型Hopfield神经网络初态X(0)=X1=-1
1
1
1,神经元的调整顺序为［1,2,3,4］，则有X(1)=Xa=1
1
1
1,可以得到异步方式只经过一步迭代，样本X1即收敛于Xa。
同样，设离散型Hopfield神经网络初态X(0)=X2=1
-1
-1
-1，神经元的调整顺序为［1,2,3,4］，则有X(1)=Xb=-1
-1
-1
-1，可以得到异步方式只经过一步迭代，样本X2即收敛于Xb。
现假设离散型Hopfield神经网络初态X(0)=X3=1
1
-1
-1，神经元的调整顺序为［1,2,3,4］，则有X(1)=-1
1
-1
-1， X(2)=-1
-1
-1
-1=Xb，可以得到异步方式只经过两步迭代，样本X3即收敛于Xb。现修改神经元调整顺序为［3,4,1,2］，则有X(1)=1
1
1
-1，X(2)=1
1
1
1=Xa。
通过上述实例分析可以看出当离散型Hopfield神经网络异步更新时，异步调整顺序确定稳定的吸引子与初态有关； 初态确定稳定的吸引子与异步调整顺序有关。
5.2.3离散型Hopfield神经网络的连接权值设计
5.2.2节介绍了离散型Hopfield神经网络的能量函数。如果能够将记忆的样本信息存储在不同的能量极值点上，然后给网络输入某一状态，网络“学习”后达到稳定状态，就可以发挥联想记忆功能，联想出之前记忆的样本。这便是离散型Hopfield神经网络的一个重要功能——联想记忆功能。要实现联想记忆，离散型Hopfield神经网络必须具有两个基本条件： ①网络能收敛到稳定的平衡状态，并以其作为样本的记忆信息； ②具有回忆能力，能够从某一残缺的信息回忆起所属的完整的记忆信息。
离散型Hopfield神经网络实现联想记忆过程分为以下两个阶段。
学习记忆阶段: 其也称为离散型Hopfield神经网络的学习过程。指研究者通过设计一种方法确定一组合适的权值，使离散型Hopfield神经网络记忆达到稳定状态。
联想回忆阶段: 联想过程就是给定输入模式，联想记忆网络通过动力学的演化过程达到稳定状态，即收敛到吸引子，回忆起已存储模式的过程。
网络的记忆样本，即能量函数的最小值的分布，由网络的连接权值和阈值决定。所以，离散型Hopfield神经网络实现联想记忆的重点就是根据能量极值点设计一组适合的网络连接权值和阈值。
吸引子的分布是由网络的权值(包括阈值)决定的，设计吸引子的核心就是如何设计一组合适的权值。为了使所设计的权值满足要求，权值矩阵应符合以下要求： 
① 为保证异步方式工作时网络收敛，W应为对称阵； 
② 为保证同步方式工作时网络收敛，W应为非负定对称阵； 
③ 保证给定的样本是网络的吸引子，并且要有一定的吸引域。
具体设计时，可以采用以下不同的方法。
(1) 比较常用的离散型Hopfield神经网络连接权值设计方法是基于Hebb学习规则的外积和法。设共有K个记忆样本Xk，k=1，2，…，K，X∈{-1,1}n，并设样本两两正交，且n>K，则连接权值矩阵W为记忆样本的外积和如式(519)所示。
W=α∑Kk=1Xk(Xk)T(519)
又知wii=0，所以式(519)可改写为式(520)。
W=α∑Kk=1［Xk(Xk)T-I］(520)
其中，I为单位矩阵； α为常数，且α>0，α一般取1或1n。
(2) 除基于Hebb学习规则的外积和法之外，还有更简单的联立方程法、δ学习规则方法、伪逆法、正交化法等，但是一般更通用的还是外积和法。
δ学习规则方法基本公式是式(521)和式(522)。

ΔW=η·δ·P(521)

wij(t+1)=wij(t)+η［T(t)-A(t)］P(t)(522)
即通过计算该神经元结点的实际激活值A(t)，与期望状态T(t)进行比较，若不满足要求，将两者的误差的一部分作为调整量，若满足要求，则相应的权值保持不变。
伪逆法具体方法为： 
设输入样本X=［X1,X2,…，XN］，输入输出之间用权重W来映射，则如式(523)所示。
Y=sgn(WX)(523)
由此可得式(524)。
W=N*P*(524)
其中，P*为伪逆，有P*=(PTP)-1PT，如果输入样本之间是线性无关的，则PTP满秩，其逆存在，则可求出连接权矩阵W。
在网络连接矩阵确定后，网络就可以进行工作，能够接收输入模式向量，实现其联想记忆功能。
但是实际上，离散型Hopfield神经网络的联想记忆功能是与其记忆容量和样本差异有关。当记忆样本数量少并且相互之间区别大时，网络的记忆效果较准确； 而当记忆样本过多且相互之间较为相似时，容易引起混淆，网络最终达到的稳定状态就不一定会是之前记忆的样本。这两项中有一项不满足要求，最后结果的出错率就会大大提高。
5.2.4离散型Hopfield神经网络的信息存储容量
信息存储是指将一组向量存储在网络中的过程，存储过程主要是调整神经元之间的连接权重，因此可以看作是一种学习的过程。
信息存储容量是神经网络处理能力的重要衡量标准之一。当网络规模一定时，神经网络所能记忆的样本数量是有限的，不同的神经网络拥有不同的存储能力，神经网络的存储容量与神经网络的规模、连接权值的设计算法以及记忆模式向量的分布都有关。离散型Hopfield神经网络的联想记忆能力是通过将一些样本存储在不同的能量极值上实现的，联想记忆能力与离散型Hopfield的信息存储容量密切相关。
以下列出一些关于离散型Hopfield神经网络的信息存储容量的定义和定理。
定义52网络能够存储的最大样本模式数称为网络的信息存储容量。
定理51若具有n个神经元的离散型Hopfield神经网络的连接权矩阵的主对角元素的值为0，则该离散型Hopfield神经网络的最大信息存储容量为n。
定理52若有m个两两正交的记忆模式Xk=(xk1,xk2,…,xkn)(k=1,2,…,m),xi∈{-1,1}(i=1,2,…,m)，其中n>m，并且网络连接权矩阵采用外积和法，由式(520)计算得到，则这m个记忆模式都是具有n个神经元的离散型Hopfield神经网络的稳定状态。
定理53若有m个两两正交的记忆模式Xk=(xk1,xk2,…,xkn)(k=1,2,…,m),xi∈-1,1(i=1,2,…,m)，其中n≥m，并且网络连接权矩阵采用外积和法，由式(519)计算得到，则这m个记忆模式都是具有n个神经元的离散型Hopfield神经网络的稳定状态。
从以上定理可知，当用外积和法设计离散型Hopfield神经网络时，如果记忆模式都满足两两正交的条件，则规模为n的离散型Hopfield神经网络最多可记忆n个样本模式，但是实际情况下，模式样本不可能都满足两两正交的条件，对于非正交模式，离散型Hopfield神经网络的信息存储能力会大大降低，其信息存储容量一般为0.13n~0.15n。
当离散型Hopfield神经网络只记忆一个稳定模式时，该模式肯定被其准确无误地记住，但当需要记忆的模式增加时，记忆模式相互影响，会造成连接权值的改变，可能会出现“权值移动”和“交叉干扰”两种情况。
在离散型Hopfield神经网络的学习过程中，Xk=(xk1,xk2,…,xkn)T,(k=1,2,…,m),xi∈{-1,1}(i=1,2,…,n)，网络对权值的更新是逐步实现的，即对权值W，网络连接权值的学习遵循下列模式，如式(525)所示。
W0=0

k=1,2,…,m

Wk=Wk-1+(Xk)T(Xk)-I(525)
从上述连接权值学习过程的描述可以看出，连接权矩阵是每次在上一次得到权值的基础上进行累加，即在原来值的基础上进行了移动，这样网络就有可能遗忘掉部分先前的记忆模式。
从动力学的角度来看，k值较小时，记忆样本会成为该离散型Hopfield神经网络的稳定状态。但是随着k值的增加，连接权值不断移动，各个记忆模式相互交叉，不但难以使后来的样本成为该网络的稳定状态，即新的样本记不住，而且有可能遗忘之前已经记忆住的模式，这种现象称为“疲劳”。
离散型Hopfield神经网络在学习多个样本后，在联想回忆阶段即验证该记忆样本时，所产生的干扰称为交叉干扰。
事实上，当网络规模n一定时，如果需要记忆的模式很多的话，联想记忆时出现错误的可能性就会很大，反之，要求出错率越低，网络的信息存储容量上限越小。有研究表明当存储容量超过0.15n时，联想记忆时就有可能出错，错误结果对应的是能量的局部极小点。可以通过改进网络拓扑结构或改进网络的权值设计方法提高网络存储容量。

 5.3连续型Hopfield神经网络
1984年，美国加州工学院物理学家Hopfield使用运算放大器实现神经元，用电子线路模拟神经元的连接，设计并研制了连续型Hopfield神经网络(Continuous Hopfield Neural Network，CHNN)，并用它解决了旅行商计算难题。连续型Hopfield神经网络在原理上基本与离散型Hopfield神经网络一致，但连续型Hopfield模型神经元的输出是(0,1)区间内的连续值，且神经元之间采取同步工作的方式。因此，它在并行性、实时性、分布性和协同性等方面会比离散型Hopfield神经网络更接近生物神经系统。
5.3.1连续型Hopfield神经网络的结构
与离散型Hopfield神经网络类似，连续型Hopfield神经网络的结构如图55所示，它是单层反馈的双向对称全互连非线性网络，每个结点的输出会反馈至结点的输入。其连接权值如式(526)和式(527)所示。
wij=wji(526)

wii=0(527)

图55中，三角形状的器件为具有正反向输出的运算放大器，它的输入和输出用来模仿神经元输入和输出之间的非线性关系。电子线路与神经网络之间关系为： 运算放大器——神经元； 神经元输入——运放输入电压uj； 神经元输出——运放输出电压Vj(输出有正向输出Vj，和反向输出Vj)； 连接权值Wij——输入端电导(电阻的倒数)； 阈值——输入偏置电流Ij。


图55连续型Hopfield神经网络的结构

5.3.2连续型Hopfield神经网络的神经元
用模拟电路实现的连续型Hopfield神经网络的神经元结点如图56所示。




图56连续型Hopfield神经网络神经元


如模拟电路所示，(V1,V2,…,Vn)是电路的输入电压，表示的是上层各神经元的输出； (R1j,R2j,…,Rnj)是电路的连接电阻，其倒数表示的是上层各神经元与神经元j的连接权值； Ij是电路的外加偏置电流，表示的是神经元j的阈值； Uj是电路中放大器的输入电压，表示的是神经元j的净输入； 电路中的等效电阻Pj和输入电容Cj存在着并联关系，这些元件决定了神经元j的时间常数，目的是模拟生物神经元中存在的延时特性； f是电路的放大器，表示的是神经元j的激活函数； Vj是电路中放大器的输出电压，表示的是神经元j的输出，如式(528)所示： 
Vj=f(Uj)(528)
其中，激活函数f(·)是一个S型曲线函数，其表达式如式(529)所示： 
f(x)=11+e-2xs0(529)
其中，s0为常数，决定了激活函数的曲线形状。当s0趋近0时，则该S型曲线函数趋向于变为阶跃函数，这表明离散型Hopfield神经网络本质上是连续型Hopfield神经网络的一种。
5.3.3连续型Hopfield神经网络的能量函数
对于连续型Hopfield神经网络的稳定性，同样可以采用能量函数加以判别。现假设一个具有n个神经元的连续型Hopfield神经网络，若其满足如下条件，则可判定其能达到稳定状态： ①网络的结构对称，即wij=wji； ②当i=j时，wij=0； ③网络神经元的激活函数单调、连续、递增且具有反函数。满足上述条件的连续型Hopfield神经网络的能量值随着网络状态的变化而减少，即该网络的能量函数E是单调递减函数。当能量值耗尽或者达到最小时，代表连续型Hopfield神经网络达到稳定状态。能量函数E如式(530)所示： 
E=-12∑ni=1∑nj=1wijViVj+∑ni=11Ri∫Vi1f-1(v)dv-∑ni=1ViIi(530)
下面对能量函数的单调递减性进行证明： 
dEdt=∑ni=1dEdVi·dVidt

=∑ni=1d-12∑ni=1∑nj=1wijViVj+∑ni=11Ri∫Vi1f-1(v)dv-∑ni=1ViIidVi·dVidt

=∑ni=1-12d∑ni=1∑nj=1wijViVjdVi+d∑ni=11Ri∫V1f-1(v)dvdVi-

d∑ni=1ViIidVi·dVidt(531)
其中，
∑ni=1d∑ni=1∑nj=1wijViVjdVi=∑ni=1d∑0w12V1V2…w1nV1Vn
w21V2V10…w2nV2Vn
︙︙︙
wn1VnV1wn2VnV2…0dVi

  =2∑ni=1∑nj=1wijVj(532)

∑ni=1d∑ni=11Ri∫vi1f-1(v)dvdVi=∑ni=1UiRi(533)

∑ni=1d∑ni=1ViIidVi=∑ni=1Ii(534)
综合式(532)和式(534)可得： 
dEdt=∑ni=1-12d∑ni=1∑nj=1wijViVjdVi+d∑ni=11Ri∫Vi1f-1(v)dvdVi-d∑ni=1ViIidVi·dVidt
=-12×2∑ni=1∑nj=1wijVj+∑ni=1UiRi-∑ni=1Ii·dVidt

=-∑ni=1∑nj=1wijVj+Ii-UiRi·dVidt(535)
代入Hopfield网络运动方程CidUidt=∑nj=1wijVj-UiRi+Ii可得： 
dEdt=-∑ni=1∑nj=1wijVj+Ii-UiRi·dVidt
=-∑ni=1CidUidt·dVdt=-∑ni=1Ci·dUidt·dVdUi·dUidt

=-∑ni=1Ci·dVidUi·dUidt2
=-∑ni=1Ci·f′(Ui)·dUidt2(536)
其中,Ci为输入电容，Ci>0。由上面章节可知，Vi=f(Ui)为单调递增函数，故其导数大于0，而dUidt2为非负数，因此可得dEdt≤0，即能量函数单调不增。

 5.4Hopfield神经网络的应用
Hopfield神经网络作为一种反馈型神经网络，已经在多个领域取得了成功。Hopfield网络的应用形式有联想记忆和优化计算两种形式，不同形式的Hopfield神经网络对应不同的应用形式： 离散型Hopfield神经网络主要用于联想记忆，连续型Hopfield神经网络主要用于优化计算。接下来分别对离散型Hopfield神经网络和连续型Hopfield网络的应用展开说明。
5.4.1离散型Hopfield神经网络的应用
离散型Hopfield神经网络采用内容寻址存储(Content Addressable Memory, CAM)方式存取信息，使得信息与存储地址不存在一对一的关系，即当只给出输入模式的部分信息时，神经网络能够联想出完整的信息。CAM方式是一种分布式存储方式，因此即使少量且分散的局部信息出错，也可以忽略其对全局信息产生的影响。利用神经网络的这种良好的容错性，能够将不完整的、含噪声的、畸变的信息恢复成完整的原型，通常用于识别和分类等任务。
1. 联想记忆
神经网络虽然具有联想功能，但是不同于人类的联想功能。人类的联想是将一种事物联系到与之相关的事物或者其他事物，而神经网络的联想功能是指网络在给定的一组信号的刺激下能够回忆出与之相对应的信号。记忆是联想的前提，联想记忆的过程就是信息的存取过程。
Hopfield神经网络也常被称为联想记忆网络，可以将其看成是非线性联想记忆或按内容寻址器。Hopfield神经网络模拟了生物神经网络的记忆功能,采用内容寻址存储方式存取信息，根据给定的部分信息，通过不断的学习联想出完整的信息。由于采用了内容寻址存储方式，因此Hopfield神经网络具备了信息存储量大、高速读取、信息检索时间与信息存储量大小无关等特点。
联想记忆可以分为两种： 一种是自联想记忆(autoassociative memory)； 另一种是异联想记忆(heteroassociative memory)。异联想记忆与自联想记忆的不同在于输出信息的形式不同。
自联想记忆： 假定联想记忆网络作为联想存储器在学习过程中存储了m个样本，即{Xk}； k=1,2,3,…,m； k=1,2,3,…,m。X′=Xk+V作为联想记忆网络在联想过程中的输入，其中Xk表示联想记忆网络存储的m个样本中的任意一个样本，V表示偏差项(可代表噪声、缺损与畸变等)，采用自联想记忆方式的联想记忆网络的输出为Xk，即存在对应关系： X′→Xk。
自联想记忆能够将某个事物的不完整的信息恢复成此事物的完整的原型。同时，自联想记忆具有容错性，能够识别含有噪声的信息。比如将一张破损的故宫照片提供给网络，能够获得一张完整的故宫照片。
异联想记忆： 异联想记忆是自联想记忆的特例，假定两组模式对之间存在对应关系： Xk→Yk； k=1,2,…,m，其中m表示网络记忆的样本个数，X′=Xk+V作为联想记忆网络在联想过程中的输入，其中Xk表示联想记忆网络存储的m个样本中的任意一个样本，V表示偏差项(可代表噪声、缺损与畸变等)，采用异联想记忆方式的联想记忆网络的输出为Y′, 其中Y′∈{Yk}。比如将某个地方的破损的照片提供给网络，能得到某个地方的名称。
异联想记忆能够根据某一事物的信息联想出另一事物的信息，即在受到具有一定噪声的输入模式激发时，网络能够通过状态的演化联想出对应的样本模式。
2. 具体应用实例
联想记忆网络的特点决定了它对含噪声的、畸变的、缺损的信息问题有着良好的处理效果，所以联想记忆神经网络有着非常广泛的应用领域，比如模式识别、模式分类、图像处理等。在模式识别领域，可以将联想记忆神经网络用于手势识别、语音识别及人脸识别； 在模式分类领域，可以用于地下工程围岩稳定性分类、遥感影像分类； 在图像处理领域，可以利用联想记忆网络对模糊，残缺图像的记忆和回忆能力，对图像及复杂背景的车牌进行识别、对在运输或者印刷过程中污损的二维码图像进行复原等。
联想记忆网络的去噪能力，在智能交通方面发挥着重要作用，本节以小型汽车的车牌识别为例，重点介绍离散型Hopfield神经网络的构建及使用联想记忆复原车牌字符的过程。
车牌识别流程图如图57所示。




图57车牌识别流程图


首先车牌识别中出现的相关概念如下： 
1) 标准字符模板
标准字符模板的作用是用来匹配分割出来的车牌字符。普通民用车牌主要由汉字、字母以及阿拉伯数字三部分组成。本实例中采用的标准字符模板大小为40×20的图像，包括31个汉字，10个阿拉伯数字(0~9)，以及24个大写英文字母。
2) 车牌定位
车牌定位是车牌识别工作的前提，作用是排除车牌字符信息以外的干扰。
3) 车牌校正
智能交通摄像机在摄取车牌图像时，由于拍摄角度、车速等原因导致采集到的车牌图像存在不同程度的倾斜，很难直接对扭曲的车牌字符进行特征提取，因此在车牌字符分割前对车牌图像进行倾斜校正，目前主要的倾斜校正方法有旋转投影法、Hough变换法等。
4) 车牌字符分割
将车牌字符单个分离出来，有利于网络进行逐个识别，准确识别出车牌号码，针对我国车牌特征，目前常用的车牌字符分割法有： 基于垂直投影的字符分割法等。
5) 存储容量
由先验知识可知，当Hopfield神经网络接受外界输入信号和需要联想匹配的样本过多，网络不能正确联想。研究表明，在一个连续型Hopfield神经网络中，所需记忆样本数量超过神经元总数的15%时，网络的联想记忆就有可能出错。本实例中标准化处理后的样本大小为40×20,因此神经网络的神经元的个数为40×20=800个。网络的存储容量最多为800×15%=120个,因此在设计网络时，记忆样本的个数最好不要超过120个。
结合以上原理，构建Hopfield神经网络记忆标准模板字符，然后利用构造好的网络对受到噪声干扰的字符图像进行去噪，具体实现步骤如下： 
(1) 确定记忆样本，对记忆样本进行编码，以便取得取值为1和-1的记忆样本。将所有待记忆的且经过二值化图像处理的模板字符存储成40×20的二阶矩阵，将二阶矩阵转换为元素个数为800个的一维列向量，元素的取值只有0或1，有内容的部分为1，无字符的位置为0。假设记忆样本个数为m个，将所有转换后的列向量合成一个n×800的二阶矩阵T。将矩阵T中值为0的元素转化为-1,Xk=(xk1,xk2,…,xkn)T； k=1,2,…,m(m<n),其中Xk表示第k个记忆模式，m为记忆模式的个数，且不大于120，神经元j的状态xkj的值为1或-1。
(2) 利用矩阵T设计网络的连接权值，采用Hebb学习规则的外积和法和(串行)异步工作方式构建神经网络模型。
(3) 采用产生噪声的方法(如随机噪声产生法、固定噪声产生法等)对待识别的记忆样本模拟产生带噪声的二阶矩阵，同时将二阶矩阵转化为元素个数为800个的一维列向量。
(4) 初始化网络状态，将步骤(3)获得的含有噪声的列向量X′=(x′1,x′2,…,x′n)T作为输入样本载入网络，xi(0)=x′i(i=1,2,…,n)，xi(t)表示神经元i在t时刻的输出状态。
(5) 随机更新网络中某一个神经元的状态，反复迭代直到网络状态为稳定状态，网络输出去除噪声的车牌字符。
(1)、(2)属于离散型Hopfield神经网络的记忆阶段，(3)~(5)属于联想阶段。
5.4.2连续型Hopfield神经网络的应用
1.  组合优化问题

连续型Hopfield神经网络主要应用于优化计算，换句话说，就是解决组合优化问题。组合优化问题也就是最优解问题，是指在给定的约束条件下，求出使目标函数获得极小值(或极大值)的变量组合问题。
2. 连续型Hopfield神经网络解决组合优化问题
连续型Hopfield神经网络解决组合优化问题利用了网络的能量函数E在网络状态的变化过程中单调递减的原理。把需要优化的问题映射到一种神经网络的特定组合状态上，能量函数E等价于解决优化问题的代价函数，当网络处于稳定状态时，能量函数E收敛于极小值点，此时的网络状态就是优化问题可能出现的解。连续型Hopfield神经网络计算优化问题的步骤如下： 
(1)  选择一种合适的表示方法表示待优化的问题，使得神经网络的输出与待优化问题的解对应； 
(2)  构造能量函数E，使能量函数的最小值点与最优解相对应； 
(3)  将步骤(2)中构造的能量函数E与连续型Hopfield神经网络的能量函数做对比，反向推出神经网络的连接权值和结构； 
(4)  由步骤(3)获得的网络结构所建立的网络的稳定运行状态，就是待优化问题的最优解。
3.  连续型Hopfield神经网络的具体应用举例
旅行商最优路径问题(Traveling Salesman Problem，TSP)是要找出一条最短路线，这条路线经过每个城市恰好一次，并回到出发点。假设有n个城市的集合{Ci}； i=1,2,…,n,任意两个城市Cx与Cy之间的距离用dxy表示，n个城市之间可能的路线有(n-1)!2条。
目前，旅行商问题的解决方法(穷举法、贪心法等)存在“组合爆炸”问题，即当城市数n较大时，冯·诺伊曼体系结构的计算机在有限时间内无法获得答案。直到1984年，Hopfield和Tank使用连续型Hopfield网络成功解决了当n=30时的旅行商问题，为解决组合优化NPhard问题开辟了一条新的途径，展现了神经网络的优越性。其主要解决步骤包括： 将旅行商问题转换成适合神经网络处理的形式，用n×n个神经元构成的矩阵表示旅行路线，然后利用约束条件构造能量函数，确定连接权值，运行网络得到结果。旅行商问题优化计算过程如下： 
第一步： 选择合适的表示方法。
旅行商问题的解是n个城市的有序排列，并且任意城市在任意一条路线上的位置可以用n维向量表示，因此可以使用n阶矩阵V来描述一次有效的旅行路线。矩阵中的元素与网络中的神经元对应，Vxi(x=1,2,…,n； i=1,2,…,n)表示神经元xi的状态，其中，x表示第x个城市Cx； i表示访问的顺序。矩阵中的元素表示某一城市在某一条有效路线中的位置，行向量表示城市Cx(x=1,2,…,n)的位置，列向量表示路线中第i(i=1,2,…,n)个位置上的城市。
Vxi=1,Cx是路线中第i个被访问的城市

0,Cx不是路线中第i个被访问的城市
假如有4个城市C1、C2、C3、C4，一条有效路线为C2→C1→C4→C3→C2，旅行路线总长为d=d21+d14+d43+d32,矩阵表示形式如图58所示。


图584个城市TSP中一次可能的路线


第二步： 构造能量函数。
解决旅行商问题的核心步骤是设计能量函数，首先分析旅行商问题和对应矩阵V的特点，总结如下： 
(1) 一个城市只能被访问一次，即矩阵行向量有且仅有1个元素为1，其余n-1个元素为0。
(2) 一次只能访问一个城市，即矩阵列向量有且仅有1个元素为1，其余n-1个元素为0。
(3) 每个城市都要到过一次，即矩阵V中有n个数值为1的元素。
(4) 旅行路线最短，即网络能量函数的最小值对应旅行商问题的最优解，即访问路线的最短距离。
结合上述特点可知，在连续型Hopfield神经网络能量函数的一般性基础上设计旅行商问题的能量函数时，还需考虑以下两点要求： 
(1) TSP的能量函数需要量化地翻译置换矩阵的规则。
(2) 能量函数要有利于量化表示最短路线的解。
在考虑以上两点要求之后，将TSP的能量函数划分成4部分： 
(1) 设计TSP能量函数的第一项E1。
由特点(1)可知第x行的全部元素按顺序两两相乘之和为0，即∑n-1i=1∑nj=i+1VxiVxj=0，其中位置j表示与i相邻的位置，从而全部n行的所有元素按顺序两两相乘之和也应为0，即∑nx=1∑n-1i=1∑nj=i+1VxiVxj=0，因此由行约束构造的能量函数E1表达式如式(537)所示： 
E1=A2∑nx=1∑n-1i=1∑nj=i+1VxiVxj(537)
其中，A为大于0的常数。显然，当E1=0时可保证对每个城市访问的次数不超过一次。
(2) 设计TSP能量函数的第二项E2。
同理，由特点(2)可知第i列的全部元素按顺序两两相乘之和为0，即∑n-1x=1∑ny=x+1VxiVyi=0，其中y表示与城市x相邻的城市，从而全部n列的所有元素按顺序两两相乘之和也应为0，即∑ni=1∑n-1x=1∑ny=x+1VxiVyi=0，因此由列约束构造的能量函数E2表达式如式(538)所示： 
E2=B2∑ni=1∑n-1x=1∑ny=x+1VxiVyi(538)
其中，B为大于0的常数。显然，当E2=0时可保证每次访问的城市个数不超过一个。
(3) 设计TSP能量函数的第三项E3。
由特点(3)可知矩阵中Vxi=1的数目等于城市数n，即∑nx=1∑ni=1Vxi=n因此由全局约束条件得到能量函数E3的表达式如式(539)所示： 
E3=C2∑nx=1∑ni=1vxi-n2(539)
其中,C为大于0的常数。E3=0可保证总共访问的城市个数为n个，同时平方项也表示了当访问城市总数不为n时的一种惩罚。
(4) 设计TSP能量函数的第四项E4。
同时满足以上约束条件(1)(2)(3)只能保证路线是有效的，并不能保证一定是最优的，即路线总长度不一定最短。因此，在保证路线有效的前提下，在能量函数中加入能反映路线长度的能量分量E4，同时保证E4随路线总长度的缩短而减小。
设计E4时，考虑到访问任意两城市Cx与Cy有以下两种状况。
情况一： 先访问城市Cx，再访问城市Cy，即Cx→Cy，相应的距离表达式为dxyVxiVy,i+1。
情况二： 先访问城市Cy，再访问城市Cx，即Cy→Cx, 相应的距离表达式为dxyVxiVy,i-1。
如果城市Cx和城市Cy在一条路线中相邻，结合上述两种情况可得式(540)。
Cx→Cy： dxyVxiVy,i+1=1，dxyVxiVy,i-1=0

Cy→Cx： dxyVxiVy,i+1=0，dxyVxiVy,i-1=1(540)
因此，可以定义城市Cx和城市Cy之间的距离为式(541)所示。
dxy=dxyVxiVy,i+1+dxyVxiVy,i-1=dxyVxi(Vy,i+1+Vy,i-1)(541)
由路线长度约束条件得到的能量函数E4表达式如式(542)所示。
E4=D2∑nx=1∑ny=1∑ni=1dxyVxi(Vy,i+1+Vy,i-1)(542)
其中，∑nx=1∑ny=1∑ni=1dxyVxi(Vy,i+1Vy,i-1)表示n个城市两两之间所有可能的访问路线的长度，D为大于0的常数。当E4达到最小值时保证当前路线为最短路线。
综合式(537)~式(542)，可得解决旅行商问题的连续型Hopfield神经网络的能量函数E如式(543)所示： 
E=E1+E2+E3+E4

=A2∑nx=1∑n-1i=1∑nj=i+1VxiVxj+B2∑ni=1∑n-1x=1∑ny=x+1VxiVyi+C2∑nx=1∑ni=1vxi-n2+
D2∑nx=1∑ny=1∑ni=1dxyVxi(Vy,i+1+Vy,i-1)(543)
其中,参数A、B、C、D称为权值； E1~E3称为惩罚项，只有在满足约束条件的情况下，TSP能量函数的分量E1~E3才为0，保证了路线的有效性； E4对应组合优化问题的目标函数，其最小值表示最短路线长度，保证了路线的合理性。
针对旅行商问题，网络的能量函数达到极小值的前提是要满足约束条件，也就是说能量函数分量E1~E3均为0是网络的能量函数达到极小值的前提。
第三步： 确定神经元间的连接权值。
设置网络的初始连接权值的目的是使网络能够收敛到全局极小值。对比式(530)与式(543)，可得式(544)。
wxi,yi=-Aδxy(1-δij)-Bδij(1-δxy)-C-Ddxy(δj,i+1+δj,i-1)

θxi=Cn(544)
其中，wxi,yi表示神经元xi与神经元yj的初始连接权值；  θxi表示外部激励(输入电流)，δ函数定义如式(545)所示。
δxy=1，x=y

0，x≠yδij=1，i=j

0，i≠j(545)
运行构造好的网络
Cxiduxidt=-A∑nj=1,j≠iVxi-B∑nj=1,y≠xVyi-C∑nx=1∑ni=1Vxi-n-

D∑ny=1,y≠xdxy(Vy,i+1+Vy,i-1)-uxiRxi
Vxi=f(uxi)=11+e-2uxiu0(546)
给定一个随机的初始值输入，使得构造好的网络按照式(546)运行。式(546)中u0是初始值，输入的初始值不同，得到的网络的稳定状态也不同，即不同的初始输入得到不同的旅行路线，这些路线可能是旅行商问题的最优解或者次优解。
使用连续型Hopfield神经网络解决TSP问题时需要注意以下问题。
(1) 在初始化连续型Hopfield神经网络时，可以将初始值设为任意值。但是初始值会影响程序运行的速度和精确度，因此为了达到更好的效果,要不停地对初始值进行调试。
(2) 由于每次运行程序时，输入状态都是在给定范围内的随机数，因此每次计算得到的次优解数据也会略有不同，但是只要多次运行程序就能发现多次迭代后的最优解只有一个。
(3) 用Hopfield神经网络求解TSP问题是较为有效的，但是很明显，由于很难选择合适的惩罚参数，导致利用Hopfield神经网络求解组合优化问题对缺乏经验的神经网络开发者来说不是一个容易实现的工作，反倒是经典算法中的分治法等方法对初学者更为友好。
(4) Hopfield神经网络虽然可以求解小型TSP，但是对于大规模的TSP求解很难获得较好的效果，因此要像其他大规模组合优化问题一样先分解成子问题再解决。


微课视频


 5.5本章实践
5.5.1离散型Hopfield神经网络实践
离散型Hopfield神经网络的一项重要应用就是联想记忆，它能够将一些样本模式存储在不同的能量极值点上。联想的前提是记忆，首先应该把相应的信息保存起来，才能按照某种方式或规则读取出相关信息。联想记忆分为自联想记忆和异联想记忆，离散型Hopfield属于自联想记忆。
本次实验以记忆数字矩阵为例。
1. 定义要记忆的信息




Vmat1 = np.zeros((5, 5))

Vmat1［2, :］ = 1








Vmat1［:, 2］ = 1

print("V1",Vmat1)

plt.imshow(Vmat1)

plt.title("加")

plt.show()






V1的结果如下。数字矩阵“加”如图59所示。



［［0. 0. 1. 0. 0.］

［0. 0. 1. 0. 0.］

［1. 1. 1. 1. 1.］

［0. 0. 1. 0. 0.］

［0. 0. 1. 0. 0.］］






类似的记忆“乘”“×”，如图510所示。



图59数字矩阵“加”




图510数字矩阵“乘”



2. 定义Hopfield模型





node_nums = 25

Vs = ［Vmat1.reshape(-1), Vmat2.reshape(-1)］#拼接

hopnet = HopfieldNet(node_nums, Vs)







3. 模型训练
对于权值矩阵的获得可以分别采用下面两种方式： 直接计算法和Hebb学习规则。



def init(self, node_nums, Vs):

self.node_nums = node_nums

self.W = np.zeros((node_nums, node_nums))

for i in range(node_nums):

for j in range(node_nums):

if i == j:

self.W［i, j］ = 0

else:

self.W［i, j］ = sum(［(2 * Vs［a］［i］ - 1) * (2 * Vs［a］［j］ - 1) for a in range(len(Vs))］)








def learnW(self, Vs):

for i in range(100):

for j in range(len(Vs)):

for c in range(len(Vs［j］)):

for r in range(len(Vs［j］)):

if c != r:

if Vs［j］［c］ == Vs［j］［r］:

self.W［c, r］ += 0.1

else:

self.W［c, r］ -= 0.1







4. 模型测试
定义测试数据，残缺数据考验Hopfield联想能力。模型测试如图511所示。



testmat = np.zeros((5, 5))

testmat［2, :］ = 0

testmat［:, 2］ = 0

testmat［2, 2］ = 1

testmat［0, 0］ = 1

plt.imshow(testmat)

plt.title("测试")

plt.show()

v = testmat.reshape(-1)








图511模型测试



测试数据reshape后导入Hopfield模型。



def fit(self, v):

new_v = np.zeros(len(v))

print("new",new_v)

indexs = range(len(v))

while np.sum(np.abs(new_v - v)) != 0:

new_v = copy.deepcopy(v)

for i in indexs:

temp = np.dot(v, self.W［:, i］)








if temp = 0:

v［i］ = 1

else:

v［i］ = 0

return v







5. 查看测试结果
测试结果如图512所示。



图512测试结果


可以看出Hopfield神经网络成功地对数据进行了联想，但是这种数据的联想不是稳定的，记忆有一定的记忆容量。并且，权值矩阵会随着记忆模式的引入发生偏移，神经元的记忆顺序与联想顺序也会影响模型结果。综上，程序的流程图如图513所示。


图513离散Hopfield实现记忆数字矩阵程序流程图


5.5.2连续型Hopfield神经网络实践
本实验通过连续型Hopfield神经网络解决TSP问题。
1. 将TSP转化成适合于神经网络处理的形式
鉴于TSP的解是n个城市的有序排列，因此，可以使用一个由n×n个神经元构成的矩阵来描述旅行路线。该矩阵中的每个元素对应神经网络中的每个神经元，神经元的状态可以表示某一城市在某一条有效路线中的位置。例如，神经元xi的状态用Vxi(x=1,2,…,n； i=1,2,…,n)表示，其中x表示第x个城市Cx，i表示Cx是一条有效路线中第i个经过的城市，Vxi=1表示城市Cx在路线中第i个位置出现，Vxi=0表示城市Cx在路线中第i个位置不出现，此时第i个位置上为其他城市。
由此可见，n×n矩阵V可以表示解决n个城市TSP的一次有效的旅行路线，即矩阵V可以唯一地确定对所有城市的访问次序。例如，对于8个城市TSP，一次有效路线构成的矩阵V中的各个元素，如图514所示，其中纵向表示城市名，横向表示每个城市在矩阵V中的访问次序。


图5148个城市TSP中的一次可能路线


由图514可知，这8个城市的访问顺序为C4→C2→C5→C8→C1→C3→C7→C6→C4，旅行路线总长为d=d42+d25+d58+d81+d13+d37+d76+d64。
通过分析TSP的定义以及对应的矩阵V可以发现，置换矩阵负责翻译并遵守TSP的规则： 
(1) 一个城市只能被访问一次，即矩阵每行有且只有一个1，其余元素均0。
(2) 一次只能访问一个城市，即矩阵每列有且只有一个1，其余元素均为0。
(3) 一共要访问n个城市，即矩阵的全部元素中1的数量为n。
在神经网络迭代优化过程中，每次神经元输出的状态集合只要满足上述置换矩阵的规则，则证明该组输出状态就是一个TSP问题的解，只要在这些解中找到最小代价的解即可。其中(1)~(3)反映了路线的有效性。
2. 构造能量函数
要让旅行路线最短，就需要网络能量函数的最小值对应于TSP最短路线的距离。在分析TSP及其对应的矩阵V的特点之后，我们可以发现，构造合适的能量函数是解决TSP的关键步骤。
对于TSP问题，在CHNN能量函数的一般性基础上，需要考虑以下两点： 
(1) TSP的能量函数需要量化地翻译置换矩阵的规则。
(2) 在TSP问题中的n!条合法路线中，能量函数要有利于量化表示最短路线的解。
在考虑上述的要求之后，将TSP的能量函数划分成4部分。
(1) 设计TSP能量函数的第一项，如式(547)所示： 
E1=A2∑nx=1∑n-1i=1∑nj=i+1vxivxj(547)
其中，A为常数，并且A>0。即每一行中的每一个城市x，必须有且只有一个1，符合置换矩阵的第一条规则。
(2) 设计TSP能量函数的第二项，如式(548)所示： 
E2=B2∑ni=1∑n-1x=1∑ny≠xvxivyi(548)
其中，B为常数，并且B>0。即每一列中的每一个城市x，必须有且只有一个1，符合置换矩阵的第二条规则。
(3) 设计TSP能量函数的第三项，如式(549)所示： 
E3=C2∑nx=1∑ni=1vxi-n2(549)
其中,C为常数，并且C>0。即整个矩阵有n个1，符合置换矩阵的第三条规则。
(4) 设计TSP能量函数的第四项，如式(550)所示： 
E4=D2∑nx=1∑ny≠x∑ni=1dxyvxi(vy,i+1+vy,i-1)(550)
其中,D为常数，并且D>0。式(550)包含神经网络输出中有效解的路径长度信息，dxy表示城市x到城市y的距离。
当E4保证当前路线为最短时，E4也达到了最小值。
整合E1、E2、E3、E4后，得到TSP的能量函数E，如式(551)所示： 
E=E1+E2+E3+E4

=A2∑2x=1∑n-1i=1∑nj=i+1vxivxj+B2∑ni=1∑n-1x=1∑ny≠xvxivyi+C2∑nx=1∑ni=1vxi-n2+
D2∑nx=1∑ny≠x∑ni=1dxyvxi(vy,i+1+vy,i-1)
(551)

其中,参数A、B、C、D称为权值，前三项是满足TSP置换矩阵的约束条件，称为惩罚项； 最后一项包含优化目标函数项，即优化要求——使得旅行路线最短。
3. 确定权值连接
为了使网络能够收敛到全局极小值，需要设置网络的初始连接权值。将整合后的TSP能量函数E进行优化，可以得到以下表达式。
(1) 网络的初始连接权值，如式(552)所示： 
wxi,yi=-Aδxy(1-δij)-Bδij(1-δxy)-C-Ddxy(δj,i+1,δj,i-1)(552)
其中,δ函数定义，如式(553)所示： 
δij=1,i=j

0,i≠j (553)
(2) 外部激励(输入电流)，如式(554)所示： 
θxi=Cn(554)
4. 运行网络 
给定一个随机的初始值输入，使得网络按照如式(555)运行。
Cnduxidt=-A∑nj=1,j≠ivxj-B∑nj=1,y≠xvyi-C∑nx=1∑ni=1vxi-n-

D∑ny=1,y≠xdxy(vy,i+1+vy,i-1)-uxiRxi
vxi=f(uxi)=11+e-2uxiu0(555)
得到网络稳定状态，即对应着一条最优的旅行路线。初始值不同也将会得到不同的稳定状态，即得到不同的旅行路线，这些旅行路线不是最优路线，就是次优路线。在图515和图516给出了两个解。




图5158城市TSP最优解






图5168城市TSP次优解


这是程序最后输出的一组哈密顿回路和能量趋势图，左图表示找到的最短距离路线，右图表示在神经网络的优化过程中能量函数的波动。从图515和图516可以看到，初值设置得当时，Hopfield神经网络找到的最优解已经和真实最优解一致。
5. 代码实现过程
1) 初始化Hopfield神经网络的初值(如输入电压U0、迭代次数)和权值(A、D)



# 给定城市位置

citys = np.array(［［2, 6］, ［2, 4］, ［1, 3］, ［4, 6］, ［5, 5］, ［4, 4］, ［6, 4］, ［3, 2］］)

N = len(citys)

# 设置初始值

A = N * N

D = N / 2

U0 = 0.0009# 初始电压

step = 0.0001  # 步长

num_iter = 10000  # 迭代次数






2) 构建n个城市之间的距离矩阵Dxy



# 得到城市之间的距离矩阵  

def get_distance(citys):  

N = len(citys)  

distance = np.zeros((N, N))  

for i, curr_point in enumerate(citys):  

line = ［］  

［line.append(price_cn(curr_point, other_point)) if i != j else line.append(0.0) for j, other_point in enumerate(citys)］  

distance［i］ = line  

return distance



distance = get_distance(citys)






3) 利用CHNN动态方程计算输入状态的增量



# 动态方程计算微分方程du  

def calc_du(V, distance):  

a = np.sum(V, axis=0) - 1# 按列相加  

b = np.sum(V, axis=1) - 1  # 按行相加  

t1 = np.zeros((N, N))  

t2 = np.zeros((N, N))  

for i in range(N):  

for j in range(N):  

t1［i, j］ = a［j］  

for i in range(N):  

for j in range(N):  

t2［j, i］ = b［j］  

# 将第一列移动到最后一列  

c_1 = V［:, 1:N］  

c_0 = np.zeros((N, 1))  

c_0［:, 0］ = V［:, 0］  

c = np.concatenate((c_1, c_0), axis=1)  

c = np.dot(distance, c)  

return -A * (t1 + t2) - D * c 






4) 分别由一阶欧拉方法和Sigmoid函数更新神经网络下个时刻的输入和输出状态



# 更新神经网络的输入电压U

def calc_U(U, du, step):

return U + du * step

# 更新神经网络的输出电压V

def calc_V(U, U0):

return 1 / 2 * (1 + np.tanh(U / U0))






5) 计算当前的能量函数E



def calc_energy(V, distance):

t1 = np.sum(np.power(np.sum(V, axis=0) - 1, 2))

t2 = np.sum(np.power(np.sum(V, axis=1) - 1, 2))

idx = ［i for i in range(1, N)］

idx = idx + ［0］

Vt = V［:, idx］

t3 = distance * Vt

t3 = np.sum(np.sum(np.multiply(V, t3)))

e = 0.5 * (A * (t1 + t2) + D * t3)

return e






6) 检查当前神经网络的输出状态集合，是否满足TSP置换矩阵的规则



# 检查路径的正确性

def check_path(V):








newV = np.zeros(［N, N］)

route = ［］

for i in range(N):

mm = np.max(V［:, i］)

for j in range(N):

if V［j, i］ == mm:

newV［j, i］ = 1

route += ［j］

break

return route, newV






以上3)~6)是在迭代训练优化Hopfield神经网络过程中的主要步骤，具体实现如下。



n=0

# 开始迭代训练网络

while n  num_iter:

# 利用动态方程计算du

du = calc_du(V, distance)

#更新下个时间的输入状态(电路的输入电压U)

U = calc_U(U, du, step)

#更新下个时间的输出状态(电路的输出电压V)

V = calc_V(U, U0)

# 计算当前网络的能量E

energys［n］ = calc_energy(V, distance)

# 检查路径的合法性

route, newV = check_path(V)

if len(np.unique(route)) == N:

route.append(route［0］)

dis = calc_distance(route)

if dis  best_distance:

H_path = ［］

best_distance = dis

best_route = route

［H_path.append((route［i］, route［i + 1］)) for i in range(len(route) - 1)］

print('第{}次迭代找到的次优解距离为： {}，能量为： {}，路径为： '.format(n, best_distance, energys［n］))

［print(chr(97 + v), end=',' if i  len(best_route) - 1 else '＼n') for i, v in enumerate(best_route)］

n = n + 1






根据给定的初值，Hopfield神经网络在经过10000次迭代优化后，找到的TSP的最优路线解如图517所示。


图517Hopfield神经网络找到的TSP路线


综上，该程序实现的具体流程如图518所示。



图518连续型Hopfield神经网络解决TSP问题的流程图


 5.6习题
1. 如何判断离散型Hopfield神经网络是否达到稳定状态？
2. 设计离散型Hopfield神经网络，并考察其联想性能。
X=T=1-11
1-1-1
-111
3. 试分析自联想记忆与互联想记忆的异同，并设计一个简单的联想记忆存储器。
4. 为什么连续型Hopfield神经网络能解决组合优化问题？
5. 为什么离散型Hopfield神经网络具有联想记忆功能？
6. 离散型Hopfield神经网络的训练过程主要为哪几个步骤？
7. 连续型Hopfield神经网络解决优化问题的一般步骤。
8. 解决TSP问题的算法有： 神经网络算法、、、等。
9. 请实现离散型Hopfield神经网络的联想记忆功能。