Petri网系统的可达性研究

分类号 密级 UDC 编号

中国科学院研究生院

硕士学位论文

Petri网系统的可达性研究

吴 文 渊

指导教师 杨 路 研究员

中国科学院成都计算机应用研究所

申请学位级别 硕 士 学科专业名称 计算机软件及理论 论文提交日期 论文答辩日期

培养单位 中国科学院成都计算机应用研究所 学位授予单位 中国科学院研究生院

答辩委员会主席

摘 要..........................................................................................................................II ABSTRACT ............................................................................................................. IV 前 言........................................................................................................................ VI 第一章

背景知识 ................................................................................................ 1

§1.1 历史与发展.................................................................................................. 1 §1.2 研究方法及应用.......................................................................................... 1 §1.3 Petri网的直观理解 ..................................................................................... 2 §1.4 Petri网的形式化描述 ................................................................................. 2

第二章 Petri网与代数系统的关系............................................................... 6

§2.1 Petri网模型映射到代数系统 ..................................................................... 6 §2.2 基于Grobner基的Petri网系统性质分析................................................. 8 §2.3 Maple符号计算软件介绍[14].................................................................. 12 §2.4 计算代数方法的局限性............................................................................ 14

第三章 能量优化模型 ....................................................................................... 15

§3.1 Petri网系统映射到线性空间 ................................................................... 15 §3.2 弱可达性及其分析.................................................................................... 17 §3.3 能量优化模型建立和分析........................................................................ 20

第四章 可达性的神经网络解法 .................................................................... 24

§4.1 神经网络介绍[15] ..................................................................................... 24 §4.2 Hopfield网络模型 .................................................................................... 26 §4.3 能量优化模型的神经网络解法................................................................ 30 §4.4 算法的实现................................................................................................ 32

第五章 综合分析方法 ....................................................................................... 34

§5.1 几种方法的综合比较................................................................................ 34 §5.2 综合分析方法描述.................................................................................... 34 §5.3 综合分析方法总结.................................................................................... 36

第六章 应用实例分析 ....................................................................................... 38 结尾 问题与展望 ................................................................................................ 48

致 谢....................................................................................................................... 49 附 录....................................................................................................................... 50

I

Petri网系统的可达性研究

作者：吴文渊 专业方向：计算机软件及理论 导师：杨路研究员

摘 要

本文对Petri网系统的可达性问题做了综合性的阐述和分析， 提出了利用能量优化方法来解决可达性问题，并在此基础上结合计算代数方法和神经计算模型对可达性问题做了进一步的研究。作者的主要工作在以下四个方面：1. 给出了Petri网到线性空间的映射规则及其可达性的等价性定理；2. 建立了能量优化模型, 将可达性判断化为优化问题；3. 用神经网络来求解能量优化模型；4. 最后综合了计算代数方法和能量优化模型的优点给出一个基于计算代数和神经计算的方法。本文的特点就在于提出了一种利用基于硬件的大规模并行的神经计算来代替基于软件的串行的数字计算的可达性判断解决方案。

在前言中，着重阐述了可达性问题的研究意义，主要困难和目前使用的五类研究方法，在做了简单的评价后，引出我们的研究目的和研究成果。在第一章，简要回顾了Petri网模型的背景知识和研究的历史与发展状况，研究方法和应用范围等背景知识。之后，又介绍了Petri网模型以及相关知识，将该领域的知识框架做了大体说明。

在第二章，主要介绍了计算代数方法。先描述了将Petri网模型映射到代数系统的基本思想，Petri网模型的行为特征对应的代数表示，将可达性问题归结为代数问题。接着讲解了必要的计算代数方面的基础知识，主要讲解了计算代数方法的核心工具－Grobner基，以及计算Grobner基的著名数学软件Maple的使用方法和Grobner基软件包。最后，分析了计算代数方法的局限性。

从第三章开始大部分是作者的工作，在第三章中主要给出了利用能量优化模型及其可达性的等价性定理来解决可达性问题。先说明了该方法思想的出发点和形成过程，之后在该模型下自然诱导出弱可达性概念及其性质。提出利用整数规划方法来处理弱可达性条件，并介绍了相关的数学软件。最后描述了能量优化模型建立的过程和方法。

第四章是针对第三章的能量优化模型提出神经网络的模型计算方案。首先，叙述了神经网络的基础知识，神经计算的特点和应用。之后介绍了神经网络的一种全连接模型－Hopield神经网络，及Hopield网络在能量优化模型的应用。接着对Hopield网络求解能量优化模型的能量函数和相关参数做了计算和分析。最后对神经计算的软件硬件实现做了简单的说明。

II

第五章总结了前几章叙述的各类方法，对其优缺点进行分析比较后提出了综合分析方法，给出了综合分析方法的算法流程。在第六章，以停等协议的Petri网模型为例利用综合分析方法对可达性问题做了分析。最后，本文结尾对Petri网模型的可达性研究的存在问题和将来需要做的工作做了简要阐述和展望。

在附录中给出了用Matlab编写的利用Hopield网络求解能量优化模型的算法程序。

关键词：Petri网模型；可达性；Grobner基；能量优化模型；Hopield神经网络；

弱可达性；综合分析方法；

III

Reachability Analysis Of Petri Net

Author: Wu Wen-Yuan Advisor: Yang Lu (Research Scientist)

ABSTRACT

This work makes a general introduction for the reachability analysis of Petri net and presents the energy optimization model. Furthermore, the structures and behaviors of the Petri net are described by using linear space and polynomial ring. Highly concurrent system suffers from the state explosion problem produced by an exponential increase of the number of reachable states. The state explosion can be handled by using a hybrid method, which is based on Grobner Basis and the energy optimization model.

In the preface of this paper gives a concise statement of the reachability analysis of Petri net and introduces the most general methods, which are using in the field at present.

In the first chapter, the background of Petri net, such as the research history, development, research approach and its application fields, is elucidated. Afterward, this paper illustrates Petri net model, related knowledge, the importance of reachability analysis and the bottleneck of the problem.

Computer algebra method is the main content in the second chapter. Firstly, the paper depicts the fundamental ideal, how the Petri net model is mapped to algebra system, then gives out the relevant algebra expressions for behaviors of the Petri net. Sequentially, essential knowledge about computer algebra, Grobner basis, the key tool of reachability, and Maple, the most famous mathematics software, are introduced. Moreover, the paper emphasizes on the limits of computer algebra method.

From the third chapter, a new way to resolve reachability is coming out from matrix-equation method and the idea of penalty function, and naturally the concept of weak reachable condition is derived from this model. Using integer programming to solve weak reachable condition and building energy optimization model are the main content of this chapter.

In the fourth chapter, we propose to use neural network to calculate the result of the model. Consequently, many concepts and properties about neural network are discussed, especially the Hopfield network. This paper gives out the total energy

IV

function and parameters of the model. Afterwards, implementation of neural network by software and hardware tools is mentioned.

In the fifth and sixth chapters, we present a hybrid method by combining computer algebra method and energy optimization method, which are introduced in previous chapters. A representative example is presented in order to show how the energy optimization model is generated, described and calculated by using relevant software, and how the hybrid method is applied to reachability test.

Finally, the promises and problems of the approach are illustrated. By using the energy optimization framework, properties requiring an exhaustive analysis need an advanced research.

Key Words: Petri net, Reachability, Grobner basis, Energy optimization model,

Hopfield network, Weak reachable condition, Hybrid method

V

前 言

自从1962年Carl Adam Petri 在他的博士论文[1]中提出Petri网模型以来，该

