Petri网系统的可达性研究
§4.2 Hopfield网络模型
1985年，霍普菲尔德(J. J. Hopfield)和塔克(D. W. Tank)[18]建立相互连接型神经网络模型，并且用它成功地讨论了具有NP完全复杂性的旅行商(TSP)问题的求解方法。在Hopfield网络模型中，每一个神经元都和所有其它神经元相连接，所以又称为全互联网络。研究表明，当连接权矩阵无自连接以及具有对称性质即：
Wi,i?0 i=1,2,…,N 和Wi,j?Wi,j i, j=1,2,…,N 时，算法是收敛的。
Hopfield网络可分为离散型和连续型： 1． 离散型Hopfield网络
Hopfield最早提出的网络是二值神经网络，神经元的输出只取1和0这两个值，所以，也称离散Hopfield神经网络。在离散HopfieId网络中，所采用的神经元是二值神经元；故而，所输出的离散值1和0分别表示神经元处于激活和抑制状态。
首先考虑由三个神经元组成的离散Hopfield神经网络，其结构如图2中所示。在图中，第0层仅仅是作为网络的输人，它不是实际神经元，所以无计算功能；而第一层是实际神经元，故而执行对输人信息和权系数乘积求累加和，并由非线性函数f处理后产生输出信息。f是一个简单的阈值函效(阶跃函数)，如果神经元的输出信息大于阈值θ，那么，神经元的输出就取值为1；小于阈值θ，则神经元的输出就取值为θ。其中：Xi为外部输入。
对于一个离散的Hopfield网络，其网络状态是输出神经元信息的集合。对于一个输出层是n个神经元的网络，则其t时刻的状态为一个n维向量：Y(t)=[Y1(t),Y2(t),...,Yn(t)]T，故而，网络状态有2n个状态；因为Yj(t)(j＝1??n)可以取值为1或0；故n维向量Y(t)有2n种状态，即有2n种网络状态。
对于一个由n个神经元组成的离散Hopfield网络，则有n×n权系数矩阵w：
W??Wij?
i=1,2,...,n j=1,2,...,n ，同时，有n维阈值向量θ：θ=[θ1,θ2,...θn]T
一船而言，w和θ可以确定一个唯一的离散Hopfield网络。
图2 三神经元组成的Hopfield网络
26
第四章 可达性的神经网络解法
考虑离散Hopfield网络的一个节点状态；用Yj(t)表示第j个神经元，即节点j在时刻t的状态，则节点的下一个时刻(t+1)的状态可以求出如下：
?1Yj(t?1)?f?Uj(t)????0,U,Ujj?0?0 ，其中 Uj(t)?n?Wi?1ijYi(t)?Xj??j
当Wij在i＝j时等于0，则说明一个神经元的输出并不会反馈到它自己的输入；这时，离教的HopfieId网络称为无自反馈网络。
当Wij在i＝j时不等于0，则说明—个神经元的输出会反馈到它自己的输入；这时，离散的Hopfield网络称为有自反馈的网络。
离散Hopfield网络有二种不同的工作方式： 1．串行(异步)方式
在时刻t时，只有某一个神经元j的状态产生变化，而其它n-1个神经元的状态
?n不变这时称串行工作方式。并且有Yj(t?1)?f??WijYi(t)?X?i?1j???j?
?Yi(t+1)=Yj(t) i≠j。
?n?在不考虑外部输人时，则有Yj(t?1)?f??WijYi(t)??j??i?1?
2．并行(同步)方式
在任一时刻t，所有的神经元的状态都产生了变化；则称并行工作方式。并且有
?nYj(t?1)?f??WijYi(t)?X?i?1j???j? j?1,2,?,n?
?n?在不考虑外部输入时，则有Yj(t?1)?f??WijYi(t)??j??i?1? j?1,2,?,n
对于一个网络来说，稳定性是一个重大的性能指标。对于离散Hopfield网络，
其状态为Y(t)：Y(t)=[Y1(t),Y2(t),...,Yn(t)]T如果，对于任何△t>0．当神经网络从t＝0开始，有初始状态Y(0)；经过有限时刻t，有：Y(t+△t)=Y(t) 则称网络是稳定的。在串行方式下的稳定性称之为串行稳定性。同理，在并行方式的稳定性称之为并行稳定性。在神经网络稳定时，其状态称稳定状态。从离散的Hopfield网络可以看出：它是一种多输入，含有阈值的二值非线性动力系统。在动力系统中，平衡稳定状态可以理解为系统的某种形式的能量函数在系统运动过程中，其能量值不断减小，最后处于最小值。
对Hopfield网络引入一个Lyapunov函数，即所谓能量函数：
E?(?12)?i?WjijYiYj??XjjYj???jjYj (4)
27
Petri网系统的可达性研究
对于神经元j，其能量函数可表示为 Ej?(?)?WijYiYj?XjYj??jYj
2i1即有：E??E?E。神经元j的能量变化量：△Ej＝
jj?1YjYi?Yj??Yj??(?)?(WijYi?WijYj)?X?Yj?Yj2?Y?Yi?jj??EjjYj???j??Yj ?Yj?Yj??Yj如果存在条件 Wii=0,i=1,2,...,n；Wij=Wji i=1,2,...,n j=1,2,...,n 则有：
?△Ej＝????WijYi?Xij?n???j??Yj????WijYi?X??i?1,i?jj???j??Yj
?如果，令Uj=ΣWijYi+Xj，则△Ej可表示为：
考虑如下两种情况：
1．如果Uj≥θj，即神经元j的输入结果的值大于阈值，则Uj-θj≥0，则从二值神经元的计算公式知道：Yj的值保持为1，或者从0变到1。这说明Yj的变化△Yj只能是0或正值。这时很明显有△Ej≤0；
2．如果Uj≤θj，即神经元j的输入结果的值小于阈值，则Uj-θj≥0，则从二值神经元的计算公式可知：Yj的值保持为0，或者从1变到0。这说明Yj的变化△Yj只能是零或负。这时则有△Ej≤0；
这说明Hopfield网络神经元的能量总是减少。
上面两点说明了Hopfield网络在权系数矩阵W的对角线元素为0，而且W矩阵元素对称时，Hopfield网络是稳定的。应该指出：这只是Hopfield网络稳定的充分条件．而不是必要条件。在实际中有很多稳定的Hopfield网络，但是它们并不满足权系数矩阵w是对称矩阵这一条件。
2. 连续状态Hopfield神经网络
连续Hopfield网络的拓朴结构和离散Hopfield网络的结构相同。这种拓朴结构和生物的神经系统中大量存在的神经反馈回路是相一致的。在连续Hopfield网络中，和离散Hopfield网络一样，其稳定条件也要求Wij=Wji。连续Hopfield网络和离散Hopfield网络不同的地方在于其函数g不是阶跃函数，而是S形的连续函数。一般取 g(u)=1/(1+e-u)
连续Hopfield网络在时间上是连续的．所以，网络中各神经元是处于同步方式工作的。考虑对于一个神经细胞，即神经元j，其内部膜电位状态用uj表示．细胞膜输入电容为Cj，细胞膜的传递电阻为Rj，输出电压为Vj，外部输入电流用Ij表示，则连续Hopfield网络可用图4所示的电路表示。
ndUj(t)Uj(t)???WijVj(t)??I?CjdtRi?1j??V(t)?g(U(t))j?1,2,?,nj?jj
其中： n是神经网络神经元的个数
28
第四章 可达性的神经网络解法
vj(t)为输出电位； Uj(t)为输入电位。
图4 连续Hopfield网络的电路形式
对于连续Hopfield网络，Hopfield给出如下稳定性定理： 给出能量函数E(t),
E(t)?(?12)?i?WjijVi(t)Vj(t)??Vjj(t)Ij??j1Rj?Vj(t)0g?1(V)dV
其中：g-1(v)是Vj(t)＝gj(uj(t))的反函数。
如果连续Hopfield网络中神经元传递函数是单调增长的连续并有界函数，并且Wij＝Wji，则有
dE(t)dt?0； 当并且仅当
dVi(t)dt?0时有
dE(t)dt?0。
这个定理的意义可以解释如下：当网络神经元的传递函数是S函数，并且网络权系数矩阵对称；则随时间的变化网络的能量会下降或不变；而且仅当输出电位随时间变化不变时．网络的能量才会不变。换而言之，在上述条件下的网络是能量不变或下降的。这个定理的证明过程请见相关资料。
最后，有如下结论： 当Hopfield网络的神经元传递函数g是连续且有界的，例如Sigmoid函数，并且网络的权系数矩阵对称，则这个连续Hopfield网络是稳定的。在实际应用中，任何一个系统，如果其优化问题可以用能量函数E(t)作为目标函数，那么，总可以用连续Hopfield网络对其进行求解。由于引入能量函数E(t)，Hopfield使神经网络和问题优化直接对应；这种工作是具开拓性的。利用神经网络进行优化计算，就是在神经网络这一动力系统给出初始的估计点，即初始条件；然后随网络的运动传递而找到相应极小点。这样，大量的优化问题都可以用连续的Hopfield网来求解[20]。这也是Hopfield网络用于神经计算的基本原因。
应该说明一点，Hopfield神经网络的能量函数是朝着梯度减小的方向变化，所以它仍然存在一个问题，那就是一旦能量函数陷入到局部极小值，它将不能自动跳出局部极小点，到达全局最小点，因而无法求得网络最优解。这可以通过模拟退火算法或遗传算法等随机化算法得以解决，在此不再一一介绍，相关资料请见[30]。
29
Petri网系统的可达性研究
§4.3 能量优化模型的神经网络解法
一．建立Hopfield神经网络模型
下面我们将利用Hopfield网络来解能量优化模型，关键在于建立能量优化模型中的能量函数与Hopfield网络中的能量函数的对应关系，变迁变量与神经元的对应关系。根据第三章第三节的符号约定，对于P/T网系统，∑=(S,T；F, K,W, M0)当 K=1 时 能量优化模型：
?a1,1??a2,1令平移变换集：TS＝?f1,f2,?ft?＝????a?s,1nsa1,2a2,2as,2???a1,t??a2,t?? ?as,t??Min E=????[(?j??i)??j??i]
2i?1j?1 ci?ei?V0 , bi?ei?Vn?ci，?i?ei?TS,?i?(2?ci?1)?i 为已知量 S.t. 1. ?i?TTT??，?i??0,e1,e2,?,et?，0表示0向量，e表示标准单位向
kiik?1量，ei＝(0,?,0,1,0?0) 第i个分量为1,其它的为0。
?x1,1??x2,1TC???1,?2,?,?n??????x?t,1x1,2x2,2?xt,2????x1,n??x2,n?为未知变量, xi,j=0或1. ???xt,n??2. Vn=V0＋TS??n
nnn?1i?1,k3．当有位置是某个变迁的输入和输出时， ?xi,k?k?1?xk?1??xk?1i,k?xi?1,k?1。
我们用t×n个神经元来表示变迁选择矩阵TC中的各个未知变量并要满足以
上三条约束，下面我们利用罚函数的思想我们构造出神经网络计算的能量函数。
?j??i?ej?TS??i?(aj1,aj2,?,ajt)?(x11???x1i,x21???x2i,?,xt1???xti)
= aj1(x11???x1i)?aj2(x21???x2i)???ajt(xt1???xti)
?j??i?(2?cj?1)?j??i?(2?cj?1)(aj1(x11???x1i)?aj2(x21???x2i)???ajt(xt1???xti))
对应的神经网络能量函数：
30