当前位置:首页 >> 理学 >>

Petri网系统的可达性研究


分类号 UDC

密级 编号

中国科学院研究生院 硕士学位论文
Petri 网系统的可达性研究
吴 文 渊

指导教师





研究员

中国科学院成都计算机应用研究所
申请学位级别 论文提交日期 培养单位 学位授予单位





学科专业名称 计算机软件及理论 论文答辩日期

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

答辩委员会主席

摘 要.......................................................................................................................................... II ABSTRACT .............................................................................................................................IV 前 言.........................................................................................................................................VI 第一章
§1.1 §1.2 §1.3 §1.4

背景知识 ............................................................................................................. 1
历史与发展 ............................................................................................................... 1 研究方法及应用 ...................................................................................................... 1 Petri 网的直观理解 ................................................................................................. 2 Petri 网的形式化描述 ............................................................................................ 2

第二章
§2.1 §2.2 §2.3 §2.4

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

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

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

第五章 综合分析方法 ................................................................................................... 34
§5.1 §5.2 §5.3 几种方法的综合比较 ........................................................................................... 34 综合分析方法描述................................................................................................ 34 综合分析方法总结................................................................................................ 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=( 2 M T ,∪,∩, φ ,MT),映射函数 ε:M T → B n

?M ∈ M T

?1,如果pi ∈ M ?i,pi = ? ?0,如果pi ? M

可达状态空间由该集合的特征函数来表示,只要是属于可达状态空间的点, 通过特征函数计算,输出为 1,反之亦然。所以无论状态空间的大小,一个特征 函数与可达标识集是一一对应的。特征函数: χψ : B n → B 的一个子集。 ?p ∈ B n

ψ ∈ 2 M ,既是 MT
T

?1,如果p ∈ψ p=? ?0,如果p ?ψ

比如:ψ = {( p 2 , p3 )( p2 , p7 )( p4 , p7 )} ,

χ ψ = p1 p 2 p 4 p 5 p 6 ( p 3 + p 7 ) + p 1 p 3 p 5 p 6 p 7 p 4
所以,求可达状态集就可以通过循环计算特征函数来得到。 算法: 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)的含 既是计算 From 对应的可达状态集中能实施 义是将变迁 t 作用于布尔函数 From,
VII

变迁 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. 2. 3. S∩T= φ (二元性); S∪T≠ φ (网非空); 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<i ≤ n, 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 新产生的 弧上标注 t。y 结点标注的标识 M ′ 可由 M 1′ 来计算, 1′ 满足于 M[t> M 1′ , M 即 ? s∈S,M 1′ (s)= M(s)-W(s,t)+W(t,s)。M ′ 的计算可区分为两种情况: 1) 从 r 到 y 的路上,如果存在标注 M ′′ 的结点 z≠y 且 ? s∈S: M 1′ (s)
4

第一章 背景知识

′ ? M 1 ( s ), 如果M 1′ ( s ) = M ′′( s ) ≥ M ′′ (s),那么 M ′ (s)= ? 其他 ?ω
2) 其它情况, M ′ = M 1′ 。 一个 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 P2

2 P4

t2 P5

2 2 系统状态为:x13x2x5 Pol(t1)=x12x2-x3x42 = f1 Pol(t2)=x42-x52 = f2 很明显,系统状态与多元多项式环上的单项式一一对应。 这时 t1 是可施实的,t1 实施后系统状态变为:

P1

2

1

P3

1 P2

2 P4 2 2 P5

变迁过程的代数表达: 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 , t j ) ei = ? ?0 if ( pi , t j ) ∈ F 其它

7

Petri 网系统的可达性研究

?W (t j , pi ) di = ? ?0

if (t j , 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 , ? , x n ) 1 ≤ t;

2、对每个 s, t1 , t 2 ∈ T ( x1 , x2 , ? , x n ), t1 ≤ t 2 ? t1 ? s ≤ t 2 ? s 关于单项式序的例子有很多,比如最常用的有字典序: 定义 2-3 在 T ( x1 , x2 , ? , x n ) 中,定义 x1 1 ? xn
d dn

≤ x1 1 ? x n n 当且仅当
e e

( d 1 , ? , d n ) = ( e1 , ? en ) 或者存在 1 ≤ i ≤ n 使得 d j = e j ,1 ≤ j ≤ i ? 1并且 d i < ei 。这种
序被称为字典序,我们常用 ≤ lex 表示。 很容易验证字典序是单项式序。我们可以给出一些例子。
8

第二章 Petri 网与代数系统的关系
2 3 2 1. x1 x2 > lex x 2 x3 。 3 6 3 4 2. x1 x2 x3 > lex x1 x2 x3 ;按照字典序我们有 x1 > lex x2 > lex ? > lex x n ,

另 一 方 面 , 在 变 元 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 , ? x n ] ,称(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 , ? x n ] 的子集, ?p ∈ P, p ≠ 0 我们有 1、如果 t ∈ T ( f ), 并且存在s ∈ T ( x1 , ? , x n) ,使得 s ? HT ( p ) = t ,而且 g= f ? a ? s ? p, 其中 a 是 t 在 f 中的系数 HC ( p )

2、如果存在 t ∈ T ( f ) 使得 f → p g [t ] , 则称 f 模 p 约化到 g 记做: f → p g 。 3、如果存在 p ∈ P, 使得 f → p g ,则称 f 模 P 约化到 g 记做: f → P g 4、如果存在 g ∈ k [x1 , ? , x n ] , g ≠ f 使得 f → P g ,则称 f 模 P 可约化。

9

Petri 网系统的可达性研究

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

? 使得 f → P g1 , g1 → P g 2 , ? , g n ?1→ P g n = g )。我们用 f → P g 表示。
如果一个多项式 f 模 P 是不可约化的,则称 f 模 P 的范式。很明显,只有当 T(f)中的每一项都不能被{HT(p) | p ∈ P } 中的任一项整除时, 模 P 才是不可约 f 化的。 对于每个多项式 f,都存在一个多项式 g 使得: f → P g 其中 g 是 f 模 P 是不可约化的,我们称 g 是 f 是模 P 的范式。 定理 2-2 假设 P= p1 , p2 , ? , p s 是 k [x1 , x2 , ? x n ] 的有限序列,f∈ k [x1 , x2 , ? x n ] , 则存在 f 模 P 的范式 g,和一组多项式{a1,a2,…,as} ? k [x1 , x2 , ? x n ] 满足 f = ∑ ai pi + g ,并且 max{HT( a i pi ) | 1≤i≤s, a i pi ≠0}≤HT(f)。
i =1 s

有了存在性人们自然要研究它的唯一性, 可惜在一般情况下不能保证范式的唯一 性,下面就是一个简单的反例。 例 设 f ( x, y ) = xy 2 ? x ∈ k [x, y ], p1 ( x, y ) = y 2 ? 1 , p2 ( x, y ) = xy + 1

令 P={p1(x,y),p2(x,y)}, ≤是 T(x,y)上的字典序。 我们有 f ( x, y ) → p1 0 另一方面又有 f ( x, y ) → p2 ( ? x ? y ) 这里 0, ( ? x ? y ) 都是 f ( x, y ) 模{p1(x,y),p2(x,y)}的范式,但它们是不同的。 二.Grobner 基及其算法 为了研究多项式环,就必须研究环上的理想,研究理想的结构,基是一个有 力的工具,第一个要问的问题就是基的个数,有限还是无穷。下面的定理给出了 一个明确的普遍而深刻的回答。 定 理 (Hilbert 基 定 理 ) 每 个 理 想 I ? k [x1 , x 2 , ? x n ] 都 有 一 个 有 限 基 , 即 存 在
f 1 , f 2 , ? , f t ∈ I 使得 I = f1 , f 2 , ? , f t 。这个有限集 G = { f 1 , f 2 , ? , f t } 称为 I 的 Grobner 基。(详细证明请见[13],[22]) Hilbert 基定理给出了有限基的存在性,接着下一个问题就是如何找到。要想 找到,首先必须知道目标的“样子” ,也就是 Grobner 基有什么样的性质。 Grobner 基性质定理

设 G 是 k [x1 , x2 , ? x n ] 的有限子集,给定单项式序≤,则下

列性质等价:
10

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

(1) G 是理想 G 的 Grobner 基; (2) 对每个 f ∈ G ,f 模 G 的范式为 0; (3) 对每个非零的多项式 f ∈ G ,f 模 G 是可约的。 定义 2-6 设 g1 , g 2 ∈ k [x1 , x 2 , ? xn ] , 是两个非零多项式。
a b a b 如果 HT ( g1 ) = x1a1 x2 2 ? xn n ,HT ( g 2 ) = x1b1 x22 ? x nn 令 ci = max{ai , bi } , i=1,…,n, c c 则称 x c = x1c1 x22 ? xnn 为 HT ( g1 ) 和 HT ( g 2 ) 的最小公倍式,

记作: LCM( HT ( g1 ) , HT ( g 2 ) )。 设 ti = HT ( g i ) , ai = HC ( g i ) , i=1,2 并且 t = si ti = LCM (t1 , t 2 ) ,其中 si ∈ T ( x1 , ? , xn ) 则称: S ( g1 , g 2 ) = a 2 s1 g1 ? a1 s2 g 2 为 g1, g2 的 S-多项式 例1. 设 f = x 3 y 2 ? x 2 y 3 + x , g = 3 x 4 y + y 2 ∈ R[x, y ] , 单项式序是分次字典

序,则 LCM ( HT ( f ), HT ( g )) = x 4 y 2 , S ( f , g ) = 3 x ? f ? y ? g = ?3x 3 y 3 + 3x 2 ? y 3 定理 2-3 假设 G 是 k [x1 , x2 , ? x n ] 的有限子集,并且 0?G,则下列性质等价: (1) G 是理想〈G〉的 Grobner 基; (2) ?g1 , g 2 ∈ G , S (g1 , g 2 ) → 0
G ?

有了这些性质,我们就可以计算 Grobner 基。
Grobner 基算法[34]:

设 F = { f1 , f 2 , ? , f t } ? k [x1 , x2 , ? x n ] , 理想 I = f1 , f 2 , ? , f t ,则下列算法可计算 理想 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 , g 2 ) = a 2 s1 g1 ? a1 s2 g 2 ,消掉两项,剩下的保持两单项式相减的 形式。又 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 基软件包 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 := [ 240 z 6 + 1600 z 3 + 9 z 9 ? 96 z 8, 640 x z 3 + 9 z 8 + 120 z 5 ? 96 z 7, x 2 ? 2 x z + 5, 80 y z 3 ? 3 z 8 + 32 z 7 ? 40 z 5, 3 y 2 ? 8 z 3 ]
> gbasis(WL,tdeg(x,y,z));