模型就成为理论计算机科学包括自动机模型和形式语言理论的一个分支。在分析并行系统的状态行为的技术中，Petri网模型具有自然，直观，简单易懂等特点。它是一种形式化模型描述方法，在并行模型分析，协议的验证，自动控制等方面有广泛的应用。可达性分析是系统的状态，行为分析的基础。可达性就是研究系统可能达到的状态和状态间的关系，而连接状态和状态的纽带就是变迁。可达性也是研究系统最基本的行为，其他行为特征比如：可逆性、有界性、活性、可覆盖性、公平性等，都可归结为可达性的研究。但是，随着系统规模的扩大，状态空间的组合爆炸使可达性分析非常困难。利用Petri网模型进行系统分析的复杂度呈指数倍提高，明显阻碍了该方法在实时系统中的应用。各种相关的处理方法被提出，但各有优缺点。

可达性的研究最基本方法就是穷举法，构造可达树，遍历所有的过程和状态，是最彻底也是最低效的方法,该方法对于规模较小的问题是有效的，但对于复杂的系统该方法就无能为力了。因为可达性的研究面临的主要困难就是组合爆炸，当问题规模变大，可能的状态数呈几何级数增加，解决问题所需的时间空间也呈几何级数增加。这就阻碍了实时并行系统的分析。

目前提出的解决方法主要还有以下几种：转化为代数问题再利用Grobner基作判断的方法[2](在第二章我们将着重介绍计算代数的方法)；转化为矩阵计算问题利用不变量求解线性方程的方法(与第三章介绍的能量优化方法的出发点一致)；通过进程代数将问题分而治之的方法[3]；还有基于布尔函数计算和二叉决策图压缩状态空间的方法[4]。下面先介绍一下后两种方法。

基于进程代数的分而治之的分析方法：

组合爆炸可以通过利用分而治之的方法来加以控制，一般称为组合分析方法(compositional analysis technique)。主要思想是分析一个大系统的各个部分，再将各个部分按层次合成起来。传统的可达性分析方法不能将系统分解，而进程代数和进程计算方法可将一个大系统分解为等价的子系统。

进程代数是关于通信并发系统的代数理论的统称。20世纪70年代后期，英国学者R.Milner和C.A.R.Hoare分别提出了通信系统演算CCS[5]和通信顺序进程TCSP[6]，开创了用代数方法研究通信并发系统的先河。之后Bergestra和Klop提出的 ACP[7]，ED Brinksma 提出的LOTOS[8]等等，这些代数理论都使用通信，而不是共享存储，作为进程间相互作用的基本手段，表现出面向分布式系统的特征。在语法上，进程代数用一组算子作为进程的构件。算子的语义通常用结

VI

构化操作语义方法定义，这样进程就可以看成是带标号的变迁系统。进程代数的一个显著特征是把并发性归结为非确定性，将并发执行的进程行为看成是各单个进程行为的所有可能的交错合成。进程代数研究的核心问题是进程的等价性，即在什么意义下两个进程的行为相同。但问题在于，在分解时可能将一个大系统分为子系统的同时，产生过多的进程图和进程图节点[3]。

基于布尔函数计算和二叉决策图压缩状态空间的方法：

主要思想是用布尔函数来表示Petri网的结构和行为，将Petri网的变迁转化为布尔函数的计算。Petri网转化为布尔代数是很自然的，PN=(T,S;F,K,W,M0)，假定K=1, 令MT=2T，就可以表示Petri网系统所有的状态空间，而可达标识集必是MT的一个子集。Bn=(2M,∪,∩,?，MT)，映射函数 ?：MT?Bn

T?1，如果pi?M ?M?MT ?i，pi??0，如果p?Mi?可达状态空间由该集合的特征函数来表示，只要是属于可达状态空间的点，通过特征函数计算，输出为1，反之亦然。所以无论状态空间的大小，一个特征函数与可达标识集是一一对应的。特征函数：??：Bn?B?1，如果p??的一个子集。?p?B p??

0，如果p???n??2MT,既是MT

比如：???(p2,p3)(p2,p7)(p4,p7)?，

??＝p1p2p4p5p6(p3?p7)?p1p3p5p6p7p4

所以，求可达状态集就可以通过循环计算特征函数来得到。 算法：

Reached=From=M0 do To=0

for each t?T do To= To+ Img(t,from) New=To - Reached From=New

Reached=Reached + New while (New ?0) return Reached

其中: Reached, From, New 都是状态点集对应的特征函数，Img(t, From)的含义是将变迁t作用于布尔函数From，既是计算From对应的可达状态集中能实施

V II

变迁t所得到的所有新可达状态集所对应的特征函数。

算法中所有的运算都是布尔运算，而布尔运算的实现可通过二叉决策图(Binary Decision Diagrams)的相应运算实现，并且可以证明每种运算都是多项式时间完成，在此不再做介绍，相关文献请见[9][10]。

该方法的优点在于求出特征函数后可快速判断某个状态是否可达。但该方法的问题在于：1. 在运算过程中使用的二叉决策图峰值远远大于最后结果的个数

2. 求出的特征函数只是一个无结构的集合，不能给出标识间的结

构关系，不能构造变迁过程，也无法讨论系统的可逆性。

这些方法都有自己的适用范围和优缺点。我们提出的方法是基于计算代数和神经计算的方法：综合了计算代数方法和矩阵计算方法，建立了能量优化模型，并用神经网络来实现算法，其特点就在于提出了一种可利用基于硬件的大规模并行的神经计算代替了基于软件的串行的数字计算。

在第一章简要介绍了Petri网的背景知识，第二章介绍了计算代数的方法和相关知识。后四章给出了作者的主要工作。附录中给出上述算法的Matlab程序。

VIII

第一章 背景知识

第一章 背景知识

§1.1 历史与发展

Petri网的概念最早在1962年Carl Adam Petri 的博士论文中提出来[1]。网论从一开始就以物理为基础，当时的理论计算机科学包括自动机模型和形式语言理论，其概念构架不适合描述物理系统，它缺少重要的并发概念。Petri网是一个状态变迁模型，可用来描述系统中各异步成分之间的关系，同时允许同时发生多个状态变迁，也是一个并发模型。当时的计划是要用一种兼容物理和计算机科学两者的语言和概念构架来形式化描述制约通信进程的所有“自然法则”[11]。1970至1975年，MIT的计算结构研究小组积极参与Petri网的相关研究，在1975年7月在MIT举行第一次Petri网和相关方法的研讨会。从1980年召开第一次Petri网理论和应用的国际研讨会以来，每年一次的国际研讨会连续不断，Petri网理论和应用的研究成果也不断涌现，到1987年已有2074篇重要的相关论文发表[12]。

随着研究的不断深入，Petri网理论也在不断地充实和完善，其抽象和描述能力也不断的朝着横向纵向发展。它的纵向扩展表现为：从基本的条件/事件(C/E)网，位置变迁(P/T)网，发展到谓词/变迁网和着色网等高级网。它的横向扩展表现为：从无参数的网，发展到时间Petri网和随机Petri网。

§1.2 研究方法及应用

Petri网模型就是一个基于图的数学形式化描述模型，用来分析离散的并发系统，或者说Petri网模型用来描述非同步的因果和非因果行为，包括并行和不确定选择。Petri网理论研究的主要内容是系统模型的行为特征，包括：可逆性(reversibility)、有界性(boundedness)、活性(liveness)、可达性(reachability)、可覆盖性(cover)、公平性(fairness)等。Petri网以研究模型的组织结构和动态行为为目标，着眼于系统中可能发生的各种状态变化及变化之间的关系。Petri网模型的主要分析方法依赖于对诸如关联矩阵、可达树、状态方程、位置不变量、变迁不变量等的研究与分析。

在Petri网研究与应用的发展历史中，它的应用范围已经远远超出了计算机科学的领域，成为研究离散事件动态系统的一种有用工具。如今，Petri网模型在众多方面得以应用。两个成功的应用领域是性能评价和通信协议，其他很有前景的应用领域包括分布式软件系统，分布式数据库系统，并发并行计算，柔性制造系统，多处理机系统，逻辑推理，办公自动化系统，形式语言，神经元网络和决策模型等。以协议工程形式化方法为例：协议的验证是基于对Petri网模型分析而进行的。概括地讲，协议工程形式化方法是要为协议设计的整个阶段提供规范化的指导，这包括描述(Specification)、验证(Verification)、实现(Implementation)和测试(Testing)等几个主要阶段，每一阶段都有相应的方法和技术。通过位置/变迁（P/T）网模型就可以很好的描述并分析整个系统。

1

Petri网系统的可达性研究

§1.3 Petri网的直观理解

用Petri网描述的系统有一个共同的特征：系统的动态行为表现为资源(物质资源和信息资源)的流动。在提供Petri网(PN)形式描述之前，通过分布系统几个基本行为模型描述的例子，先对Petri网作一个直观的说明。

一个Petri网的结构元素包括：位置(place)、变迁(transition) 、弧(arc)。位置用于描述可能的系统局部状态，例如：计算机和通信系统的对列、缓冲、资源等。变迁用于描述修改系统状态的事件，例如：计算机和通信系统的信息处理、发送、资源的存取等。弧通过其指向来规定局部状态和事件之间的关系：它们引述事件能够发生的局部状态；由事件所引发的局部状态的转换。

在Petri网模型中，标记包含在位置中，它们在位置中的动态的变化表示系统的不同状态。如果一个位置描述一个条件，它能包含或不包含一个标记，当一个标记表现在这个位置中，条件为真；否则为假。如果一个位置定义一个状态，在这个位置中的标记个数用于规定这个状态。例如：在计算机和通信系统中，标记可以用于表示处理的信息单元、资源单元和顾客、用户等对象实体。

一个Petri网模型的动态行为是由它的实施规则规定的，当使用等于1的弧权时，如果一个变迁的所有输入位置(这些位置连接到这个变迁，弧的方向是从位置到变迁)至少包含一个标记，那么这个变迁可能实施(相关联的事件发生)。对这种情况，这个变迁称为可实施的。一个可实施的变迁导致从它所有的输入位置中清除一个标记，在它的每一个输出位置(这些位置连接到这个变迁，弧的方向从标迁到位置)中产生一个标记。当使用大于1的弧权时，在变迁的每一个输入位置中都要包含至少等于连接弧权的标记个数，它才可以实施；这个变迁的实施 将清除在该变迁的每一个输入位置的相应的标记个数，并在变迁的每一个输出位置产生相应的标记个数。变迁的实施是一个原子操作，清除输入位置的标记和在输出位置产生标记是一个不可分割的完整操作。 §1.4 Petri网的形式化描述

本节的目的是把上一节的概念形式化。 一．网及其图形表示

定义 1-1 三元组N=(S, T ; F) 称为有向网的充要条件是：

1. S∩T=? (二元性)； 2. S∪T≠? (网非空); 3. F?S×T∪T×S;

4. dom(F)∪cod(F) = S∪T ;

其中 dom(F) ={x| ?y : (x,y)?F}，cod(F) ={y| ?x : (x,y)?F}

S和T分别称为N的位置集和变迁集，F为流关系(flow relation)。位置集和变迁集是有向网的基本成分，流关系是从它们构造出来的。位置和变迁是两类不同的元素，所以S∩T=? ，而S∪T≠? 表示网中至少有一个元素。每一个位置

2

第一章 背景知识

表示一种资源，变迁是资源的流动，由流关系规定，所以变迁只能与位置有直接关系： F?S×T∪T×S。dom(F)∪cod(F) = S∪T表示不存在不参加任何变迁的资源和不引起资源流动的变迁。

二．网系统定义

有向网是系统的结构框架，活动是框架上的是系统中流动的资源。网系统必须需指明资源的初始分布，规定框架上的活动规则，即位置的容量和变迁与资源之间的数量关系。

记: N={1,2,3,?}, N0={0}∪N, ω：+∞,对于有向网N=(S, T；F)。 定义 1-2

1．K: S?N∪{ω}称为N的容量函数（capacity function） 2．对于给定的容量函数k

M: S? N0 称为N的一个标识（marking）的条件是：

? s∈S M(s)≤K(s)

3．W：F?N 称为N上的权函数，对(x,y)∈F

W(x,y)=W((x,y)) 称为(x,y)上的权。权函数规定每个变迁发生一次引起的资源量上的变化，显然对任何(x,y)∈F，有 0< W(x,y) < ω

在此基础之上我们定义Petri网系统。 定义 1-3

六元组∑=(S,T；F, K,W, M0)构成Petri网系统的条件：

1．N=(S,T; F) 构成有向网，称为∑的基网

2．K, W, M0依次为N上的容量函数，权函数和初始标识(initial marking) 以上的是Petri网系统从结构到资源的静态特征。下面给出变迁发生的条件和结果，这种动态规律称为变迁规则。 定义1-4 可实施与实施(enabling and firing) 令∑=（S, T；F, K, W, M0）是一个P/T系统。

1．函数M:S?N叫做Σ的标识??s∈S: M(s)≤K(s)。 2．一个变迁t∈T在M下是可实施的??s∈S: W(s,t)≤M(s)≤K(s)- W(t,s).

T在M有发生权记作M[t>。

3．如果t∈T在标识M下是可实施的，那么t可以实施并产生一个新的后

继标识M’,M’可由下列方程给出：

?s∈S: M’(s)=M(s)－W(s,t)＋W(t,s)。

4．系统标识M经过t的实施得到新的标识M’，可以表示成M[t>M’

或者M?M’。

定义1-5 实施序列

令∑=(S,T；F, K,W, M0)是一个P/T系统，σ=M0t1M1t2?tnMn是∑的一个有限实施序列??i,1≤i≤n:Mi-1[ti>Mi ;σ的长度 ?=n ，t1t2?tn叫变迁实施序列。 定义1-6 可达标识

令∑=(S, T；F, K,W, M0)是一个有限的P/T系统，标识M是由M0可达的当且仅当存在一个变迁实施序列σ，使得M0经σ实施得到M，亦即，M0[σ>M。

3

Petri网系统的可达性研究

三．网系统分类

C、A、Petri1962年使用的系统模型实际上是K=Ω和W=1的网系统，70年代A、Holt把这种系统称为Petri网，于是Petri网由此得名。按网系统的容量函数K和权函数ω可分为三类：

1．K=1, W=1

这时每个S元只有“有token”和“无token”两种状态，可理解为只有“真”和“不真” 两种状态的布尔变量。网论中把这种s元称为条件，与条件关联的变迁称为事件。这种由条件和事件构成的网系统称为EN系统(条件/事件网)。 2．K=ω, W=1

这是传统上称为Petri网系统，又称为P/T网。 3．K，W为任意函数

这种系统通常称为P/T系统，下面将着重介绍

四．可达标识集

许多应用问题都关心系统可能的状态，可达标识集是解决这类问题的关键。可达标识集是Petri网任何可能发生序列所能进入的全部状态的集合。Petri网可达性的分析对于协议验证十分必要，因为用Petri网模拟协议的正确性的许多问题都可转化为可达性问题。P/T系统的若干重要性质可以用可达标识集来定义。 定义1-7 可达标识集

P/T系统∑=(S,T,F,K,W, M0)的可达标识集[M0>是满足下列条件的最小集合：

1. M0∈[M0>

2. 若有M’∈[M0>，t∈T,使M’[t>M,则M∈[M0>。

由以上定义可得：

定理1-1 M∈[M0>,则存在序列σ=M0t1M1t2M2…tnMn,使得? i: 0

Mi-1[ti>Mi,且Mn=M 。反之已然。

定义1-8 可达树

首先定义一记号ω：对于所有n∈N，n<ω；n+ω=ω+ω=ω-n=ω。

令∑=(S,T；F, K,W, M0)是一个P/T系统。∑的可达树是由标识（标记值可能由ω表示）为结点构成的树，其弧度由T元素标注。可达树由下列递归算法构成。(在第六章应用实例分析的最后，我们将给出该实例的可达树。) 算法1：P/T系统可达树构造

1．根结点r由M0标注。

2．一个标注M的结点x是一个叶结点当且仅当，不存在t∈T：t在M是可实施的或者在从r到x的路上存在一个结点y≠x，但结点y也是由M标注的。

3．如果一个标注M的结点x不是一个叶结点，那么对于所有t∈T使得在M下可实施的t实施而产生一个新的结点y，且在从x到y新产生的

M1?满足于M[t>M1?,弧上标注t。 y结点标注的标识M?可由M1?来计算，

即?s∈S，M1?(s)= M(s)－W(s,t)＋W(t,s)。M?的计算可区分为两种情况： 1) 从r到y的路上，如果存在标注M??的结点z≠y且?s∈S：M1?(s)

4

第一章 背景知识

?M1?(s),≥M??(s)，那么 M?(s)= ???如果M1?(s)?M??(s)其他

2) 其它情况，M?=M1?。

一个P/T系统有界，指的是它所有的元素都是有界的，很自然它的可达树也是有界的。

定义2-8 可达图

令∑=（S, T；F, K,W, M0）是一个有限的P/T系统，∑的可达图是由标识(标记值可能由ω表示)为结点的图，其弧线由T元素标注。可达图有下列算法构成。 算法2：可达图构成

1．两个可达树的结点是等价的当且仅当它们有相同的标注M。

2．可达图的结点是它的可达树结点的等价类。从结点Y到结点Z的弧线

标注为t，当且仅当存在y∈Y且存在z∈Z，使得在可达树中从y到z由弧线t。

可达图是可达树中相同结点的相重叠。

五．系统模型的行为特征

1. 若对于所有的M∈[M0>，存在正整数k，使得对所有s∈S，M(s)≤k，就说Σ是有界P/T系统，或k_为界P/T_系统。Petri网模型的有界性是指网中任何位置的标记数是有界的，无界的Petri网模型表示相应的协议层上有无限多的标记数，这样的协议显然是很不公平的。k=1时也称Σ为安全系统。k为界系统也称k安全系统，k是这种系统的界。

2． t∈T，若对任一可达标识M∈[M0>,均有从M可达的,存在标识M?∈[M>，使得M?[t>，就说变迁t是活的。若所有t∈T都是活的，就说系统Σ是活的。Petri网具有活性表明该协议是无死锁的。有些系统的界有时不易或无法确定，但可以证明其存在性，这时也可以笼统的说该系统是有界的。定义中的[M>为从M出发有限步可到达的标识集，也就是以M为初始标识时的可达标识集。 M?[t>是t在M?有发生权。T的活性要求它在任何可达标识M∈[M0>均有潜在的发生权，即有限步即可获得的发生权。

3. Petri网模型的可覆盖性：在一个P/T系统中，标识M称为可覆盖的，当且仅当系统可达集中存在标识M′，使得对系统中任一位置P，M′(P)?M(P)成立。

4．Petri网模型的可逆性：在一个P/T系统中，若对于所有的M∈[M0>，都有从M可达到M0 。如果M0[σ> M’，M’[t>M，我们可以得到，从M可达到M’。

六．Petri网模型的主要分析方法 定义2-11 关联矩阵和不变量

令∑=(S,T;F,K,W,M0)是一个有限的P/T系统，且S={s1,s2,?,sn},T={t1,t2,?,tm}。 1．矩阵C=[cij](1≤i≤n，1≤j≤m)是∑的关联矩阵当且仅当

cij =W(tj，si)－W(si，tj)。

2．一个n元整数列向量x叫作∑的一个S-不变量当且仅当 CT×x=0，其中CT

为C的转置矩阵。

3．一个m元整数列向量y叫作∑的一个T-不变量当且仅当 C×y=0。

5

Petri网系统的可达性研究

假定m元非负整数行向量σ是σ的变迁实施计数向量，亦即σ的第i元素表示变迁i从M0到M转换过程中的实施次数，则有:

M=M0+ C×σ 于是有下面定理: 定理1-2：

一个n维向量X是∑的一个S-不变量当且仅当 MTX=M0TX，其中M0是∑的初始标识，M∈[M0>。 证明：“?”

因为x是∑的一个S-不变量，所以有CTX=0；又有M∈[M0>，所以 M=M0+ C×σ，即MT= M0T+σT×CT，所以MTX=M0TX＋σT×CTX，得 MTX=M0TX。

―?‖

M∈[M0> ? MT= M0T+σT×CT, MTX=M0TX＋σT×CTX，又有MTX=M0TX

σT×CTX=0; 由M的任意性可知CTX=0。 ?

同样有下面的定理。 定理 1-3：

一个m维向量X≥0是∑的一个T-不变量当且仅当存在∑的一个标识

M∈[M0>（M0是∑的初始标识）和一个变迁实施序列σ从M回到M，亦即，M?M，σ的实施计数向量σ等于X。

第二章 Petri网与代数系统的关系

§2.1 Petri网模型映射到代数系统

除了用关联矩阵，各种向量的方法来表示Petri网系统的状态和系统变化的过程以外，还有其他的数学描述方法来刻划和定量分析Petri网系统的性质。1995年Olga Caprotti, Alois Ferscha, Hoon Hong[2]提出利用代数系统来描述Petri网系统的性质。下面将介绍Petri网系统的多项式的描述方法。 一．映射的直观描述

1．系统状态映射成多元多项式环上的单项式。

系统位置Pi?Xi

Pi中的token数?Xi的方次 系统状态M ?一个单项式a 2．变迁条件映射成双项式

根据ti的输入输出的连接位置及弧的权值，将变迁条件映射成双项式。 ti ? fi

3．变迁过程映射成多项式除法。

ti在状态M下可施实等价于 ?ci ,使得a=ci LT ( fi ) , a是M对应的单项式，ci 是单项式，LT(fi)表示 fi的第一项，ST(fi)表示 fi的第二项。 后继状态＝a－cifi＝ci ST ( fi ) 。

ci 的实际意义是ti变迁没用到的资源；

6

第二章 Petri网与代数系统的关系

LT(fi) 的实际意义是ti变迁消耗的资源； ST(fi) 的实际意义是ti变迁产生的资源。

比如：

t1 P1 2 1 P3 1 2 t2 P2 P4 P5

2 2 系统状态为：x13x2x5

Pol(t1)＝x12x2－x3x42 = f1 Pol(t2)＝x42－x52 = f2

很明显，系统状态与多元多项式环上的单项式一一对应。

这时t1是可施实的，t1实施后系统状态变为：

P1 2 1 P3

1 2 P4 P5 P2 2 2

变迁过程的代数表达:

x1x3x42x5=x13x2x5－x1x5f1＝x13x2x5－x1x5(x12x2－x3x42)

=x13x2x5－x13x2x5 + x1x3x42x5

二．映射的形式化描述

Petri网系统到Petri网代数系统。

定义2-1：给定一个Petri网系统PN=(S,T,F; W,M0) 都可以生成一个Petri网代数系统PNA=(X,H,a0)。

I. X={x1,x2,?,xn} 系统位置Pi?xi

II. H={hi | hi 为型如 x1e1x2e2?xnen － x1d1x2d2?xndn 的双项式}

对tj∈T, 对应的双项式

hj ：x1e1x2e2?xnen － x1d1x2d2?xndn 其中:

?W(pi,tj)ei???0if(pi,tj)?F其它

7

Petri网系统的可达性研究

?W(tj,pi)di???0if(tj,pi)?F其它

III. a0 = x1k1x2k2?xnkn ki 表示 M0 状态下Pi中的token数。

三．可达性的代数表达 定理2-1：

对于P/T网系统，∑=（S,T；F, K,W, M0），σ=M0t1M1t2…tnMn是∑的一个有限实施序列，其中，Mi对应的状态单项式为ai，ti对应的变迁双向式为gi，则：a0－an=∑cigi , ci为多项式

证明：M0[t1>M1 对应的代数表示为：a1=a0 – c1g1

M1[t2>M2 对应的代数表示为：a2=a1 – c2g2=a0 – c1g1– c2g2

??

M0[σ>Mn 对应的代数表示为：an＝a0－∑cigi ，即a0－an=∑cigi 。

定理2-2：对于P/T网系统，从M1可变迁到M2?存在a0－an的一组正表示即

a0－an=∑cigi，并且ci为正多项式。

证明：充分性上面已经证明，下面证明其必要性。

a0－an=∑cigi，并且ci为正多项式，可以将各项拆开，a0－an=∑digi d1是正单项式, 当然gi可能有重复，digi是双项式,记为：xi－yi

等式左边为两个正单项式之差，右边必存在xi1＝a0，将xi1－yi1移到左边 a0－(xi1－yi1) －an＝yi1－an , 令yi1=a1 , 重复上面的工作，最后得到一组正 单项式{a1 , … , an-1 },也就构造出M1变迁到M2的过程。

我们将可达性问题转化为了一个多项式是否属于某个理想的问题，要研究该问题必须用到计算代数的相关知识。

§2.2 基于Grobner基的Petri网系统性质分析 一．计算代数基本概念[13]

定义2-2 在T(x1,x2,?,xn) 上满足下列条件的线序≤叫做T(x1,x2,?,xn)上的单项式序。

1、?t?T(x1,x2,?,xn)1?t;

2、对每个s,t1,t2?T(x1,x2,?,xn),t1?t2?t1?s?t2?s

关于单项式序的例子有很多，比如最常用的有字典序: 定义2-3 在T(x1,x2,?,xn)中，定义x1?xn(d1,?,dn)?(e1,?en)或者存在1?i?nd1dn?x11?xnn当且仅当

ee使得dj?ej,1?j?i?1并且 di?ei。这种

序被称为字典序，我们常用?lex表示。

很容易验证字典序是单项式序。我们可以给出一些例子。

8

第二章 Petri网与代数系统的关系

1．x1x22?lexx23x32。

2．x1x23x36?lexx1x23x34;按照字典序我们有x1?lexx2?lex??lexxn, 另一方面，在变元x1,x2,?,xn中任意给定一个次序，也可诱导出上

T(x1,x2,?,xn)的一个字典序。假如设变元是

x, y，如果规定x>y，则在T(x, y)

中给出一个字典序，但是如果规定y?x，则在T(x, y)中给出了另一个字典序，这两个序是不同的。一般的，在n个变元的情况下，我们可以给出n!种不同的字典序。

研究多项式时，很多时候研究多项式的首项，下面给出相关的几个概念。 定义2-4. 假设≤是T上的单项式序。对于非零的多项式f?k?x1,?xn?，称(T(f),

?)中的最大项为

f的首项，用HT?f?表示。称(M(f), ?)中的最大项为f的首单

项式用HM?f?表示。首单项式HM?f?的系数称为首系数，用HC?f?表示。显然有

HM?f?= HC?f??HT?f?

对于给定的单项式序≤，如果f≠0，并且HC?f?=1，则称f是首1的多项式。

有了单项式的序就可以自然诱导出多项式的序，单项式序的诸多性质也为化简多项式提供了计算的方向和可计算的保证。

定义2-5 假设k是数域，令f,g,p?k?x1,x2,?xn? ，其中f,p?0，设≤是

T(x1,x2,?,xn)上的单项式序，P

是k?x1,x2,?xn?的子集，

?p?P,p?0我们有

1、如果t?T(f),并且存在s?T(x1,?,xn），使得s?HT(p)?t，而且

g?f?aHC(p)?s?p, 其中a是t在f中的系数

2、如果存在t ?T(f)使得f?pg?t?, 则称f模p约化到g记做：f?pg。 3、如果存在p?P,使得f?pg，则称f模P约化到g记做：f?Pg 4、如果存在g?k?x1,?,xn?,g?f使得f?Pg，则称f模P可约化。

9

Petri网系统的可达性研究

如果一个多项式f可以经过一系列约化步骤得到g，(即存在g1,g2,?,gn

?Pg表示。 使得f?Pg1,g1?Pg2,?,gn?1?Pgn?g)。我们用f?如果一个多项式f模P是不可约化的，则称f模P的范式。很明显，只有当T(f)中的每一项都不能被{HT(p) | p?P} 中的任一项整除时，f模P才是不可约化的。

对于每个多项式f,都存在一个多项式g使得：f?Pg 其中g是f模P是不可约化的，我们称g是f是模P的范式。

定理2-2 假设P=p1,p2,?,ps是k?x1,x2,?xn?的有限序列，f∈k?x1,x2,?xn?,则存在f模P的范式g，和一组多项式{a1,a2,…,as}?k?x1,x2,?xn?

s满足f??ai?1ipi?g，并且 max{HT(aipi) | 1≤i≤s, aipi≠0}≤HT(f)。

有了存在性人们自然要研究它的唯一性，可惜在一般情况下不能保证范式的唯一

性，下面就是一个简单的反例。

例 设f(x,y)?xy2?x?k?x,y?,p1(x,y)?y2?1，p2(x,y)?xy?1

令P={p1(x,y)，p2(x,y)}, ≤是T(x,y)上的字典序。

我们有f(x,y)?p0

12 另一方面又有f(x,y)?p(?x?y)

这里0，(?x?y)都是f(x,y)模{p1(x,y)，p2(x,y)}的范式，但它们是不同的。

二．Grobner基及其算法

为了研究多项式环，就必须研究环上的理想，研究理想的结构，基是一个有力的工具，第一个要问的问题就是基的个数，有限还是无穷。下面的定理给出了一个明确的普遍而深刻的回答。

定理(Hilbert基定理) 每个理想I?k?x1,x2,?xn?都有一个有限基，即存在

f1,f2,?,ft?I使得I?f1,f2,?,ft。这个有限集G??f1,f2,?,ft?称为I的

Grobner基。(详细证明请见[13],[22])

Hilbert基定理给出了有限基的存在性，接着下一个问题就是如何找到。要想找到，首先必须知道目标的“样子”，也就是Grobner基有什么样的性质。 Grobner基性质定理 设G是k?x1,x2,?xn?的有限子集，给定单项式序≤，则下列性质等价：

10

第二章 Petri网与代数系统的关系

（1） G是理想G的Grobner基； （2） 对每个f?G,f模G的范式为0；

（3） 对每个非零的多项式f?G，f模G是可约的。

定义2-6 设g1,g2?k?x1,x2,?xn?, 是两个非零多项式。 如果HT(g1)?x1ax2a?xna，HT(g2)?x1bx2b?xnb12n1212nn 令cii=1,?,n,?max{ai,bi}，

则称xc?x1cx2c?xnc为HT(g1)和HT(g2)的最小公倍式， 记作： LCM(HT(g1),HT(g2))。

设ti?HT(gi),ai?HC(gi), i=1,2并且t?siti?LCM(t1,t2),其中si?T(x1,?,xn) 则称：S(g1,g2)?a2s1g1?a1s2g2为g1, g2的S-多项式

例1. 设f?x3y2?x2y3?x,g?3x4y?y2?R?x,y?, 单项式序是分次字典 序，则LCM(HT(f),HT(g))?x4y2, S(f,g)?3x?f?y?g??3x3y3?3x2?y3 定理2-3 假设G是k?x1,x2,?xn?的有限子集，并且0?G,则下列性质等价： (1) G是理想〈G〉的Grobner基； (2) ?g1,g2?G, S?g1,g2??0

G?有了这些性质，我们就可以计算Grobner基。

Grobner基算法[34]：

设F??f1,f2,?,ft??k?x1,x2,?xn?, 理想I?f1,f2,?,ft，则下列算法可计算理想I的Grobner基G。

Input: F={f1,f2,…,fs}

Output: G={g1,g2,…,gt}?F, G is Grobner basis of〈F〉 Begin G:=F

B:={{g1,g2}| g1,g2∈G,g1≠g2} While B≠Φ do Choose {g1,g2}∈B B:=B－{{g1,g2}}

h:= S(g1,g2) h0:= S(g1,g2)G

11

Petri网系统的可达性研究

if h0≠0 then B:=B∪{{g,h0}| g∈G} G:=G∪{h0} End

根据上面的算法和变迁多项式的形式，我们有下面的定理。 定理2-4

变迁多项式的Grobner基仍保持两单项式相减的形式，每项系数为1(或-1) 。 证明：由上面的算法，G先赋值为F每一项是两单项式相减的形式，

h:= S(g1,g2)＝S(g1,g2)?a2s1g1?a1s2g2，消掉两项，剩下的保持两单项式相减的形式。又h0:= hG 约化时每次同时消掉两项，剩下的保持两单项式相减的形式。所以添加到G中的多项式都是两单项式相减的双项式。 同理可得计算过程保持每项系数为1(或-1)。

由于在计算过程中有此形式，所以计算量比通常的求Grobner基的计算量小。 根据以上的理论，Petri网可达性等行为特征就可以用Grobner基来表述，因为用Grobner基的方法很容易判断一个多项式是否属于某个理想，所以根据定理 对于完全可逆Petri网，Grobner基的方法是一个完全的判准；但对于不可逆Petri网，它只是状态可达的一个必要条件。 §2.3 Maple符号计算软件介绍[14]

一．Maple简介

Maple 是加拿大Waterloo University 发展起来的一种数学软件, 它那无与伦比的符号运算能力，已使Maple在国际通用数学软件的激烈竞争中独占熬头。不仅使国外学生中广为流行的\科学便笺式\软件Mathcad靠Maple实现符号运算，就连首屈一指的数值计算软件MATLAB在扩展其符号运算能力时，也借助了Maple的威力。Maple V版本提供数学函数2000余种（现在更新的版本有Maple 7.X），其涉及范围：基本代数学、欧几里德几何学、数论、有理函数、微积分、线性代数及矩阵论、微分方程、图形学、离散数学、群论、以及数学的其它许多领域。Maple是一个开放的系统，它提供一套内部的编程语言，使用户可以开发自己的应用程序。事实上 Maple 所提供的2000多种函数种，绝大部分是用这种语言编写的。

二. Maple的工作窗口

Maple V Release 2有基于Dos 和 Windows 的两个版本，可以在80386或80486以上的微机上运行。基本运行环境要求硬盘有至少15MB的空间、4MB的内存，其中Windows 版需要 MS-windows3.1 以上版本（中西文版本均可）均可.Maple V for windows 启动后会出现一个Maple 工作区空白窗口. 此时，用户就可以在 Maple 工作区内出现的提示符号―>‖后，输入命令，进行工作。需要说明的是：输入表达式后面必须用分号\；\结尾，以表示命令的结束，然后按回车键进行运算。如若结尾缺少\；\，那么Maple 认为命令没有结束，而处于等待状态。

12

第二章 Petri网与代数系统的关系

三. 符号运算

Maple最主要的功能是符号运算，其功能强大是举世公认的.符号运算的魅力在于：运算时，无需事先对独立变量赋值，而所得得结果以标准得符号形式表达。在符号表达式中得数字都是不含任何机器精度误差得绝对精确值（如：2/3就绝不会表示成0.66666.....).这是任何数值计算所无法实现的。

四．Grobner基软件包

我们所使用的Maple版本是Maple V Release 2。

在进入Maple系统后，只需键入： > with (grobner)；

即可调入Grobner基软件包。（其中>是Maple系统的提示符，所有的Maple命令都以分号结束）。当Grobner基软件包被调入后就可以计算Grobner基，范式，S-多项式等。在上一节我们介绍了几种单项式的序，在Maple系统中可以使用字典序和分次逆字典序。Maple系统用plex表示字典序，用tdeg表示分次逆字典序。单项式序还与变元的排列次序有关，因此必需给出变元的排列次序。比如：为了告诉Maple系统使用字典序，变元排列次序为x>y>z，需要输入plex和[x,y,z]，Maple系统的缺省单项式序是tdeg。

在Maple的Grobner基软件包中最常用的命令是gbasis,可用来计算一组多项式的Grobner基，用法是:

> gbasis(polylist,termorder)；

其中：polylist表示生成理想的多项式组，termorder表示变元的排列次序及单项式序。例如：

> with(Grobner):

WL:=[x^2-2*x*z+5,x*y^2+y*z^3,3*y^2-8*z^3]: GB:=gbasis(WL,plex(y,x,z));

GB := [240z???1600z???9z???96z,640xz???9z???120z???96z,x???2xz???5,80yz???3z???32z???40z,3y???8z]387523639838572

> gbasis(WL,tdeg(x,y,z));

[x???2xz???5,?3y???8z,8xy???3y,9y???48zy???320y]22323432

在Maple的Grobner基软件包中另一个在Maple的Grobner基软件包中另一个最常用的命令是normalf，可以用来计算多项式f模理想I的范式。 它的用法是：

> normalf(f,polylist,termorder)；

其中：polylist表示生成理想的多项式组，termorder表示变元的排列次序及单项式序。

例如：

> q:=x^2-x*z^3+y^3+y*z: normalf(q,GB,plex(x,y,z));

13

Petri网系统的可达性研究

2xz???yz???73640z???87360z???77348z???5

5

在Grobner基软件包中其他常用命令有：

? leadmon 计算多项式f的首单项式HM(f). ? spoly 计算多项式f,g的S-多项式.

? solvable 判断多项式方程组{f1,f2,…,fn}在代数封闭域K上是否有

解。

? finite 判断多项式方程组{f1,f2,…,fn}在代数封闭域K上是否有

有限解。

? gsolve 可以求出多项式方程组{f1,f2,…,fn}在代数封闭域K上是

否有解。

§2.4 计算代数方法的局限性

通过上述的分析，我们知道计算代数方法，在处理可达性的时候有个强假设就是该Petri网系统可逆，但对于实际问题，你事先根本不知道该Petri网系统是否可逆。问题的关键在于Petri网系统的变迁条件与过程是有方向的，也就是在变迁多项式（双项式）前乘上的系数必须为正，而理想中的元素被基所表示时不能有效的反应这种性质。要判断可逆性就必须判断某种状态是否能回到初状态，又回到可达性问题了，所以只能作一个必要条件用，这一问题始终不能解决。 其次，即使Petri网系统是可逆的，用计算代数方法只能判断是否可达而不能构造出变迁过程。而在分析系统性质时状态变迁过程是必要的。

当然就Grobner基方法本身也存在一些问题，从现在已知最好的算法来看，计算一个理想的Grobner基，也需要花费很长的时间和大量的存储空间，主要原因是：在Grobner基的计算过程中，我们需要生成大量的中间多项式。

当然除了Grobner基方法还有其它的计算代数方法，比如：吴方法[26]，Dixon结式方法[31]，相对单纯分解方法[23]，聚筛方法[32]。在计算效率上比Grobner基方法高，但是这些方法都着眼于多项式组的零点问题，而不是理想的归属问题。由Hilbert 零点定理[22]，代数簇与理想不是一一对应，而与根理想一一对应，所以在用于Petri网系统的可达性分析时有些不方便，仅仅可作为可达性分析的一个比较弱的必要条件。 所以我们有必要找到一个有效的方法来解决以上计算代数方法的不足。通过第二章第二节的内容，我们知道Petri网系统的状态与n维线形空间的第一象限的整点有自然的对应，同样变迁对应于对点作平移变换，可达性问题可以化为点对点的平移变换序列的存在性，但变换是有限制的，就是只能在第一象限做变换。这种限制可以通过能量优化的方法表现。下面我们将介绍能量优化模型和模型的神经网络解法。

14

第三章 能量优化模型

第三章 能量优化模型

能量优化模型的引入主要基于用矩阵描述变迁过程和用罚函数处理约束的思想，每个变换步骤对应一个能量，整个变换过程只能在第一象限，一旦“出界”对能量函数加上一个足够大的惩罚，这样只要存在一个解使得总能量充分小就能说明该解满足约束条件。

§3.1 Petri网系统映射到线性空间

一．Petri网到线性空间的映射规则

给定一个Petri网系统PN=(S,T,F;K,W,M0) 都可以生成一个Petri网线性空间PNL=(LP+,TS,V0)。

1．系统状态空间映射成LP+，n维线形空间第一象限的符合容量函数K限制

的整点集，

系统位置Pi?xi ，n维线形空间的第i个分量，

系统状态Mi?Vi , n维线形空间的一个各分量为非负整数的符合容量函数K限制地状态点; 2．变迁映射成平移变换集TS={fi | fi 是n维线形空间中各分量为整数的向量} 对tj∈T,

A. 当没有位置是同时某个变迁的输入和输出时， 对应的平移变换fj ：(x1,x2,?,xn) 其中:

?W(tj,pi)?xi???W(pi,tj)??0如果(tj,pi)?F并且(pi,tj)?F如果(pi,tj)?F并且(tj,pi)?F 其它B. 当有位置是同时某个变迁的输入和输出时，

对应两个平移变换fj＋：(x1,x2,?,xn) 和 fj－：(y1,y2,?,yn) 其中:

?W(tj,pi)xi???0??W(pi,tj)yi???0如果(tj,pi)?F其它如果(pi,tj)?F其它

3．tj在状态M下施实条件映射成：

A. 当没有位置是同时某个变迁的输入和输出时，

对于V+fj 的每一个分量xi 都满足,0≦xi≦K(xi) , 而且V+fj就是tj在状态M下的施实结果。

15

Petri网系统的可达性研究

B．当有位置是同时某个变迁的输入和输出时， 对于V+fj－ 的每一个分量xi 都满足,0≦xi≦K(xi) ,

对于V+ fj－＋fj+ 的每一个分量xi 都满足,0≦xi≦K(xi) , 而且V+ fj－＋fj+ 就是tj在状态M下的施实结果。

4. 初状态a0?V0 =(x1,?,xn), 其中xi 表示 M0 状态下Pi中的token数。

5．一个变迁过程Mi [ti>Mi+1 映射成对状态点Vi作平移变换fi，变换到状态点Vi＋1。

tj实施时先作变换fj－，再作变换fj＋。这时将tj分解为两个平移变换，其目的是: 为了保证PNL=(LP+,TS,V0)的变迁条件与PN=(S,T,F;K,W,M0) 的变迁条件等价。 定理3-1 tj可实施的条件为?pi∈S: W(pi,tj)≤ M(pi)≤K(pi)- W(tj,pi).

与PN=(S,T,F;K,W,M0) 的变迁条件等价。

证明：根据tj的连接情况将位置点pi分为四类：

a) (pi,tj)?F并且(tj,pi)?F, W(pi,tj)＝0，W(tj,pi)＝0，M(pi)＝xi b) (pi,tj)?F并且(tj,pi)?F, W(tj,pi)＝0，M(pi)－W(pi,tj)＝xi

0≦xi≦K(xi) ? W(pi,tj)≤ M(pi)≤K(pi)

c) (pi,tj)?F并且(tj,pi)?F, W(pi,tj)＝0，M(pi)+ W(tj,pi)＝xi

0≦xi≦K(xi) ? 0≤ M(pi)≤K(pi)- W(tj,pi)

d) (pi,tj)?F并且(tj,pi)?F,

对于V+fj－ 的每一个分量xi 都满足,0≤xi 等价于W(pi,tj)≤ M(pi) 对于V+ fj－＋fj+ 的每一个分量xi 都满足, 0≤xi≤K(xi) 等价于0≤M(pi)－W(pi,tj)＋W(tj,pi)≤K(pi)

二．可达性的矩阵表达

定理3-2:对于P/T网系统，∑=（S,T；F, K,W, M0），σ=M0t1M1t2…tnMn是∑的

一个有限实施序列，其中，Mi对应的状态点为Vi，ti对应的平移变换为fi，则：Vn=V0+∑fi 。

证明：M0[t1>M1 对应的向量表示为：V1=V0＋f1，

M1[t2>M2 对应的向量表示为：V2=V1＋f2 ， ??

M0[σ>Mn对应的向量表示为: Vn=V0+∑fi。

定义 3-1变迁矩阵：对于P/T网系统，∑=（S,T；F, K,W, M0），σ=M0t1M1t2…tnMn是∑的一个有限实施序列，对应的变迁矩阵：TM=[V0 ,V1,?, Vn]每个Vi对应Mi。

定义 3-2变迁选择矩阵：

对于P/T网系统，∑=（S,T；F, K,W, M0），σ=M0t1M1t2…tnMn是∑的一个有限

16

第三章 能量优化模型

实施序列，平移变换集的个数为t，ti 对应平移变迁ft，其变迁选择矩阵为：

iTC=[X0 ,X1,?, Xn],Xi为t维列向量，其中第ti个分量为1，其它的分量为0。

定理 3-3 M0[σ>Mn ? 存在一有限平移变换序列使得V0 变换到Vn，且整个

变换过程的状态点的每一个分量xi 都满足,0≦xi≦K(xi) 。

证明：由定理3-1和定理3-2可得。 §3.2 弱可达性及其分析

一．弱可达性的引入

将定理3-3修改为较弱的命题：

M0[σ>Mn ?存在一有限平移变换序列使得V0 变换到Vn； 也就是存在一组非负整数k1,k2,?kn使得：

?Vn?V0??f1,f2,?fn???k1,k2,?kn? (1)

是M0[σ>Mn的必要条件，其中ki表示变迁ti被实施了ki次。

定义3-2 弱可达性：如果该方程组有非负整点解则称M0到Mn弱可达。 该问题转化为方程组的非负整点解的问题，这个问题又分为两个问题： a．是否有解

b．是否有非负整点解

二．弱可达性的判断 1．求解方程组

对于方程组， ?f1,f2,?fn???x1,x2,?xn?T＝Vn－V0 先三角化，再求解 1) 如果解是零维解，计算出来看是否是非负整点解；

2) 如果解是流形解，设xm,xm+1,?,xn是自由变元，原问题化为不等式方程

组的整点解的问题：

?x1?g1(xm,xm?1,?,xn)?0?x?g2(xm,xm?1,?,xn)?0?2?? (2) ???x?gm?1(xm,xm?1,?,xn)?0?m?1??xm?0,xm?1?0,?,xn?0其中：g1,g2,?,gm-1为关于xm,xm+1,?,xn的线性表达式

2．不等式方程组的整点解问题的转换

定理3-4 将 Maxx1?g1(xm,xm?1,?,xn)作为目标函数，

17

Petri网系统的可达性研究

?g2(xm,xm?1,?,xn)?0?????将 ?gm?1(xm,xm?1,?,xn)?0作为限制条件，该问题转化为整数规划的问

?x?0,x?0,?,xn?0m?1?m?是整数?x1,x2,?,xn题。如果解得x1最大值小于零则原方程无解，否则就有解。

证明： 如果解得x1最大值小于零，则方程组（2）必然无解，否则x1最大值就

大于等于零。

如果解得x1最大值大于等于零，则取该最优值时的各变量取值也满足 方程组（2），即方程组（2）有解。

定义3-2 最短可达距离 (状态间距离下界)

假设方程组（2）有解，将 Min D=x1+x2+?＋xn 作为目标函数，

?g1(xm,xm?1,?,xn)?0?g(x,x,?,xn)?0?2mm?1????将 ?

gm?1(xm,xm?1,?,xn)?0??xm?0,xm?1?0,?,xn?0??是整数?x1,x2,?,xn作为限制条件，该问题又转化为整数规划的问

题。Min D 就称为最短可达距离。其含义是从一种系统状态变迁到另一种系统

状态，在不考虑“越界”情况下，从M0达到Mn所需的最少步骤。也是M0到Mn的状态间距离下界。根据其定义，不难证明。同时解出x1,x2,?,xn，即计算出每个变迁ti被实施的次数。这个状态间距离下界将作为能量优化模型中初始变迁步数设定的一个参考量。

三．整数规划方法介绍[17] 1．数学模型

minf(x)?c1x1?c2x2???cnxn

(p)

?a1,1x1?a1,2x2???a1,nxn?b1?ax?a2,2x2???a2,nxn?b2?2,11?s.t. ???

?ax?ax???ax?bm,22m,nnm?m,11??xi?0且为整数，i?1,2,?,n

相应的线性规划问题（即不考虑整数条件）为 min f (x) =cX

18

第三章 能量优化模型

(p?)

s,t. ??AX?b?X?0 X表示未知变元构成的向量。

称p?为P的松弛问题，P为p?的一个限制。

2．分支定界算法

第一步，求解p?。若p?没有最优解，则停止计算，P也无最优解；否则转入

下一步。

第二步，若求得p?的最优解满足整数条件，则它就是P的最优解，停止计算；否则，转入下一步。

第三步，在p?的解中，任选一个不是整数的变量xj，如xj的值为bj，作两

个后继问题，即对问题p?增加一个约束条件xj 小于bj的最大整数或xj大于bj的最小整数，不考虑整数条件，求解这两个后续问题。

第四步，在现有的且未分解出后续问题的可行问题中，选目标函数值为最小的问题重新称为问题p?，返回第二步。

3．线性规划问题

对于问题p?，即线性规划问题有许多方法，在此对算法本身不作详细介绍，只简单说明一下方法的思想。

? 单纯形法[17]： 对于标准形式的线性规划问题,若有有限最优值，则目标函数的最优值必在某一基本可行解处达到，因而只需在基本可行解中寻找最优解。单纯形法的基本思想就是先找一个基本可行解，检验是否为最优解，否则，再找一个使目标函数值有改进的基本可行解进行检验，反复进行迭代，直到找到最优解，或判断问题无界（即无有限最优值）。

? Karmarkar投影尺度算法[33]： 1984年AT&T贝尔实验室的N. K. Karmarkar，提出一个新的解决线性规划的多项式时间算法，成为线性规划突破性进展，以后几乎被所有现代LP(线性规划linear programs)解决方案所采用。这种算法不同于单纯形方法，每次迭代不是从一个极点出发求改进的极点，而是使迭代点保持在单纯形内部，因此是一种内点算法。其基本思想是，给定一个可行内点，对解空间进行变换，使得现行解位于变换空间中多胞形的中心附近，然后使它沿着最速下降方向移动，求得一个改进的可行内点，再做变换，将在变换空间中求得的点映射回原来的解空间，得到新的内点，重复以上过程，直至求出满足精度要求的最优解。算法的总复杂度为 O(n3.5L2 lnL lnlnL),其中n是变量数，L是方程个数。

19

Petri网系统的可达性研究

五．整数规划常用数学软件

MATLAB[16]是一个高性能的科技计算软件，广泛应用于数学计算、算法开发、数学建模、系统仿真、数据分析处理及可视化、科学和工程绘图、应用系统开发，包括建立用户界面。当前它的使用范围涵盖了工业、电子、医疗、建筑 等各领域。MATLAB是英文Matrix Laboratory(矩阵实验室)的缩写，最早是由C.Moler用Fortran语言编写的，用来方便地调用LINPACK和EISPACK矩阵代数软件包的程序。后来他创立了MATHWORKS公司，对MATLAB作了大量的、坚持不懈的改进。现在MATLAB已经更新至6.x版，MATLAB提供的工具箱已覆盖信号处理、系统控制、统计计算、优化计算、神经网络、小波分析、偏微分方程、模糊逻辑、动态系统模拟、系统辨识和符号运算等领域。

目前在欧美各国MATLAB的使用十分普及。在大学的数学、工程和科学系科，MATLAB被用作许多课程的辅助教学手段；在科研机构和工业界，MATLAB是高质量新产品研究、开发和分析的主要工具之一。1997年，MATHWORKS公司总裁兼首席科学家Moler因其对MATLAB的贡献当选为美国工程科学院院士。 相关资料请浏览MATHWORKS公司主页：http://www.mathworks.com

LINDO是一种专门用于求解数学规划问题的软件包。由于LINDO执行速度很快、易于方便输入、求解和分析数学规划问题。因此在数学、科研和工业界得到广泛应用。LINDO主要用于解线性规划、非线性规划、二次规划和整数规划等问题。也可以用于一些非线性和线性方程组的求解以及代数方程求根等。LINDO中包含了一种建模语言和许多常用的数学函数（包括大量概论函数），可供使用者建立规划问题时调用。 一般用LINDO（Linear Interactive and Discrete Optimizer）解决线性规划（LP—Linear Programming）。整数规划（IP—Integer Programming）问题。其中LINDO 6 .1 学生版至多可求解多达300个变量和150个约束的规划问题。其正式版（标准版）则可求解的变量和约束在1量级以上。LINDO有多种组件和版本，版权由美国Lindo System Inc.拥有，有关该软件的发行版本、发行价格和最新信息可从该公司网站http://www.lindo.com获取

§3.3 能量优化模型建立和分析

一．N步可达性

定义3-3 状态间距离上界：

P/T系统∑=(S,T,F,K,W, M0)的可达标识集[M0>，可达标识集中任意两个状态Mi ,Mj，如果从Mi 可达到Mj, 则将实施序列长度记为: length (Mi ,Mj)， 令状态间距离上界 D(∑)=max{ length (Mi ,Mj) | Mi ,Mj ?[M0> } 定义3-4 N步可达性

对于P/T网系统，∑=（S,T；F, K,W, M0），和状态标识M，对于给定的步数上界N，如果存在σ=M0t1M1t2…tnMn是∑的一个有限实施序列，Mn=M， 且n

很明显N步可达性的条件比可达性强，当然由于状态间距离上界不知道，所以很难确定N, 规定一个N步可达性其原因在于：

1. 在实际的变迁中或随机Petri网中，当实施步骤越多，发生的概率越小； 2． 在能量优化模型中必须有这么一个变迁步数的上界便于分析。

20

第三章 能量优化模型

二．罚函数(能量映射函数)的确定

弱可达性仅是判断可达性的一个必要条件，其区别在于没有对越界作处理， 我们找到一个没有出现越界的变迁过程。所以一旦出现“出界”就对能量函数加上一个足够大的惩罚，这样只要存在一个解使得总能量充分小就能说明该解满足约束条件。

定义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

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

本文来源：https://www.bwwdw.com/article/20m6.html