第三章 能量优化模型
二．罚函数(能量映射函数)的确定
弱可达性仅是判断可达性的一个必要条件，其区别在于没有对越界作处理， 我们找到一个没有出现越界的变迁过程。所以一旦出现“出界”就对能量函数加上一个足够大的惩罚，这样只要存在一个解使得总能量充分小就能说明该解满足约束条件。
定义3-4 能量阈值：规定一个能量值，当解使得总能量小于该值是能保证该解满足约束条件。
我们知道整个变换过程的状态点的每一个分量x 都必须满足0≦x≦K，所以对应的能量映射函数f(x)必须满足以下性质： 1) 当0≦x≦K，x为整数， f(x)?? 2) 当x≦0，或x≧K, x为整数，f(x)????0
其中：?,?是正常数，并且?足够小，?足够大，即满足 ?×s×m
并且?×s×m +?
每一次变迁的状态点有s个分量，而变迁步骤必小于变迁步骤数的上界，
这样整个过程一旦有一个分量一次越界，总能量都足够大而超过阈值；只有当整个过程中都没有一个分量一次越界，总能量才会小于阈值。所以很明显有下面的定理。
定理 3-1: 对于P/T网系统，∑=(S,T；F, K,W, M0)，从M1可变迁到M2? E
三．总能量表达式 为了表达式的前后统一，我们做以下约定：
s 表示该Petri网的位置的数量； t 表示Petri网的变迁的数量；
m 表示状态间距离上界(变迁步骤数的上界)； ? 表示能量阈值；
Ei 表示第i步的能量(所有分量对应的能量和)； E 表示变迁过程的总能量(每一步状态的能量和) TS 平移变换集 TC 变迁选择矩阵
为了简化计算过程，便于说明思想，我们先假设K=1，取 f(x)???x?(x?1)
对于P/T网系统，∑=（S,T；F, K,W, M0），σ=M0tp1M1tp2…tpnMn是∑的一个有限实施序列，对应的变迁矩阵：TM=[V0 ,V1,?, Vn]，fi表示变迁ti对应的平移变换，其中V1=V0＋fp1，V2=V1＋fp2 ，?，Vn=V0＋?f1,f2,?ft???k1,k2,?kt?T
21
Petri网系统的可达性研究
?a1,1??a2,1令平移变换集TS＝?f1,f2,?ft?＝????a?s,1a1,2a2,2as,2???a1,t??a2,t??，用向量?i表示第i步?as,t??实施的变迁 fpi =TS??i，?i??e1T,e2T,?,etT?，ei＝(0,?,0,1,0,?，0)，表示第i个分量为零的单位向量，对应的变迁选择矩阵：TC???1,?2,?,?n?。
i令?i???, ckk?1i?ei?V0 (初状态位置
i的token数，0或1)，
?i?ei?TS；?i?(2?ci?1)?i (2?ci?1 = －1或1)；
所以：V1=V0＋f1＝V0＋TS??1，V2= V0＋f1＋f2＝V0＋TS??1＋TS??2，
inVi = V0＋TS??k＝V0＋TS??i , Vn = V0＋TS??k= V0＋TS??n .
k?1k?1总能量表达式：
nnsnsE=?Ei=?i?1?j?1f(ej?Vi)＝???i?1?ej?1j?Vi(ej?Vi?1)=
i?1ns???i?1n?ej?1sj?(V0?TS??i)(ej?(V0?TS??i)?1)????i?1n?[cj?2cj?j??i?(?j??i)?cj??j??i]?
j?1s22???i?1n?[2c?jj?1sj??i?(?j??i)??j??i]=
2????[(?j??i)??j??i].
2i?1j?1对于P/T网系统，∑=(S,T；F, K,W, M0), 当K=1时能量优化模型：
nsMin E=????[(?j??i)??j??i] (3)
2i?1j?1 ci?ei?V0，?i?ei?TS,?i?(2?ci?1)?i 为已知量 S.t. 1. ?i?
TTT??，?i??0,e1,e2,?,et?，为未知变量，0表示0向量。
kk?1i22
第三章 能量优化模型
2. Vn?V0?TS??n
注： 1．n的取值有一定的不确定性，minD≦n≦m，在检验弱可达性时虽计算出minD， n取minD时不可达，并不能说明其他情况不可达。通常可取较大的n，多余的步数，?i就取0向量。
2．当有位置是同时某个变迁的输入和输出时，一个变迁对应于两个连续平移变换，比如ti对应的变迁为fi-，fi+ (在变迁矩阵中，对应于第i个和第i＋1个列向量)；
?x1,1??x2,1 令变迁选择矩阵：TC???1,?2,?,?n??????x?t,1x1,2x2,2?xt,2????x1,n??x2,n?，假设第j步发生???xt,n??fi- 则第j＋1步发生fi+ ，则xi,j?1,nnxi?1,j?1?1
n?1i?1,k；
?xi?1,k?1其连续性可用下面条件约束：?xi,k?k?1?xk?1??xk?1i,k, 第一项为fi- 发生
的次数，第二项为fi+发生的次数，第三项为fi- fi+同时为1的次数。可以证明，
n?1n当第j步发生fi- 必有第j＋1步发生fi+，否则有?xi,k?xi?1,k?1?k?1?xk?1i,k；
所以当有位置是同时某个变迁的输入和输出时，只需在能量优化模型的约束条件
nni,kn?1i?1,k中加上:
?xk?1??xk?1??xk?1i,k?xi?1,k?1。
四．计算的复杂性
该能量优化模型其实是一个0－1二次规划，也是一个组合优化问题，变量数目为：t?n个，t为Petri网系统的总变迁个数，n为变迁步骤数。如果用穷举法则搜索空间为2t?n，与其他组合优化问题一样具有很高的计算的复杂度。 所以为了求解该模型，我们必须找到一个行之有效的计算方案。1985年，霍普菲尔德(J. J. Hopfield)和塔克(D. W. Tank) 建立相互连接型神经网络模型，并且用它成功地讨论了具有NP完全复杂性的旅行商(TSP)问题的求解方法。这给了我们启示：如果能将该问题转化为Hopfield神经计算模型，就可以用基于硬件的大规模并行的神经计算代替了基于软件的串行的数字计算。这就是我们利用神经网络来处理可达性问题的出发点。
23
Petri网系统的可达性研究
第四章 可达性的神经网络解法
§4.1 神经网络介绍[15]
神经网络的研究已在国内外广泛兴起，成为政府、科研机构、生产和开发厂家十分重视的课题，各国都投入了大量的人力、物从事有关神经网络应用、理论、模型和实现等方面的研究。人工神经网络（简称神经网络——NN）是由人工神经元（简称神经元）互连组成的网络，它是从微观结构和功能上对人脑的抽象、简化，是模拟人类智能的一条重要途径， 反映了人脑功能的若干基本特征，如，并行信息处理、学习、联想、模式分类、记忆等[35]。
一．大脑模型
根据一个简化的统计，脑是一个由大约1011个神经元构成的复杂的网络，每一个神经元通过约1000个突触与它周围的神经元发生互连作用，总共有1014个互联通道。通过这种连结方式，神经可以收发不同数量的能量。神经的一个非常重要的功能是它们对能量的接受并不是立即作出响应，而是将它们累加起来，当这个累加的总和达到某个临界阈值时，它们将它们自己的那部分能量发送给其它的神经。大脑通过调节这些连结的数目和强度进行学习。尽管这是个生物行为的简化描述。但同样可以充分有力地被看作是神经网络的模型。我们从大脑模型抽象出决定网络整体性能的三大要素为：
(1) 神经元（信息处理单元）的特性；
(2) 神经元之间相互联接的形式——拓扑结构； (3) 为适应环境而改善性能的学习规则。
二．阈值逻辑单元（Threshold Logic Unit，TLU）
理解神经网络的第一步是从对抽象生物神经开始，并把重点放在阈值逻辑单元（TLU）这一特征上。一个 TLU 是一个对象，它可以输入一组加权系数的量，对它们进行求和，如果这个和达到或者超过了某个阈值，输出一个量。让我们用符号标注这些功能，首先，有输入值以及它们的权系数：X1,X2,?Xn和
W1,W2,?Wn。接着是求和计算出的 XiWi，产生了激发层 a，换一种方法表示：
a?(X1?W1)?(X2?W2)???(XnWn)
阈值称为 theta。最后，输出结果 y可以由一个阶跃函数决定当 a >=theta 时
y=1，反之 y=0。请注意输出可以是连续的，因为它也可以由一个 squash 函数 s（或 sigma）决定，该函数的自变量是 a，函数值在 0 和 1 之间，y=s(a)。 （见图一）
24
第四章 可达性的神经网络解法
图 1. 阈值逻辑单元，带有 sigma 函数（顶部）和阶跃函数（底部）
三．神经网络的应用及其特点
神经网络有着很广泛的应用领域，能很好地解决这些领域中面临的诸多问题。比如：在自动控制领域，对被控系统进行辩识并修正参数的方法只能较好地应用于线性系统或一类可线性化的简单非线性系统，很难推广到复杂的非线性系统，人们只好在此基础上作大量的近似或简化，这就难免失去应有的准确性。
在信号处理（包括模式识别和智能控制）领域中的应用引人注目。在信号处理中，无论是信号的获取、传输，还是识别、变换、存储、分类、建模与显示，所采用的技术、手段、理论、方法和系统都是与数字电子计算机的原理、结构和发展紧密相关的，由于这种计算机固有的程序式数字化串行处理方式以及局域式地址存储特征所受到的限制，使得在信号处理许多领域内的研究陷入了困境。
特别是在信号处理的重要领域信号的检测、估计与滤波中，所谓的最优处理与其需要的运算量之间的矛盾在快速变化的环境中几乎达到了不可调和的程度，也就是说，要达到最优处理性能，则完成运算量所需要的计算机数目常常大得不能接受。如果要针对线性处理的许多不足而采用非线性处理，则所需的系统更是复杂庞大，这不得不使人们以牺牲处理性能为代价来换取算法运算量的减少和成本的降低。我们现在遇到的问题就如同在其他领域遇到的问题一样，要达到最优处理性能，需要完成的运算量常常大得不能接受。
为此，人们期待着一种新的理论和技术的诞生。神经网络研究的兴起正是在这样的大气侯下出现的。神经网络是由大量处理单元广泛互连而成的网络，它是在现代神经生物学和认知科学对人类信息处理研究成果的基础上提出来的。在信号、信息处理机制上，它与传统的数字计算机有着根本的不同，它具有大规模并行模拟处理、连续时间动力学和网络全局等特点，信息的存储体现在神经元之间连接的分布上，存储区和操作区合二为一。神经网络具有很强的自适应和学习能力、鲁棒性和容错能力，从而可以代替复杂耗时的传统算法，使信号处理过程更接近于人类思维活动。利用神经网络的高度并行运算能力，可以实时实现难以用数字计算和技术实现的最优信号处理算法。神经网络不仅是信号处理的工具，而且还是一种新的方法论。我们选择神经网络来完成能量优化模型的求解，正是因为只有这种新的方法才适合这种大规模的求解。
25