[ x 2 ? 2 x z + 5, ?3 y 2 + 8 z 3, 8 x y 2 + 3 y 3, 9 y 4 + 48 z y 3 + 320 y 2 ]

在 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+

73 8 73 7 73 5 z ? z + z ?5 640 60 48

在 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) 其中: 如果(t j , p i ) ∈ F并且( p i , t j ) ? F ?W (t j , p i ) ? x i = ?? W ( p i , t j ) 如果( p i , t j ) ∈ F并且(t j , p i ) ? F ? 其它 ?0 B. 当有位置是同时某个变迁的输入和输出时, 对应两个平移变换 fj+:(x1,x2,…,xn) 和 fj-:(y1,y2,…,yn) 其中:
?W (t j , p i ) xi = ? ?0 ?? W ( p i , t j ) yi = ? ?0 如果(t j , p i ) ∈ F 其它 如果( p i , t j ) ∈ 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) b)

( pi , t j ) ? F并且(t j , pi ) ? F , W(pi,tj)=0,W(tj,pi)=0,M(pi)=xi ( pi , t j ) ∈ F并且(t j , 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 , t j ) ? F并且(t j , 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 , t j ) ∈ F并且(t j , 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; K,W, M0) σ=M0t1M1t2…tnMn ∑= F, , 是∑的一个有限实施序列, 对应的变迁矩阵: TM=[V0 ,V1,…, Vn] 每个Vi 对应M i 。 定义 3-2 变迁选择矩阵: ,σ=M0t1M1t2…tnMn 是∑的一个有限 对于 P/T 网系统,∑=(S,T;F, K,W, M0)
16

第三章 能量优化模型

实施序列,平移变换集的个数为 t,ti 对应平移变迁 f ti ,其变迁选择矩阵为: TC=[X0 ,X1,…, Xn], X i 为 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 , k 2 , ? k n 使得:

′ Vn = V0 + ( f 1 , f 2 , ? f n ) ? (k1 , k 2 , ? k n )

(1)

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

定义 3-2 弱可达性:如果该方程组有非负整点解则称 M0 到 Mn 弱可达。 该问题转化为方程组的非负整点解的问题,这个问题又分为两个问题: a.是否有解 b.是否有非负整点解 二.弱可达性的判断 1.求解方程组 对于方程组,

( f1 , f 2 , ? f n ) ? (x1 , x2 , ? xn ) T=Vn-V0

先三角化,再求解

1) 如果解是零维解,计算出来看是否是非负整点解; 2) 如果解是流形解,设 xm,xm+1,…,xn 是自由变元,原问题化为不等式方程 组的整点解的问题: ? x1 = g1 ( x m , x m+1 , ? , x n ) ≥ 0 ? x = g ( x , x ,?, x ) ≥ 0 2 m m +1 n ? 2 ? ? ? (2) ? ? x = g ( x , x ,?, x ) ≥ 0 m ?1 m m +1 n ? m?1 ? x m ≥ 0, xm +1 ≥ 0, ? , xn ≥ 0 ? 其中:g1,g2,…,gm-1 为关于 xm,xm+1,…,xn 的线性表达式 2.不等式方程组的整点解问题的转换 定理 3-4 将 Max x1 = g1 ( xm , xm+1 , ? , xn ) 作为目标函数,

17

Petri 网系统的可达性研究



? g 2 ( xm , xm +1 , ? , xn ) ≥ 0 ? ? ?? ? ? g m?1 ( xm , xm +1 , ? , x n ) ≥ 0 作为限制条件,该问题转化为整数规划的问 ? x ≥ 0, x ≥ 0, ? , x ≥ 0 m +1 n ? 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 ,?, x ) ≥ 0 n ? 2 m m+1 ?? ? ? 作为限制条件, 该问题又转化为整数规划的问 ? g m?1 ( x m , xm+1 , ? , xn ) ≥ 0 ? ? xm ≥ 0, xm+1 ≥ 0, ? , xn ≥ 0 ? ? x1 , x2 , ? , xn 是整数 ?

题。Min D 就称为最短可达距离。其含义是从一种系统状态变迁到另一种系统 状态,在不考虑“越界”情况下,从 M0 达到 Mn 所需的最少步骤。也是 M0 到 Mn 的状态间距离下界。根据其定义,不难证明。同时解出 x1 , x2 , ? , x n ,即计算 这个状态间距离下界将作为能量优化模型中初始变 出每个变迁 ti 被实施的次数。 迁步数设定的一个参考量。 三.整数规划方法介绍[17] 1.数学模型 min f ( x ) = c1 x1 + c2 x2 + ? + cn xn ?a1,1 x1 + a1, 2 x2 + ? + a1,n xn ≤ b1 ? ?a 2,1 x1 + a 2, 2 x2 + ? + a 2,n x n ≤ b2 ? s.t. ??? ?a x + a x + ? + a x ≤ b m ,2 2 m ,n n m ? m ,1 1 ? xi ≥ 0且为整数,i = 1,2, ? , n ? 相应的线性规划问题(即不考虑整数条件)为 min f (x) =cX

(p)

18

第三章 能量优化模型

( p′ )

? AX ≤ b s,t. ? ?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 。整数规划(IP—Integer Optimizer)解决线性规划(LP—Linear Programming) 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 则称从状态 M0 到状态 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; K,W, M0), M1 可变迁到 M2 ? E< δ 。 ∑ F, 从 比如:当 K=1 时,我们可以取 f ( x ) = λ ? x ? ( x ? 1) ,由于 x 必需为整数很明显满 足上面两个要求。
三.总能量表达式

为了表达式的前后统一,我们做以下约定: s 表示该 Petri 网的位置的数量; t 表示 Petri 网的变迁的数量; m 表示状态间距离上界(变迁步骤数的上界); δ 表示能量阈值; 表示第 i 步的能量(所有分量对应的能量和); Ei 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+ ( f 1 , f 2 , ? f t ) ? (k1 , k 2 , ? k t ) T

21

Petri 网系统的可达性研究

? a1,1 ? ? a 2 ,1 令平移变换集 TS= ( f 1 , f 2 , ? f t ) = ? ? ? ?a ? s ,1

a1, 2 a2,2 a s,2
T

? a1,t ? ? ? a 2 ,t ? ? ,用向量 α i 表示第 i 步 ? ? a s ,t ? ?
i

实施的变迁 fpi =TS ? α i , α i ∈ e1 , e2 , ? , et
T T

{

},e =(0,…,0,1,0,…,0),表示第 i

个分量为零的单位向量,对应的变迁选择矩阵: TC = [α1 , α 2 , ? , α n ] 。 令 β i = ∑ α k , ci = ei ? V0 (初状态位置 i 的 token 数,0 或 1),
k =1 i

ζ 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 , Vi = V0+ TS ∑ α k =V0+ TS ? β i , Vn = V0+ TS ∑ α k = V0+ TS ? β n .
k =1 k =1 i n

总能量表达式: E= ∑ Ei = ∑∑ f ( e j ? Vi ) = λ ? ∑∑ e j ? Vi ( e j ? Vi ? 1) =
i =1 n

n

s

n

s

i =1 j =1

i =1 j =1

λ ? ∑∑ e j ? (V0 + TS ? β i )( e j ? (V0 + TS ? β i ) ? 1) =
i =1 j =1 n s

n

s

λ ? ∑∑ [c 2 + 2c jζ j ? β i + (ζ j ? β i ) 2 ? c j ? ζ j ? β i ] = j
i =1 j =1 n s

λ ? ∑∑ [2c jζ j ? β i + (ζ j ? β i ) 2 ? ζ j ? β i ] =
i =1 j =1 n s

λ ? ∑∑ [(ζ j ? β i ) 2 + ξ j ? β i ] .
i =1 j =1

对于 P/T 网系统,∑=(S,T;F, K,W, M0), 当 K=1 时能量优化模型:
Min E= λ ?

∑∑ [(ζ
i =1 j =1

n

s

j

? βi )2 + ξ j ? βi ]

(3)

ci = ei ? V0 , ζ i = ei ? TS , ξ i = ( 2 ? ci ? 1)ζ i 为已知量

S.t.

1. β i = ∑ α k , α i ∈ 0, e1 , e2 , ? , et ,为未知变量,0 表示 0 向量。
T T T k =1

i

{

}

22

第三章 能量优化模型

2. Vn = V0 + TS ? β n 注: n minD≦n≦m, 在检验弱可达性时虽计算出 minD, 1. 的取值有一定的不确定性, n 取 minD 时不可达,并不能说明其他情况不可达。通常可取较大的 n,多余 的步数, α i 就取 0 向量。 2.当有位置是同时某个变迁的输入和输出时,一个变迁对应于两个连续平移变 换,比如 ti 对应的变迁为 fi-,fi+ (在变迁矩阵中,对应于第 i 个和第 i+1 个列 向量);

? x1,1 ? ? x 2,1 令变迁选择矩阵:TC = [α1 , α 2 , ? , α n ] = ? ? ? ?x ? t ,1
fi- 则第 j+1 步发生 fi+ ,则 xi , j = 1,
n n

x1, 2 ? x1,n ? ? x 2 , 2 ? x 2,n ? ,假设第 j 步发生 ? ? ? ? ? x t , 2 ? x t ,n ? ?

xi +1, j +1 = 1 ;
n ?1 k =1

其连续性可用下面条件约束: ∑ xi ,k = ∑ xi +1,k = ∑ xi ,k ? xi +1,k +1 , 第一项为 fi- 发生
k =1 k =1

的次数,第二项为 fi+发生的次数,第三项为 fi- fi+同时为 1 的次数。可以证明, 当第 j 步发生 fi- 必有第 j+1 步发生 fi+,否则有 ∑ xi ,k ? xi +1,k +1 < ∑ xi ,k ;
k =1 k =1 n ?1 n

所以当有位置是同时某个变迁的输入和输出时,只需在能量优化模型的约束条件

中加上:

∑x
k =1

n

i ,k

= ∑ xi +1,k = ∑ xi ,k ? xi +1,k +1 。
k =1 k =1

n

n ?1

四.计算的复杂性 该能量优化模型其实是一个 0-1 二次规划,也是一个组合优化问题,变量 数目为: t × n 个,t 为 Petri 网系统的总变迁个数,n 为变迁步骤数。如果用穷举 法则搜索空间为 2 t ?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 是一个对象,它可以输入一组加权系数的 量,对它们进行求和,如果这个和达到或者超过了某个阈值,输出一个量。让 我们用符号标注这些功能,首先,有输入值以及它们的权系数: X 1 , X 2 , ? X n 和 W1 , W2 , ?Wn 。接着是求和计算出的 X iWi ,产生了激发层 a,换一种方法表示: a = ( X 1 ? W1 ) + ( X 2 ? W2 ) + ? + ( X nWn ) 阈值称为 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 = { ij } i=1,2,...,n j=1,2,...,n ,同时,有 n 维阈值向量θ:θ=[θ1,θ2,...θn]T W

一船而言,w 和θ可以确定一个唯一的离散 Hopfield 网络。

图 2 三神经元组成的 Hopfield 网络

26

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

考虑离散 Hopfield 网络的一个节点状态;用 Yj(t)表示第 j 个神经元,即节点 j 在时刻 t 的状态,则节点的下一个时刻(t+1)的状态可以求出如下:
?1 Y j (t + 1) = f [U j (t )] = ? ?0 ,U j ≥ 0 ,U j < 0

,其中 U j (t ) = ∑ WijYi (t ) + X j ? θ j
i =1

n

当 Wij 在 i=j 时等于 0, 则说明一个神经元的输出并不会反馈到它自己的输入; 这时,离教的 HopfieId 网络称为无自反馈网络。 当 Wij 在 i=j 时不等于 0,则说明—个神经元的输出会反馈到它自己的输入; 这时,离散的 Hopfield 网络称为有自反馈的网络。

离散 Hopfield 网络有二种不同的工作方式: 1.串行(异步)方式 在时刻 t 时,只有某一个神经元 j 的状态产生变化,而其它 n-1 个神经元的状态 ?n ? 不变这时称串行工作方式。并且有 Y j (t + 1) = f ?∑ WijYi (t ) + X j ? θ j ? ? i =1 ?
Yi(t+1)=Yj(t) i≠j。

?n ? 在不考虑外部输人时,则有 Y j (t + 1) = f ?∑ WijYi (t ) ? θ j ? ? i =1 ?
2.并行(同步)方式 在任一时刻 t,所有的神经元的状态都产生了变化;则称并行工作方式。并且有

?n ? Y j (t + 1) = f ?∑ WijYi (t ) + X j ? θ j ? j = 1,2, ? , n ? i =1 ? ?n ? 在不考虑外部输入时,则有 Y j (t + 1) = f ?∑ WijYi (t ) ? θ j ? ? i =1 ?
j = 1,2, ? , n

对于一个网络来说, 稳定性是一个重大的性能指标。 对于离散 Hopfield 网络, ... T 其状态为 Y(t):Y(t)=[Y1(t),Y2(t), ,Yn(t)] 如果,对于任何△t>0.当神经网络从 t =0 开始,有初始状态 Y(0);经过有限时刻 t,有:Y(t+△t)=Y(t) 则称网络是稳 定的。在串行方式下的稳定性称之为串行稳定性。同理,在并行方式的稳定性称 之为并行稳定性。在神经网络稳定时,其状态称稳定状态。从离散的 Hopfield 网络可以看出:它是一种多输入,含有阈值的二值非线性动力系统。在动力系统 中,平衡稳定状态可以理解为系统的某种形式的能量函数在系统运动过程中,其 能量值不断减小,最后处于最小值。 对 Hopfield 网络引入一个 Lyapunov 函数,即所谓能量函数:
1 E = ( ? )∑∑ WijYiY j ? ∑ X jY j + ∑ θ jY j 2 i j j j (4)

27

Petri 网系统的可达性研究

1 对于神经元 j,其能量函数可表示为 E j = ( ? )∑ WijYiY j ? X jY j + θ jY j 2 i 即有: E = ∑ E j 。神经元 j 的能量变化量:△Ej=
j

? 1 ?E j Yj Yj Yj ? Y ?E ?Y j = ?Y j = ?( ? )∑ (WijYi + Wij i Y j ) ? X j +θ j ? ?Y j ?Y j ?Y j ?Y j ?Y j ?Y j ?Y j ? ? 2 i ? ?

如果存在条件

Wii=0,i=1,2,...,n; Wij = W ji i=1,2,...,n

j=1,2,...,n 则有:

? n ? ? ? △Ej= ?? ∑WijYi ? X j + θ j ? ?Y j = ? ? ∑ WijYi + X j ? θ j ? ?Y j ? i ? ?i =1,i ≠ j ?
如果,令 Uj=Σ Wij Yi+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 是对称矩阵这一条件。 连续状态Hopfield Hopfield神经网络 2. 连续状态Hopfield神经网络 连续 Hopfield 网络的拓朴结构和离散 Hopfield 网络的结构相同。 这种拓朴结 构和生物的神经系统中大量存在的神经反馈回路是相一致的。在连续 Hopfield 网络中,和离散 Hopfield 网络一样,其稳定条件也要求 Wij = W ji 。连续 Hopfield 网络和离散 Hopfield 网络不同的地方在于其函数 g 不是阶跃函数,而是 S 形的 连续函数。一般取 g(u)=1/(1+e-u) 连续 Hopfield 网络在时间上是连续的.所以,网络中各神经元是处于同步方 式工作的。 考虑对于一个神经细胞, 即神经元 j, 其内部膜电位状态用 uj 表示. 细 胞膜输入电容为 Cj,细胞膜的传递电阻为 Rj,输出电压为 Vj,外部输入电流用 Ij 表示,则连续 Hopfield 网络可用图 4 所示的电路表示。
n U j (t ) ? dU j (t ) Cj = ∑ WijV j (t ) ? + Ij ? dt Rj i =1 ? ?V (t ) = g (U (t )) j = 1,2, ? , n j ? j

其中: n 是神经网络神经元的个数
28

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

vj(t)为输出电位; Uj(t)为输入电位。

图 4 连续 Hopfield 网络的电路形式 对于连续 Hopfield 网络,Hopfield 给出如下稳定性定理: 给出能量函数 E(t),

1 1 V j ( t ) ?1 E (t ) = ( ? )∑∑ WijVi (t )V j (t ) ? ∑V j (t ) I j + ∑ ∫ g (V )dV 0 2 i j j j Rj
其中:g-1(v)是 Vj(t)=gj(uj(t))的反函数。 如果连续 Hopfield 网络中神经元传递函数是单调增长的连续并有界函数,并且 dVi (t ) dE (t ) dE (t ) Wij=Wji,则有 ≤ 0 ; 当并且仅当 = 0 时有 = 0。 dt dt dt 这个定理的意义可以解释如下:当网络神经元的传递函数是 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; K,W, M0) F, 当 K=1 时 能量优化模型:

? a1,1 ? ? a 2 ,1 令平移变换集:TS= ( f 1 , f 2 , ? f t ) = ? ? ? ?a ? s ,1
Min E= λ ?

a1, 2 a2,2 a s,2

? a1,t ? ? ? a 2 ,t ? ? ? ? a s ,t ? ?

∑∑ [(ζ
i =1 j =1

n

s

j

? βi )2 + ξ j ? βi ]

ci = ei ? V0 , bi = ei ? Vn ? c i , ζ i = ei ? TS , ξ i = ( 2 ? ci ? 1)ζ i 为已知量 S.t. 1. β i = ∑ α k , α i ∈ 0, e1 , e2 , ? , et ,0 表示 0 向量, ei 表示标准单位向
T T T
k =1 i

{

}

量, ei = (0, ? ,0,1,0 ? 0) 第 i 个分量为 1,其它的为 0。

? x1,1 ? ? x 2,1 TC = [α1 , α 2 , ? , α n ] = ? ? ? ?x ? t ,1
2. Vn=V0+ TS ? β n

x1, 2 ? x1,n ? ? x 2 , 2 ? x 2,n ? 为未知变量, xi,j=0 或 1. ? ? ? ? ? x t , 2 ? x t ,n ? ?

3. 当有位置是某个变迁的输入和输出时, ∑ xi ,k = ∑ xi +1,k = ∑ xi ,k ? xi +1,k +1 。
k =1 k =1 k =1

n

n

n ?1

我们用 t×n 个神经元来表示变迁选择矩阵 TC 中的各个未知变量并要满足以 上三条约束,下面我们利用罚函数的思想我们构造出神经网络计算的能量函数。

ζ j ? β i = e j ? TS ? β i = ( a j1 , a j 2 , ? , a jt ) ? ( x11 + ? + x1i , x 21 + ? + x2i , ? , xt1 + ? + xti )
= a j1 ( x11 + ? + x1i ) + a j 2 ( x 21 + ? + x2i ) + ? + a jt ( xt1 + ? + xti )

ξ j ? β i = ( 2 ? c j ? 1)ζ j ? β i =
( 2 ? c j ? 1)( a j1 ( x11 + ? + x1i ) + a j 2 ( x 21 + ? + x 2i ) + ? + a jt ( xt1 + ? + xti ))

对应的神经网络能量函数:
30

第四章 可达性的神经网络解法
n t ?1 t

E = λ1 ?

∑∑ [(ζ j ? β i ) 2 + ξ j ? β i ] + λ2 ∑ (bi ? ∑∑ a ik x kj ) 2 + λ3 ∑∑
i =1 j =1 i =1 k =1 j =1

n

s

s

t

n

i =1 x =1 y = x +1

∑x

x ,i

x y ,i +

λ4 {( ∑ xi ,k ? ∑ xi +1,k ) 2 + ∑ xi ,k ? ∑ xi ,k ? xi +1,k +1}
k =1 k =1 k =1 k =1

n

n

n

n ?1

(5)

第一项是目标函数,能量优化模型中的能量;第二项为弱可达性约束;第三项为 每次只实施一次变迁的约束;第四项为当出现自反馈变迁时的变迁连续性保证。 二.确定连接权和偏置 通过与 Hopfield 网络引入一个 Lyapunov 函数,即所谓能量函数:
1 E = ( ? )∑∑ WijYiY j + ∑ θ iYi ,Yi 为神经元 i 的输出。 2 i j i

因为 a ij = 0,1或 ? 1,x ij = 0或1,所以a ij = a ij ,x ij = x ij 。
2 2

第一项中: x kp ? xlq的系数 为 λ1 ∑ (n ? q + 1)a jk ? a jl
j =1

s

其中 x kp,xlq是不同的变量 ,p≤q。 x kp的系数为 λ1 ∑ (n ? p + 1)( a jk + ( 2c j ? 1)a jk )
j =1 s

第二项中: x kp ? xlq的系数 为 λ2 ∑ a jk ? a jl
j =1

s

其中 x kp,xlq是不同的变量 。 x kp的系数为 λ2 ∑ ( a jk ? 2b j * a jk )
j =1 s

?1 第三项中: x kp ? xlq的系数 为 λ3δ pq (1 ? δ kl ) , 其中 δ ij = ? ?0

如果i = j 其他

当第 i,i+1 是自反馈变迁分拆成的两个变迁时, x kp ? xlq的系数 为:

λ 4 (δ k ,i ? δ l ,i ? (1 ? δ p , q ) + δ k ,i +1 ? δ l ,i +1 ? (1 ? δ p , q ) ? δ k ,i ? δ l ,i +1 ? δ k ,i ? δ l ,i +1 ? δ p +1, q
x kp的系数为 : λ 4 (2δ k ,i + δ k ,i +1 ) 因此,神经元 (k,p) 与 (l,q) 间的连接权 Wkp ,lq 和神经元 (k,p)的偏置 θ kp 分别为:

31

Petri 网系统的可达性研究
s s

Wkp ,lq = -2×( λ1 ∑ ( n ? q + 1)a jk ? a jl + λ 2 ∑ a jk ? a jl + λ3δ pq (1 ? δ kl ) )
j =1 j =1

(6)

θ kp = λ1 ∑ (n ? p + 1)( a jk + ( 2c j ? 1)a jk ) + λ2 ∑ ( a jk ? 2b j a jk )
j =1 j =1

s

s

(7)

当第 i,i+1 是自反馈变迁分拆成的两个变迁时,神经元 (k,p) 与 (l,q) 间的连接 权 Wkp ,lq 和神经元 (k,p)的偏置 θ kp 分别为:
Wkp ,lq =

- 2 × ( λ1 ∑ ( n ? q + 1)a jk ? a jl + λ 2 ∑ a jk ? a jl + λ3δ pq (1 ? δ kl ) ) +
j =1 j =1

s

s

λ 4 (δ k ,i ? δ l ,i ? (1 ? δ p , q ) + δ k ,i +1 ? δ l ,i +1 ? (1 ? δ p , q ) ? δ k ,i ? δ l ,i +1 ? δ k ,i ? δ l ,i +1 ? δ p +1, q (8) θ kp = λ1 ∑ (n ? p + 1)( a jk + ( 2c j ? 1)a jk ) +
j =1 s

λ2 ∑ ( a jk ? 2b j a jk ) + λ 4 (2δ k ,i + δ k ,i +1 )
j =1

s

(9)

三.相关参数的确立 由于参数 λ1 , λ2 , λ3 , λ 4 的不同取值,会影响能量函数的峰值分布,也反应了不 同约束对能量的影响。比如:λ1 很大,其他相对较小,那么神经元状态在调整过 程中会优先满足该约束。 我们在神经元的初始状态参数设置上,采用随机数方 法,因为目前还没有找到一个规则来指导这些参数的选取,当然我们可以经过多 次实验的经验来调整。 四.存在的问题 由于 Hopfield 神经网络的能量函数是朝着梯度减小的方向变化,一旦能量函 数陷入到局部极小值,它将不能自动跳出局部极小点,到达全局最小点,这和神 经元的初始状态有关,不同的初始状态可能会到达不同的局部极小点。 利用神经网络来解能量优化模型,必须要求容量函数 K 有界。因为能量映射 函数必须是多项式时,神经网络才能求解,又多项式在正无穷大时不可能是一常 数,这时罚函数机制失效,所以要求容量函数 K 有界。而这个要求是符合客观 实际的,token 数表示资源,而资源通常是有限的,存储资源的容量也应该是有 限的。 §4.4 算法的实现

一.算法的软件实现 我们使用 Matlab 编写的算法来模拟 Hopfield 神经网络,现给出算法的流程
32

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

图,见图 5。完整的程序请见附录 2。 二.算法的硬件实现 利用软件模拟,只能分析神经网络求解问题的可行性和正确性,但在实践中 效率很低,因为本来是大规模的并行神经计算,却通过串行的位运算实现,并不 能体现神经计算的优势,所以神经网络的硬件实现是非常重要的。从现在的技术 手段来看,利用现有的,以发展得相当完善的半导体大规模集成电路技术,是用 硬件方式实现神经网络信息处理和神经计算的比较可行的途径。 神经网络芯片是 以芯片的形式实现神经网络功能。神经网络芯片最大的优点是处理速度快,且易 于满足实时性要求。目前已有基于神经网络芯片的协处理器卡提供实际应用。 1985 年 Psaltis 和 Farhat 发表了第一篇用光学方法实现神经网络的理论[27]。 与电信号相比,光作为信息传递的媒体具有一些独特的性能。它的信号间不容易 相互影响,易于实现高密度的并行传递,配线可以交叉和重叠,进行三维配线, 不易受外界电气噪声的干扰。 最关键的神经网络中最基本的矩阵与矢量相乘的运 算可以很方便地通过光学器件完成。 用发光元件所发出的光对应于输入矢量 X,它通过圆筒状透镜于输出列方向 对应,棱镜的透过率与权矩阵 W 一一对应。让圆筒透镜在行向量方向聚焦,所 得到的就是输入 X 与矩阵相乘的输出矢量 Y。图 6 是利用光学实现矩阵矢量相 Frahat 等在此基础上加上相应的电子放大回路, 就可以实现 Hopfield 乘的原理图。 网络模型。
λ1 , λ 2 , λ3 , λ4 , n 等参数的确定

平移变换集 TS 赋值

图 5 Hopfield 神经网络 算法流程图

变迁选择矩阵 TC 初始化

计算权值和阈值

改变神经元状态

计算总能量 E

计算各类约束的误差 当 E=0, 或 能量变化 量=0 当 E>0 并且能量变化不为 0

输出 TC,E 和各类约束误差

33

Petri 网系统的可达性研究

权矩阵 W W11 y1 y2 感光元件 输出矢量

x1 x2 发光元件 输入矢量 图 6 光学实现矩阵矢量相乘的原理

第五章 综合分析方法

§5.1

几种方法的综合比较

我们已经就 Petri 网系统的可达性问题本身以及解决方法做了介绍和分析, 穷举法简单易懂,问题解决最彻底,但计算的时间和空间复杂度都随问题规模呈 指数增加,即使判断一个是否可达的特殊问题,也有可能将整个状态空间都搜索 一遍。 而计算代数的方法则避免了这一问题, 只需计算一次变迁多项式的 Grobner 基, 之后判断一个是否可达的问题只需作一次简单的多项式对于 Grobner 基的约 化,但缺点在于并没有构造出实施序列,而且当系统不可逆时,这个方法只能作 为可达性判断的一个必要条件,当 K 有界时可能不适合,更主要的是这个方法 没法判断系统的可逆性。能量优化模型能构造出实施序列,并且不依赖于系统的 可逆性,但缺点在于计算时间依赖于神经网络的能量函数的收敛速度,而收敛速 度依赖于初始值,各种参数等多个不确定因素。而且每判断一个是否可达的特殊 问题, 都要用神经网络的能量函数计算一次或多次。 造成平均一次判断代价太高。 下面的方法是综合了以上方法而提出的一个折中方法。 §5.2 综合分析方法描述

一.系统可逆性判断 从上一节分析来看,计算代数的方法效率最高,计算一次多项式的 Grobner 基,之后计算量就很小了,但关键就在于系统的可逆性,单靠计算代数方法自身 是不能解决这一问题的, 而能量优化模型可以不依赖于系统的可逆性来判断 Petri 网系统的可达性,我们就从此入手来作分析。
34

第五章 综合分析方法

根据系统可逆的定义,对于 P/T 网系统,∑=(S,T;F, K,W, M0),系统可逆 就是: ? M∈[M0>,=> M0∈[M>. 假设 M0[σ> Mi , Mi[ti> Mi+1,如果系统可 ’ ’ ’ 逆则 Mi+1[σ > M0 , 即 Mi+1[σ σ> Mi,所以σ σ: Mi+1 Mi,但 ti 的可逆性依 赖于 Mi,而我们在判断 ti 的可逆性时并不知道 Mi,如果存在 ti-1:将 ti 的输出通 过一有限变迁序列变为 ti 的输入,则可充分保证 Mi+1 Mi。所以我们引入变迁 可逆的概念。 定义 5-2:如果存在一有限变迁序列,将 ti 的输出状态变为 ti 的输入状态,则称 ti 是变迁可逆的。这一有限变迁序列记为:ti-1。如果每个变迁都是变迁可逆的, 则称该系统是完全可逆的。 在前面的章节中,我们引入了弱可达性概念来得到可达性的必要条件,在此 我们由它衍生出弱可逆条件。 定义 5-3:如果 ti 的输出状态到 ti 的输入状态是弱可达的,则称 ti 是弱变迁可逆 的。如果每个变迁都是弱变迁可逆的,则称该系统是弱可逆的。 很明显,有以下定理: 定理 5-1:系统完全可逆 =>系统可逆 =>系统弱可逆。 系统可逆这一性质对于该系统来说是非常重要的,能保证系统的活性,无死锁, 安全性。 定理 5-2:对于完全可逆 P/T 网系统,从 M1 可变迁到 M2 ? a1-a2 属于变迁双 向式构成的理想。 二.计算 Grobner 基和基的反演表示 由第二章的计算代数方法可知,先计算系统的 Grobner 基,再求 Grobner 基 的反演表示(也就是用原多项式来表示每个基),其目的是为了在不知道系统是否 可逆的情况下结合状态可逆条件判断状态的可达性。 给定一个 Petri 网系统 PN=(S, T, F; K,W,M0) K= ω ; 对应 Petri 网代数系统 PNA=(X,H,a0)。H={h1,h2,…,hn},H 的 Grobner 基为:G={g1,g2,…,gk}, 计算 Grobner 基及其反演表示算法: 设 F = { f1 , f 2 , ? , f t } ? k [x1 , x2 , ? x n ] , 理想 I = f1 , f 2 , ? , f t ,则下列算法可计算 理想 I 的 Grobner 基 G 及其反演表示。 Input: F={f1,f2,…,fs} Output: G={g1,g2,…,gt} ? F , G is Grobner basis of〈F〉 H={(gi , gi 对应的反演表达式)} Begin G:=F ; H=Φ 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 exp:=约化表达式
35

Petri 网系统的可达性研究

if h0≠0 then B:=B∪{{g,h0}| g∈G} G:=G∪{h0} exp0:=根据 H ,将 exp 中的 gi 置换为 gi 对应的反演表达式 H:=H∪{(h0 , exp0)} End 由该算法,给了两个状态 M1, M2, 分别对应单项式 a1, a2。可得到 a1-a2=

∑c g = ∑d h
i i i i

i i

, 如果为一正表示,则存在一个有限变迁序列使得系统从 M1 状

态变迁到 M2 状态;如果不是正表示,则必须判断系统的可逆性;如果系统完全 可逆,则可达;如果系数不是完全可逆,则需要进一步分析判断。 三.状态可逆条件 状态可逆性的引入是为了解决表达式中有负系数时可达性的判断。 假设 hi 的系数为负,状态可逆性就是指变迁是弱变迁可逆的,而不是完全可逆 的,其原因是变迁过程“越下界” ,也就是变迁过程中有状态分量小于 0,使得 即使达到最小值,总能量也较大,这时构造变迁过程,找出过程中有各状态分量 最小的值(负 token 数),这些 token 数构成的状态叫该变迁附加状态,该变迁起 始状态加上附加状态,这样就能使该变迁可逆,这时就称这些加上的 token 数为 该变迁的状态可逆条件。 假设状态差的变迁多项式表达式中的某一项为负系数,如果该变迁对应的状 态可逆条件覆盖该变迁的系数项,则该项有变迁多项式的正表示。当将所有负项 换为变迁多项式正的表示,就构造出 M1 到 M2 的不“越下界”的变迁过程。 我们必须指出构造出 M1 到 M2 的变迁过程不一定最短, 可能很长。 更关键的 是计算代数方法要求容量函数无界, 而基于神经网络的能量优化模型要求容量函 数有界,所以如果构造出 M1 到 M2 的变迁过程“越上界”就只有通过神经网络 直接构造了。 §5.3 综合分析方法总结

综上所述,我们给出综合分析方法的整个分析流程: 0. 建立能量优化模型和计算平移变换集 TS。 1. 系统的可逆性判断。 a. 对于每个变迁先通过整数规划方法作弱可逆性判断,满足则计算状态间 距离下界,并到下一步,否则到 5-e; b. 对于每个变迁通过神经网络作强可逆性判断,满足则到 2,否则下一步; c. 再通过上一步的神经网络计算得每个变迁的状态可逆条件。 2. 将 Petri 网映射成代数系统。 3. 计算变迁多项式的 Grobner 基及其基的反演表达式(当 K 有界时必须注意基 的反演表达式中变量的次数不能越界)。 4. 对于需要判断可达性的某个状态, 如果系统满足强可逆条件,则使用 Grobner 基作可达性的完全判断准则,到 7,输出相应的结果;否则,到下 一步。
36

第五章 综合分析方法

5. 对于需要判断可达性的某个状态, 系统不满足强可逆条件: a. 计算该状态与初状态的差被 Grobner 基约化的范式, 范式为 0, 则下一步, 否则到 6,输出“不可达” b. 计算该状态与初状态的差的变迁多项式表达式; c. 如果没有负系数的项,则可达,构造实施序列,否则下一步; d. 如果负系数的项满足状态可逆条件,则可达,构造实施序列,否则下一 步; e. 直接通过神经网络计算其可达性。 6. 输出结果,结束。

37

Petri 网系统的可达性研究

第六章 应用实例分析

P3 t1 t10 t3 P1 t5 t8 P6 t11 t2 P4 t9 P2 t4 t6 P7

发方状态
P5 t7

收方状态

信道状态 图 7 停等协议的 Petri 网模型 我们以停等协议为例来说明,综合分析方法的应用,停等协议是一个比较简 单的计算机网络链路层数据传输协议。 由于每发送一个数据帧就停止等待, 0, 用 1 作数据帧的发送序号。 发送结点: 1.从主机取一个数据帧 2.V(s)=0, 发送状态变量初始化 3.N(s)=V(s), 写入发送序号,将数据帧存入缓冲区 4.发送缓存区中的数据帧 5.设置超时定时器(适当的超时时间 tout) 6.等待 7.如果收到确认帧 ACK, 则从主机取出下一数据帧,V(s)=[1-V(s)] goto 3. 8.如果超时,则 goto 4. 接收结点: 1.V(r)=0, 接收变量初始化,(接收变量:欲接收的数据帧发送序号) 2.等待
38

第六章 应用实例分析

3.收到一帧,如果 N(s)=V(r), 则下一步;否则丢弃该帧 goto 6. 4.将收到的数据帧的数据部分送主机。 5.V(r)=[1-V(r)]. 6. 发送确认帧 ACK, goto 2. P1: 发方 发 0 序号帧后的等待状态 P2: 发方 发 1 序号帧后的等待状态 P3: 0 序号帧在信道的状态 P4: ACK 在信道的状态 P5: 1 序号帧在信道的状态 P6: 收方 期望收 1 序号帧的等待状态 P7: 收方 期望收 0 序号帧的等待状态 t1: 发方 发 0 序号帧 t2: 发方 发 1 序号帧 t3: 发方 发 0 序号帧后超时处理 t4: 发方 发 1 序号帧后超时处理 t5: 0 序号帧在信道丢失处理 t6: ACK 在信道丢失处理 t7: 1 序号帧在信道丢失处理 t8: 期望收 1 序号帧而收到 0 序号帧的处理 t9: 期望收 0 序号帧而收到 1 序号帧的处理 t10: 期望收 0 序号帧又收到 0 序号帧的处理 t11: 期望收 1 序号帧又收到 1 序号帧的处理 对应的 Petri 网模型 PN=(S,T; F, M0) 其中:S={ P1 , P2 , P3 , P4 , P5 , P6 , P7}, T={ t1 , t2 , t3 , t4 , t5 , t6 , t7 , t8 , t9 , t10 , t11}, F 表示位置与变迁间的连接方式, M0=(P1 , P3 , P7) 一.建立能量优化模型 1.计算 fi 表示变迁 ti 对应的平移变换

t1 → f1 = (1,?1,1,?1,0,0,0)

t 2 → f 2 = ( ?1,1,0,?1,1,0,0)

t3 → f 3? = ( ?1,0,0,0,0,0,0) 和 f 3+ = (1,0,1,0,0,0,0)

t 4 → f 4? = (0,?1,0,0,0,0,0) 和 f 4+ = (0,1,0,0,1,0,0)
t5 → f 5 = (0,0,?1,0,0,0,0) t7 → f 7 = (0,0,0,0,?1,0,0) t8 → f 8? = (0,0,?1,0,0,?1,0) 和 f 8+ = (0,0,0,1,0,1,0) t9 → f 9? = (0,0,0,0,?1,0,?1) 和 f 9+ = (0,0,0,1,0,0,1) t10 → f10 = (0,0,?1,1,0,1,?1) 初状态 M0 映射为 C=(1,0,1,0,0,0,1)
39

t6 → f 6 = (0,0,0,?1,0,0,0)

t11 → f11 = (0,0,0,1,?1,?1,1)

Petri 网系统的可达性研究

2.平移变换集 TS= ( f1 , f 2 , ? f 11 ) ? 1 ?1 ?1 ? 0 ??1 1 ? 1 0 0 ? =??1 ?1 0 ? 0 1 0 ? 0 0 ? 0 ? 0 0 0 ? 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 ? ? 0 0 ? ?1 0 ? ? 1 1 ? 0 ? 1? ? 1 ? 1? ?1 1 ? ? 0

0 ?1 1 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 ?1 0 0 ?1 0 0 ?1 0 0 1 0 0 ?1 0 0 0 0 0 0 0 0 0

0 0 0 0 1 0 0 ?1

?1 1 0 0 0 0 ?1 1

二.系统的可逆性判断 1.对每个变迁先通过整数规划方法作弱可逆性判断 1) 计算关联矩阵
C = [ci , j ] (1 ≤ i ≤ 7,1 ≤ j ≤ 11) = W (t j , si ) ? W ( si , t j ) 0 0 0 0 0 0 ? ? 1 ?1 0 0 0 ? ? 0 0 0 0 0 0 ? ??1 1 0 0 0 ? 1 0 1 0 ?1 0 0 ?1 0 ?1 0 ? ? ? =??1 ?1 0 0 0 ?1 0 1 1 1 1 ? ? 0 1 0 1 0 0 ? 1 0 ? 1 0 ? 1? ? ? 0 0 0 0 0 0 0 0 1 ? 1? ? 0 ? 0 0 0 0 0 0 0 0 0 ?1 1 ? ? ? 2) 应用 Maple 软件和 Matlab 软件作弱可逆性判断

t1 的弱可逆性: CXT = b1T , X= (x1 , ? , x11 ) ,
b1=col(mulcol(c,1,-1),1)= ( ?1,1,?1,1,0,0,0) , xi 是非负整数 利用 Maple 软件解方程得: > with(linalg): > linsolve(c,b1); [-1+_t[4],_t[4],_t[5],_t[6],_t[4]+_t[5]-_t[1]-_t[3], -2*_t[4]+_t[1]+_t[2]+2*_t[3],_t[4]+_t[6]-_t[2]-_t[3],_t[1],_t[2], _t[3], _t[3]] 将 x6 作为目标函数: x1= -1+_t[4] 解下列整数规划问题。 max (x1) s.t. x2= _t[4]>=0 x3= _t[5]>=0 x4= _t[6]>=0 x5= _t[4]+_t[5]-_t[1]-_t[3]>=0
40

第六章 应用实例分析

x6= -2*_t[4]+_t[1]+_t[2]+2*_t[3]>=0 x7= _t[4]+_t[6]-_t[2]-_t[3]>=0 x8= _t[1]>=0 x9= _t[2]>=0 x10= _t[3]>=0 x11= _t[3]>=0 x1,x2,x3,x4,x5,x7,x8,x9,x10,x11 为整数 先调用 Matlab6.1 的线性规划软件包,解对应的线性规划问题。问题可化为 如下形式:

函数调用格式 x = linprog(f,A,b,Aeq,beq,lb,ub),所以对应的求解过程如下 f = [0,0,0,1,0,0]; A = [ -1, 0, -1, 1, 1,0; 1, 1, 2, -2, 0, 0; 0,-1,-1,1,0,1]; b=[0,0,0]; lb=[0,0,0,0,0,0]; x=linprog(-f,-A,-b,[ ],[ ],lb,[ ])-1; 求解结果为:x = 1.0e+008 * 2.8964 0.0111 0.0109 1.9819 1.8298 1.1639 表示 x6 无最大值,即可取到非负整数。所以 t1 是弱可逆的。
x1 + x 2 + ? + x11 = -1+2*_t[4]+2*_t[5]+2*_t[6]+_t[1]+_t[2]+2*_t[3] 对应的状态间距离下界: f = [1,1,2,2,2,2]; A = [ -1, 0, -1, 1, 1,0; 1, 1, 2, -2, 0, 0; 0,-1,-1,1,0,1; 0,0,0,1,0,0]; b=[0,0,0,1]; lb=[0,0,0,0,0,0]; x=linprog(f,-A,-b,[ ],[ ],lb,[ ]); f*x-1 Optimization terminated successfully. min = 3

也就是可达过程至少三步(由后面给出的可达树可知 t1 的逆变迁

41

Petri 网系统的可达性研究

三个变迁的合成)。 同理 t 2 的弱可逆性: b2 := [1, -1, 0, 1, -1, 0, 0], xi 是非负整数 ,解方程得: > linsolve(c,b2); [1+_t[3], _t[3], _t[4], _t[5], _t[6], -1-_t[3]+_t[4]-_t[6]+_t[2]+_t[1], _t[3]+_t[5]+1-_t[1]-_t[2], 1+_t[3]+_t[4]-_t[6]-_t[2], _t[1], _t[2], _t[2]] 取 x6 为目标函数, 化为规划问题后用 Matlab 求解, 得到 x6 无最大值所以 t 2 是 弱可逆的。 x1 + x 2 + ? + x11 =3*_t[3]+3*_t[4]+2*_t[5]+2-_t[6]+_t[1]+_t[2] 对应的状态间距离下界:3
t3 和 t5 ; t 4 和 t7 正好互为弱可逆的。 t6 的弱可逆性: CX T = b T , b= (0,0,0,1,0,0,0) , xi 是非负整数 ,解方程得:

[-_t[1]+_t[3]+_t[5]+_t[6],-_t[1]+_t[3]+_t[5]+_t[6], _t[1]-_t[3]-_t[5]+_t[2]+_t[4], _t[1], _t[2], -1+_t[4]+2*_t[1]-2*_t[3]-_t[5], _t[3], _t[4], _t[5], _t[6], _t[6]]

取 x6 为目标函数, 化为规划问题后用 Matlab 求解, 得到 x6 无最大值所以 t6 是 弱可逆的。 x1 + x 2 + ? + x11 =4*_t[6]-1+2*_t[2]+3*_t[4]+2*_t[1]+_t[5] 对应的状态间距离下界:2
t8 的弱可逆性: CX T = b T , b =(0, 0, 1, -1, 0, 0, 0), xi 是非负整数 ,解方程得: ([-_t[1]+_t[3]+_t[5]+_t[6], -_t[1]+_t[3]+_t[5]+_t[6], _t[1]-_t[3]-_t[5]+1+_t[2]+_t[4], _t[1], _t[2], 2*_t[1]-2*_t[3]-_t[5]+1+_t[4], _t[3], _t[4], _t[5], _t[6], _t[6]]

取 x6 为目标函数, 化为规划问题后用 Matlab 求解, 得到 x6 无最大值所以 t8 是 弱可逆的。 x1 + x 2 + ? + x11 =4*_t[6]+2+2*_t[2]+3*_t[4]+2*_t[1]+_t[5] 对应的状态间距离下界:2
t9 的弱可逆性: CX T = b T , b =(0,0,0,-1,1,0,0), xi 是非负整数 ,解方程得: [_t[1], _t[1], _t[2]-_t[4]-_t[6]-1+_t[3]+_t[5], _t[2], _t[3], -1+_t[5]-_t[6]+2*_t[2]-2*_t[4], _t[4], _t[5], _t[6], _t[1]+_t[2]-_t[4]-_t[6]-1, _t[1]+_t[2]-_t[4]-_t[6]-1]

取 x7 为目标函数, 化为规划问题后用 Matlab 求解, 得到 x7 无最大值所以 t9 是

42

第六章 应用实例分析

弱可逆的。 x1 + x 2 + ? + x11 =4*_t[1]+6*_t[2]-4*_t[4]-3*_t[6]-4+2*_t[3]+3*_t[5] 对应的状态间距离下界:2 t10 的弱可逆性: CX T = b T , b =(0,0,1,-1,0,-1,1), xi 是非负整数 ,解方程得:
[-_t[1]+_t[3]+_t[5]+_t[6], -_t[1]+_t[3]+_t[5]+_t[6], _t[1]-_t[3]-_t[5]+_t[2]+_t[4], _t[1], _t[2], 2*_t[1]-2*_t[3]-_t[5]+_t[4], _t[3], _t[4], _t[5], -1+_t[6], _t[6]]

取 x3 为目标函数, 化为规划问题后用 Matlab 求解, 得到 x3 无最大值所以 t10 是 弱可逆的。 x1 + x 2 + ? + x11 =4*_t[6]-1+2*_t[2]+3*_t[4]+2*_t[1]+_t[5] 对应的状态间距离下界:3

t11 的弱可逆性: CX T = b T , b =(0,0,0,-1,1,1,-1), xi 是非负整数 ,解方程得:
[1-_t[1]+_t[3]+_t[5]+_t[6], 1-_t[1]+_t[3]+_t[5]+_t[6], _t[1]-_t[3]-_t[5]+_t[2]+_t[4], _t[1], _t[2], 2*_t[1]-2*_t[3]-_t[5]+_t[4], _t[3], _t[4], _t[5], 1+_t[6], _t[6]] 取 x1 为目标函数, 化为规划问题后用 Matlab 求解, 得到 x1 无最大值所以 t11 是 弱可逆的。 x1 + x 2 + ? + x11 =4*_t[6]+3+2*_t[2]+3*_t[4]+2*_t[1]+_t[5] 对应的状态间距离下界:3
2.强可逆性判断和状态可逆条件计算 下面对每个变迁通过神经网络作强可逆性判断,如果不是强可逆就计算每个 变迁的状态可逆条件,我们取 N 为 4。

t1 的强可逆性:E =

4

process = 1 0 0 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 1 0 0 -1 -1 0 0 error1 = 4 error2 = 0 error3 = 0 error1:变迁过程中越界的误差, error2:变迁过程的末状态与目标状态的误差
43

Petri 网系统的可达性研究

error3:每步施超过一次变迁的误差 process 表示变迁过程每个位置的状态 E 不为 0,所以 t1 不满足强可逆性, P7 出现越界,所以如果 P7 有个 token 就可保证其可逆性。 x= 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 t1 的状态可逆条件为:p7 同理 t 2 不满足强可逆性,状态可逆条件为:p6 t3 满足强可逆性

t 4 满足强可逆性
t5 不满足强可逆性,状态可逆条件为:p1 t6 不满足强可逆性,状态可逆条件为:p2,p7 t7 不满足强可逆性,状态可逆条件为:p2 t8 不满足强可逆性,状态可逆条件为:p1 t9 不满足强可逆性,状态可逆条件为:p2 t10 不满足强可逆性,状态可逆条件为:p1

t11 不满足强可逆性,状态可逆条件为:p2
三.将 Petri 网映射成代数系统
44

第六章 应用实例分析

1.系统位置 Pi xi 2.变迁条件映射成双项式 t1 → h1 = x 2 x 4 ? x1 x3 t3 → h3 = x1 ? x1 x3 t5 → h5 = x3 ? 1 t8 → h8 = x3 x6 ? x4 x6 t10 → h10 = x3 x7 ? x 4 x6 3.初状态 M0 → x1 x3 x7
四.计算 Grobner 基及其基的变迁多项式表达式

t 2 → h2 = x1 x 4 ? x2 x5 t 4 → h4 = x 2 ? x 2 x 5 t6 → h6 = x4 ? 1 t9 → h9 = x5 x7 ? x4 x7 t11 → h11 = x5 x6 ? x4 x7 t7 → h7 = x5 ? 1

1.计算 Grobner 基 > ps:=[h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11]; > ps:= [x2 x4 - x1 x3, x1 x4 - x2 x5, x1 - x1 x3, x2 - x2 x5, x3 - 1, x4 - 1, x5 - 1, x3 x6 - x4 x6, x5 x7 - x4 x7, x3 x7 - x4 x6, x5 x6 - x4 x7] 调用 Grobner 基计算函数 G:=gbasis (ps, plex(x1,x2,x3,x4,x5,x6,x7)); 计算结果 G := [x6 - x7, x5 - 1, x4 - 1, x3 - 1, x1 - x2] g1=x6-x7, g2=x5-1 ,g3=x4-1 ,g4=x3-1, g5=x1-x2
2. 计算基的反演表达式

g1=x6-x7=h11 - x6*h7 + x7*h6; g4=h5; g5= - h1+x2*h6-x1*h5

g2=h7;

g3=h6;

五.可达性检验 比如:要研究(p2, p5, p6)是否可由初状态达到 (p2, p5, p6) → x2 x5 x6 , 计算始末状态差的变迁多项式表示 > q:=x1*x3*x7-x2*x5*x6; > normalf (q, G, plex(x1,x2,x3,x4,x5,x6,x7)); q := x1 x3 x7 - x2 x5 x6 0 q = x3*x7*g5+x2*x7*g4 - x2*x5*g1 - x2*x7*g2 = x3*x7*(- h1+x2*h6-x1*h5)+x2*x7*h5-x2*x5*(h11 - x6*h7 + x7*h6) - x2*x7*h7 = - x3*x7*h1+x3*x7*x2*h6- x3*x7*x1*h5+x2*x7*h5-x2*x5*h11+x2*x5* x6*h7 - x2*x5* x7*h6 - x2*x7*h7 = x3*x7*x2*h6+x2*x7*h5+x2*x5* x6*h7 - x3*x7*h1- x3*x7*x1*h5- x2*x5*h11 - x2*x5* x7*h6 - x2*x7*h7
45

Petri 网系统的可达性研究

因为不知道该系统是否可逆,所以仅用 Grobner 基的方法还不能判断(p2, p5, p6)是否可由初状态达到。 但是通过上面计算的状态可逆条件: (t1 ; p7), (t2 ; p6) , (t3), (t4), (t5 ; p1), (t6 ; p2,p7), (t7 ; p2), (t8 ; p1), (t9 ; p1), (t10 ; p1), (t11 ; p2)。我们 可以肯定:对于每一个变迁多项式前系数为负的项,检查得正好满足状态可逆条 件,所以(p2, p5, p6)可由初状态“不越下界”达到。 但是很明显实施过程“越上界” ,我们只有用能量优化模型直接求解: 末状态(p2, p5, p6) 映射成 D=(0,1,0,0,1,1,0) >> hop-solve E1 = 73 E2= 64 E3 = 13 E 4= 0 x= 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 能量降为 0 表示可达,并 D=C+f10+f2 , 即(p1, p3, p7) 顺序通过变迁 t10 ,t2 达到 (p2, p5, p6)。

46

第六章 应用实例分析

六.构造可达树验证 为了说明上述方法的正确性,我们构造该系统的可达树。 用可达树构造算法得: 1,3,7 t10 1,4,6 t2 2, 5, 6 t7 2,6 t4 2,5,6 2, 7 t4 2, 5, 7 t7 2, 7 t9 2,4,7 t6 t11 2,4,7 t1 1,3,7 t6 1, 6 t3 1,3,6 t8 1, 4, 6 t5 1,6 t5 1,7 t3 1,3,7

很明显上述方法和可达树构造的解是一致的。 我们举该例子的目的只是为了说明综合分析方法的处理流程和正确性,当然 就该例子而言,构造可达树的方法更有效,但当系统规模很大时,神经计算的优 势会表现出来。

47

Petri 网系统的可达性研究

结尾 问题与展望
Petri 网易于表示系统变化发生的条件及变化发生后的系统状态, 但不易表示 系统中数据值的具体变化。在大型,复杂系统模型中,Petri 网应用的主要困难 是模型状态空间的复杂性问题,它将随实际系统规模的增大而呈指数性增长。因 此,在 Petri 网的实际应用中,经常需要根据特定的应用环境对网模型加以修改 和限制。 Petri 网模型的化简技术的研究始终是 Petri 网研究的主题之一。 对 目前, 层次化模型技术和分块模拟逐步抽象综合技术是经常采用的方法之一; 另一种方 法是根据特定应用环境采用等效变换或保持某种性质的变换, 以达到缩小状态空 间,简化分析的目的。 用软件模拟神经计算的效率很低,因为并没有发挥神经计算高度并行和硬件 快速响应的特点。光电混合神经网络的出现可以很好的解决这一问题。而计算代 数 Grobner 基方法本身存在的一些问题,由于在 Grobner 基的计算过程中,我们 需要生成大量的中间多项式,当变量很多,多项式也很多时,计算一个理想的 Grobner 基,也需要花费很长的时间和大量的存储空间。所以我们希望能有更快 的 Grobner 基算法和计算工具,或更有效的判断一个多项式是否属于某个理想的 算法。 就能量优化模型而言,当达到可接受阈值时说明状态可达,但没有达到可接 受阈值时不能说状态不可达,有可能是因为神经网络陷于局部极点,所以它是可 达性的一个充分条件;而计算代数方法很明显是一个必要条件。我们综合了两种 方法,先用必要条件判断,再用充分条件判断,比单独使用任一种方法的效率要 高。但始终没有得到可达性的一个行之有效的充分必要条件。我们将这个问题作 为公开问题,在以后将作进一步的探讨。

48

致 谢

致 谢
本文是在我的导师杨路研究员的指导下完成的,杨老师严谨求实的治学态 度、广博的知识、敏锐的洞察力和丰富的科研经验给我留下深刻的印象,也必将 在我今后的学习工作中产生深远的影响。 杨老师对前沿交叉学科的深刻认识和其 他相关领域的关心,为我的研究工作提供了极大的帮助。同时在为人处事、治学 态度等各个方面也给了我谆谆教诲。 杨老师为我们提供了许多学习讨论研究的机 会和条件,不断将新的思想、方法和资料介绍给我们。更可贵的是杨老师能根据 学生的能力和特点让其发展。在此论文完成之际,谨向杨老师致以最崇高的敬意 和最衷心的感谢。

我也非常感谢曾振柄研究员的鼓励和帮助,在此论文写作过程中曾老师给我 提供了很多珍贵的建议,在与曾老师的研究合作和学术讨论中,他渊博的学识、 助人为乐的精神和平易近人态度尤其令我敬佩。同时,我还要感谢符红光研究员 和王晓京研究员等在学习、生活上给我的许许多多的教导、鼓励和帮助。

感谢夏时洪、陈光喜、向晓林、李永彬等博士,我们在研究生讨论班中进行 了友好的卓有成效的合作,在我的学习和论文写作期间给予我极大的帮助。也感 谢何永忠、黄黎、罗中兵、陈帆、马廷淮、朱大勇、王翠兰等同学,谢谢他们在 学习和生活上给予的帮助和支持,我向他们表示诚挚的谢意。

感谢我的父母在生活上对我无微不至的关心和帮助,更感谢他们对我的工作 的关心、支持和理解。特别感谢我的女友欧春艳小姐在寒假期间,为我查找、收 集了大量的相关资料和前期的资料整理工作。

最后,感谢所有关心、帮助和支持我完成学业及此论文的老师、同学、同事 和我的亲人朋友们!

49

附 录

附 录
1.参考文献
[1] Kommunikation mit Automaten. Petri, C.A., Bonn: Institut für Instrumentelle Mathematik, Schriften des IIM Nr. 2, 1962, [2] Olga Caprotti, Alois Ferscha, Hoon Hong. “Reachability Test in Petri Nets by Gr?bner Bases,” Jan. 1995 [3] Wei Jen Yeh, Michal Young, “Compositional Reachability Analysis Using Process Algebra”, NEC ResearchIndex, 1991, http://citeseer.nj.nec.com/ [4] Enric Pastor, Jordi Cortadella and Oriol Roig, “Symbolic Analysis of Bounded Petri Nets,” IEEE Transaction On Computers,Vol. 50, No. 5, May 2001, pp. 432-448. [5] Robin Milner, “A Calculus of Communication Systems, volume 92 of Lecture Notes in Computer Science. Springer-Verlag, New York, 1980. [6] S.D.Brookes,C.A.R.Hoare and A.W. Roscoe. A theory of communication sequential processes. Journal of the ACM, 31(3) , pp 560-599, July 1984. [7] J.A.Bergstra and J.W.Klop. Process algebra for synchronous communication. Information and Control, 60, pp 109-137 , 1984. [8] Ed Brinksma. A tutorial on LOTOS. Protocol Specification Testing and Verification. pp 171-194, Elsevier, 1986. [9] S.B.Akers, “Binary decision diagrams,” IEEE Transaction On Computers, Vol,C-27, No. 6,June 1978, pp. 509--516 [10] R.Bryant, “Symbolic Boolean Manipulation with Ordered Binary decision diagrams,” ACM. Computing Surveys, Vol. 24 , No.3, Sept 1992, pp 293-318 [11] 袁崇义, “Petri 网原理”电子工业出版社,1998 年 4 月 [12] 林闯, “随机 Petri 网和系统性能评价” 清华大学出版社,2000 年 1 月 [13] 何青, “计算代数” 北京师范大学出版社 1997 [14] Roy Nicolaides and Noel Walkington, “Maple -- A comprehensive introduction”Cambridge University Press 1996 [15] 焦李成, “神经网络系统理论”西安电子科技大学出版社,1996 [16] 李人厚,张永安, “精通 MATLAB--综合辅导与指南” ,西安交通大学出版 社,1998 ,清华大学出版社,1982 [17] “运筹学” [18] Hopfield J. and Tank, D. Neural computation of decisions in optimization
50

附 录

problems. Biological Cybernetics,1985, 52:141 - 152. [19] T. Murata, Petri Nets: Properties, Analysis and Applications, Proceedings of the IEEE, Vol. 77, No 4, April, 1989, pp. 541-580. [20] Kate Smith, Marimuthu Palaniswami, and Mohan Krishnamoorthy “Neural Techniques for Combinatorial Optimization with Applications”, IEEE Transactions On Neural Networks, Vol. 9, No. 6, November 1998 pp1301-1318 [21] 傅京孙,蔡自兴,徐光祐“人工智能及其应用”清华大学出版社,1987 年。 [22] Bhubaneswar Mishra. Algorithmic Algebra. 科学出版社. 2001. [23] 杨路, 张景中, 候晓荣. 非线性代数方程组与机器证明. 上海:上海科技教 育出版社, 1996. [24] 杨路. 全局优化的符号算法与有限核原理. 林东岱等主编:数学与数学机械 化. pp.210-220, 山东教育出版社, 2001. [25] Yang, L., Xia, S. H.. An inequality-proving program applied to global optimization, Proceedings of the Asian Technology Conference in Mathematics, W-C. Yang et al (eds.), ATCM, Inc., Blacksburg, pp.40-51, 2000. [26] Wu W.T., On the decision problem and the mechanization of theorem-proving in elementary geometry. Sci. Sinica 1978,21:159-172. [27] D.Psaltis, N.Farhat, Optical information processing based on associative-memory model of neural nets with thersholding and feedback, Opt.Lett. 10, 1985, pp98-100. [28] 宋菲军,S.Jutamulia, “近代光学信息处理” ,北京大学出版社,1998 年。 [29] Neil Collings, R.Sumi,K.J. Weible, Bruno Acklin, Wei Xue, Use of optical hardware to find good solutions to the traveling,salesman problem, pp.637-641,SPIE
Proceedings Vol. 1806,1993。

[30] W. K. Lai and G. G. Coghill, “Genetic breeding of control parameters for the Hopfield/Tank neural net,” in Proc. Int. Joint Conf. Neural Networks, 1992, vol. IV, pp. 618–623. [31] Kapur D., Saxena T, Yang L., Algebraic and geometric reasoning using Dixon resultants. In: Proc. ISSAC'94, 1994, ACM Press, 99-107. [32] Yang L., Hou X.R., Gather-and-Sift: A symbolic method for solving polynomial systems. Proc.ATCM'95,1995,Singapore. [33] Karmarkar N. “A new polynomial time algorithm for linear programming”, Combinatorica 4,1984, pp373-395 [34] Buchberger B., Groebner Bases: An algorithmic method in polynomial ideal theory. Chapter 6 in: Recent Trends in Multidimensional Systems Theory.Bose N.K.(ed.), D.Reidel Publ.Comp.,1985. [35] Andrew Blais, Ph.D. (onlymice@gnosis.cx), David Mertz, Ph.D. (mertz@gnosis.cx) “An introduction to neural networks”, Gnosis Software, Inc.July 2001

51

附 录

2.Matlab 实现的能量优化的神经网络算法
s=7; %place t=15; %transfer n=3; %steps lamda1=1; %para1 lamda2=5; %para2 lamda3=10; %para3 lamda4=10; %para4 % transfer matrix a=[ 1 -1 -1 1 0 0 0 -1 1 0 0 -1 1 0 1 0 0 1 0 0 -1 -1 -1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 c=[1,0,1,0,0,0,0]; % init b=[-1,1,-1,1,0,0,0]; % end-init

0 0 0 -1 0 0 0

0 0 0 0 -1 0 0

0 0 -1 0 0 -1 0

0 0 0 1 0 1 0

0 0 0 0; 0 0 0 0; 0 0 –1 0; 0 1 1 1; -1 0 0 -1; 0 0 1 -1; -1 1 -1 1];

% init varible x=zeros([t,n]); w=zeros([t,n,t,n]); u=zeros([t,n]); for k=1:t for p=1:n x(k,p)=floor(rand(1)*7/5); end end

% calculate w and u for k=1:t for p=1:n for l=1:t for q=1:n if ~(k==l & p==q) temp=0; for j=1:s temp=temp+a(j,k)*a(j,l); end temp=lamda1*temp*(n-max(p,q)+1)+lamda2*temp; if p==q & ~(k==l)
52

附 录

temp=temp+0.5*lamda3; end w(k,p,l,q)=-temp; end end end temp=0; for j=1:s temp=temp+ lamda1*((2*c(j)-1)*a(j,k)+abs(a(j,k)))*(n-p+1) + lamda2*(abs(a(j,k)) - 2*b(j)*a(j,k)); end u(k,p)=temp; end end % loop for time=1:10 % change nn state for k=1:t for p=1:n temp=-u(k,p); for l=1:t for q=1:n if ~(k==l & p==q) temp=temp+w(k,p,l,q)*x(l,q); end end end if temp>0 x(k,p)=1; else x(k,p)=0; end end end

% calculate energy E=0; for k=1:t for p=1:n for l=1:t
53

附 录

for q=1:n if ~(k==l & p==q) E=E-w(k,p,l,q)*x(k,p)*x(l,q); end end end E=E+u(k,p)*x(k,p); end end for i=1:s E=E+lamda2*b(i)*b(i); end E % calculate errors error1=0; % main error process=zeros([n,s]); for i=1:n for j=1:s temp=0; for p=1:t sum=0; for q=1:i sum=sum+x(p,q); end temp=temp+sum*a(j,p); end process(i,j)=temp+c(j); error1=error1+temp*temp+(2*c(j)-1)*temp; end end process' error1=lamda1*error1 error2=0; % reachability error for i=1:s temp=b(i); for k=1:t for j=1:n temp=temp-a(i,k)*x(k,j); end end error2=error2+temp*temp; end
54

附 录

error2=lamda2*error2 error3=0; % only one transform in one row for i=1:n for j=1:t-1 for k=j+1:t error3=error3+x(j,i)*x(k,i); end end end error3=lamda3*error3 end

3. 国外相关研究机构
Lancaster University (Computer Science)
Address Computer Science Department, Lancaster University, Lancaster WWW http://www.comp.lancs.ac.uk/computing/users/angie/work.htm Net Models Coloured Petri nets, ordinary Petri nets Research Topics in Petri Nets Application of Petri nets to mobile robotics and mechatronics using partially automatically generated code based on the Petri net model. Related issues such as model checking. Tools Developing TRAMP (Toolkit for Rapid Autonomous Mobile robot Prototyping) Papers http://www.comp.lancs.ac.uk/computing/users/angie/publications.htm Contacts Angie Chandler (angie@comp.lancs.ac.uk)

LAAS-CNRS (Organization and Control of Discrete Systems)
Address LAAS-CNRS, Organization and Control of Discrete Systems WWW http://www.laas.fr/~robert/ Net Models Petri nets with objects Research Topics in Petri Nets

55

附 录 Application to manufacturing systems and industrial processes (supervisory control and monitoring), Relationships with logic (linear logic, reasoning with time, fuzzy markings, diagnosis) Tools MISS-RdP (developed by IXI) Papers http://www.laas.fr/~robert/ Contacts Robert VALETTE (robert@laas.fr)

Humboldt University of Berlin (Petri Net Technology)
Addresses Humboldt University of Berlin, Computer Science Department Technical University of Berlin, Computer Science Department WWW http://www.informatik.hu-berlin.de:80/PNT/ Net Models Low-Level Petri nets, Algebraic High-Level Petri nets, Coloured Petri nets, Higher-Order Petri nets Research Topics in Petri Nets Conception, theoretical foundation and validation of an applied Petri Net Technology, Petri net construction kit consisting of individual building blocks along with rules for combinig them, process model, integration of other formal or semi-formal description techniques, universal approach to description and classification of Petri nets, data type description techniques, horizontal and vertical structuring principles, transformation between different net classes, specification and verification concepts such as temporal logic, analysis and simulation techniques for Petri nets Papers http://www.informatik.hu-berlin.de:80/PNT/pnt-public.html Contacts Project management (PNT-leitung@informatik.hu-berlin.de)

Berlin University of Technology
Address Berlin University of Technology, Computer Science Department WWW http://pdv.cs.tu-berlin.de/forschung/performance.engl.html Net Models Non-Markovian stochastic Petri nets, Colored Petri nets, Fluid stochastic Petri nets Research Topics in Petri Nets Transient and stationary numerical analysis of non-Markovian Petri nets, analysis of Petri nets with discrete timing, fast simulation techniques, modeling and performance evaluation of manufacturing systems with timed and colored Petri nets, Fluid stochastic Petri nets.

56

附 录 Tools TimeNET Papers http://pdv.cs.tu-berlin.de/veroeffentlichungen.html#Modellierung Contacts Reinhard German (rge@cs.tu-berlin.de), Christian Kelling (ck@cs.tu-berlin.de), Armin Zimmermann (azi@cs.tu-berlin.de), Robert Zijal (bob@cs.tu-berlin.de)

Eindhoven University of Technology
Address Eindhoven University of Technology, Mathematics and Computing Science Department, Information Systems group, Eindhoven WWW http://www.win.tue.nl/win/cs/is/ Net Models High-level Petri nets (Petri-nets extended with color, time and hierarchy) Research Topics in Petri Nets High-level Petri nets, Colored Petri nets, Timed Petri nets, Applications (in particular business process reengineering, workflow and logistics), Performance analysis, (Distributed) simulation, Verification, Equivalences on Petri nets. Tools ExSpect (used as CASE and BPR-tool) and analysis tools such as INA. Papers http://www.win.tue.nl/win/cs/is/smis/ Other Resources ftp://ftp.win.tue.nl/pub/techreports/ Contacts Wil van der Aalst (wsinwa@win.tue.nl)

Nanyang Technological University
Address Nanyang Technological University, School of Mechanical and Production Engineering WWW http://web.ntu.edu.sg/mpe/ Net Models Intelligent Petri nets Research Topics in Petri Nets Knowledge based Petri net, Object-oriented Intelligent Petri nets, Hybrid Intelligent Petri net Tools Hybrid Intelligent Petri Net Tool (being developed) Papers

57

附 录 http://www2.ntu.ac.sg:8000/~m95017L61/pn.htm Contacts X.F. Zha (m95017L61@ntuvax.ntu.ac.sg)

Swiss Federal Institute of Technology (Computer Engineering and Networks)
Address Swiss Federal Institute of Technology, Institut of Technische Informatik und Kommunikationsnetze, Computer Engineering and Networks Laboratory WWW http://www.tik.ee.ethz.ch/~codesign/ Net Models High-level object-oriented time Petri Nets Research Topics in Petri Nets Tools, applications, simulation, (timing) verification Tools CodeSign (editor, simulator, embedding of other specification formalisms) Papers http://www.tik.ee.ethz.ch/~tec/Publications.dhtml Contacts Prof. Lothar Thiele (thiele@tik.ee.ethz.ch)

University of Aarhus
Address University of Aarhus, Computer Science Department WWW http://www.daimi.au.dk/CPnets/ Net Models Coloured Petri Nets Research Topics in Petri Nets Coloured Petri Nets, tools, application, equivalences in occurrence graphs, invariants, temporal logics, object-oriented Petri Nets. Tools * Design/CPN (editor, simulator, and Occurrence Graph Tool) * CPN Tools * Invariant Tool Papers http://www.daimi.au.dk/CPnets/publ/ Other Resources ftp://ftp.daimi.au.dk/pub/petrinet/papers/ Contacts Kurt Jensen (kjensen@daimi.au.dk)

University of Aizu
Address

58

附 录 University of Aizu, Computer Hardware Department WWW http://www.u-aizu.ac.jp/labs/hw-ce/asy-gr.html Net Models Signal Transition Graphs, Petri net unfoldings, Place Chart Nets Research Topics in Petri Nets Asynchronous (self-timed) circuits and systems. Models of concurrent behavior (Petri Nets, Signal Transition Graphs, FSMs, etc.). Petri net unfoldings, Place Chart Nets. Tools Forcage - PC based tool for synthesis and analysis of speed-independent circuits, Unfolding - Tool for checking properties of Petri Nets and STGs working under SIS, Petrify - Tool for synthesis and transformation of Petri Nets and STGs (Created in UPC) Papers http://www.u-aizu.ac.jp/labs/hw-ce/asy-gr.html#papers Other Resources ftp://ftp.u-aizu.ac.jp/u-aizu/async/ Contacts Michael Kishinevsky (kishinev@u-aizu.ac.jp), Alex Kondratyev (kondraty@u-aizu.ac.jp), Alexander Taubin (taubin@u-aizu.ac.jp)

Duke University
Address Duke University, Durham WWW http://www.ee.duke.edu/~kst Net Models Stochastic Reward Nets, Markov Regenerative Stochastic Petri Nets, Fluid Stochastic Petri Nets Research Topics in Petri Nets Fundamental developments, numerical solution techniques, applications Tools SPNP, SHARPE Contacts Kishor Trivedi (kst@ee.duke.edu)

General Motors Research and Development Center
Address General Motors Research and Development Center WWW http://www.gm.com Net Models Stochastic Petri Nets, Colored Petri Nets Research Topics in Petri Nets

59

附 录 Modeling and analysis of manufacturing systems, logistic and supply chain network Tools Decision support system with a PN modeler Contacts Shang-Tae Yee (shang-tae.yee@gm.com)

George Mason University
Address C3 Architectures Laboratory, C3i Center, George Mason University, Fairfax, VA 22030 WWW http://viking.gmu.edu/http/ Net Models Colored Petri Nets Research Topics in Petri Nets Determination of excutable models (Petri Nets) from structured analysis models and from object oriented approaches. Generation of information architectures. Mathematical organization theory. Validation and verification of rule bases. Temporal logic and petri nets. Applications in command and control systems and adaptive system architectures. Tools Design/CPN and associated algorithms Other Resources ftp://viking.gmu.edu Contacts Alexander H. Levis (alevis@gmu.edu)

University of Illinois at Chicago
Address University of Illinois at Chicago, EECS Department WWW http://www.eecs.uic.edu/~shatz/cssl.html Research Topics in Petri Nets Reachability analysis; modeling and analysis of concurrent software, including Ada tasking and logic programs; object-oriented nets; real-time analysis. Tools Research tools for Ada tasking analysis and for real-time models. Contacts Tadao Murata (murata@eecs.uic.edu), Sol Shatz (shatz@eecs.uic.edu), Ugo Buy (buy@eecs.uic.edu), Bob Sloan (sloan@eecs.uic.edu)

University of Illinois at Urbana-Champaign
Address

60

附 录 University of Illinois at Urbana-Champaign, Coordinated Science Laboratory, Center for Reliable and High-Performance Computing WWW http://www.crhc.uiuc.edu/PERFORM Net Models Stochastic Activity Networks, Stochastic Petri Nets, others Research Topics in Petri Nets Efficient techniques for extremely large systems, stochastic process solution techniques, relationships between net structure and behavior, applications to computer systems and networks. Tools UltraSAN (a tool with an X-Windows-based graphical user interface for model-based evaluation of systems represented as stochastic activity networks) Papers http://www.crhc.uiuc.edu/PERFORM/papers.html Other Resources ftp://ftp.crhc.uiuc.edu/pub/UltraSAN/USAN_papers Contacts William H. Sanders (whs@crhc.uiuc.edu)

61


相关文章:
更多相关标签: