（计算机软件与理论专业论文）基于petri网的时间知识推理算法的研究.pdf

基于p e l r i 隔的时闻知识推理算法的研究 摘要 随着科学技术的发展，尤其是信息技术的发展，人们所研究的系统规模越来 越大，内容更加丰富，同时不确定因素层出不穷。目前所研究的内容一般包括： 定性和定量的行为、确定性和不确定性问题、多系统的混合问题等。时间知识具 有一定的不确定性，在许多应用系统中起着重要作用。现有的时间知识表示方法 中，单一时间点的表示既不实际也不完整，常用的时间区间的表示缺少定量的分 析；已有的基于时间p e t r i 网的时间知识推理算法过程较为复杂。 本文在前人研究的p e t r i 网理论的基础上，针对一类复杂系统形式化建模过程 中存在的时间不确定性问题，构建了相应时问知识的表示方法及分析方法，即将 p e l r i 网理论和模糊集合理论相结合，在对系统进行建模的基础上，进行时间知识 的定量分析。首先，本文定义一种对复杂系统进行形式化建模的模糊时间p e t r i 网 ( f t p n ) ，该网引入四个时间的模糊集理论函数，即模糊时间片、模糊使能时问、 模糊发生时间和模糊延迟，来处理时间的不确定性：然后基于时间模糊集理论函 数的相关运算提出f t p n 时间知识推理算法的基本思想，详细讨论了最迟时间可 能性分布l a t e s t ，最早时间可能性分布e a r l i e s t 以及最小操作m i n 的运算方法：最 后，用列车运行算例验证算法的有效性，并与已有的基于时间p e t r i 网的时间知识 推理算法进行了对比分析，对比结果表现出该算法具有定量分析、计算简单、简 化系统，便于系统集成的特点。 本文的模糊时间p e t r i 网能够有效表示一类复杂系统在形式化建模过程中存在 的时间不确定性知识，相应的时间知识推理算法能够对时间不确定性问题进行定 量分析，可以应用于智能交通、计算机的通讯控制等领域。另外，模糊时间p e t r i 网模型可以与a g e n t 技术结合，与各种p e t f i 网分析工具进行集成，对各种智能专 家系统的研究也有很大现实意义。 关键字：模糊时间p e t f i 网，不确定性，模糊时间函数，时间知识推理 基于p e t r i 网的时问知识推理算法的研究 a bs t r a c t w i t ht h e d e v e l o p m e n t o fs c i e n c ea n dt e c h n o l o g y , e s p e c i a l l yi n f o r m a t i o n t e c h n o l o g y , t h es c o p eo f o u rr e s e a r c hg e t sl a r g e ra n dl a r g e r , t h ec o n t e n ti sm u c hr i c h e r a n dt h eu n c e r t a i nf a c t o r se m e r g ei ne n d l e s s l y t h ep r e s e n tr e s e a r c hi n c l u d e st h e s ef i e l d s s u c ha sq u a l i t a t i v ea n dq u a n t i t a t i v eb e h a v i o r s ，c e r t a i n t ya n du n c e r t a i n t yi s s u e sa n d h y b r i di s s u e so fm u l t i s y s t e me t c t i m ei st e m p o r a lk n o w l e d g ew i t hu n c e r t a i n t y , w h i c h i si m p o r t a n ti nm a n ya p p l i c a t i o ns y s t e m s t h ep r e s e n tr e p r e s e n t a t i o n so ft e m p o r a l k n o w l e d g eu s ep o i n to f t i m ea n dt i m ei n t e r v a l t h eu s u a lr e p r e s e n t a t i o no fs i n g l ep o i n t o ft i m ei si m p r a c t i c a la n dn o ti n t e g r a t e da n dt i m ei n t e r v a li sd i f f i c u l tt od oq u a n t i t a t i v e a n a l y s i s t h ec o r r e s p o n d i n gt e m p o r a lk n o w l e d g er e a s o n i n gi sn o ta c c u r a t eo rc l e a r t h e p r o c e s so f r e a s o n i n ga l g o r i t h mb a s e do nt i m ep e t r in e ti sm o r ec o m p l e x b a s e do ne x i s t e dp e t r in e tt h e o r i e s ，t h ep a p e rg i v e sp r o m i n e n c et ou n c e r t a i n t yi n s y s t e mm o d e l i n ga n dc o n s t r u c t sak i n do fr e p r e s e n t a t i o no ft e m p o r a lu n c e r t a i n t ya n d s y s t e ma n a l y s i sm e t h o df o rc o m p l e xs y s t e m s c o m b i n i n gp e t r in e tt h e o r ya n df u z z ys e t t h e o r y , w ed oq u a n t i t a t i v ea n a l y s i sf o rt e m p o r a lu n c e r t a i n t yb a s e do ns y s t e mm o d e l i n g t h ep a p e rd e f i n e saf u z z yt i m ep e t r in e t ( f t p n ) a d o p t i n gf o u rf u z z ys e tt h e o r e t i c f u n c t i o n so ft i m ec a l l e df u z z yt i m e s t a m p ，f u z z ye n a b l i n gt i m e ，f u z z yo c c u r r e n c et i m e a n df u z z yd e l a y , t od e a lw i t ht e m p o r a lu n c e r t a i n t yo fs o m ec o m p l e xs y s t e m s 。 a c c o r d i n gt of u z z yt i m ef u n c t i o n sat e m p o r a lk n o w l e d g er e a s o n i n ga l g o r i t h m i s p r e s e n t e da n dt h ec a l c u l a t i o nm e t h o d so fl a t e s t ，e a r l i e s ta n dm i na r ed i s c u s s e di nt h i s p a p e r t h et r a i no p e r a t i o ni n s t a n c e ss h o wt h a tt h em e t h o dc a ne f f i c i e n t l yv a l i d a t et r a i n o p e r a t i o np l a n ，r e p r e s e n tt e m p o r a lk n o w l e d g ea n dr e a s o n c o m p a r e dw i t he x i s t e d m e t h o d s ，t h i sm e t h o dh a ss o m eo u t s t a n d i n gc h a r a c t e r i s t i c ss u c ha sq u a n t i t a t i v ea n a l y s i s ， s i m p l ec o m p u t a t i o n ，s y s t e ms i m p l i f y i n g a n dc o n v e n i e n c ef o rs y s t e mi n t e g r a t i n g f u z z yt i m ep e t r in e tc a nr e p r e s e n tt e m p o r a lu n c e r t a i n t yk n o w l e d g ei nt h ep r o c e s s o fm o d e l i n gm a n yc o m p l e xs y s t e m s t h ea l g o r i t h mb a s e do nf u z z yt i m ep e t r in e tc a n d oq u a n t i t a t i v ea n a l y s i sf o rt e m p o r a lu n c e r t a i n t ya n dc a l l b ea p p l i e dt oi n t e l l i g e n tt r a f f i c ， c o m m u n i c a t i o nc o n t r o lo fc o m p u t e r se t c i na d d i t i o n f t p nm o d e lc a ni n t e g r a t ew i t h a g e n tt e c h n o l o g ya n dv a r i o u sp e t r in e tt o o l sa n d i ti ss i g n i f i c a n tf o rr e s e a r c ho fv a r i o u s i n t e l l i g e n te x p e r ts y s t e m s k e y w o r d s ：f u z z yt i m ep e t r in e t ；u n c e r t a i n t y ；f u z z yt i m ef u n c t i o n ；t e m p o r a l k n o w l e d g er e a s o n i n g i i 郑重声明 y7 8 2 7 6 8 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、抄 袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由此产生的一切 法律责任和法律后果，特此郑重声明。 学位论文作者( 签名) ： 王确 伽誓年5 月f 目 基于p e t r i 网的时间知识推理算法的研究 第一章绪论 随着科学技术的发展，尤其是信息技术的发展，人们所研究的系统规模越来 越大，内容更加丰富，同时不确定因素层出不穷。目前所研究的内容一般包括： 定性和定量的行为、确定性和不确定性问题、多系统的混合问题等。时间知识具 有一定的不确定性，在许多应用系统中起着重要作用，如何恰当合理的表示这种 不确定的时间知识是众多应用系统的关键问题。本文在前人研究的p e t r i 网理论的 基础上，针对一类复杂系统形式化建模过程中存在的时间不确定性问题，构建了 相应时间知识的表示方法及分析方法，即将p e t r i 网理论和模糊集合理论相结合， 在对系统进行建模的基础上，进行时间知识的定量分析。 本章主要介绍基于p e t r i 网的时间知识推理的研究背景、现状和意义，以及本 文的研究内容。 1 1 研究背景与现状 p e t r i 网自1 9 6 2 年由德国的c a p e t r i 提出以来，经历四十多年的发展，已经 形成了较为坚实的理论基础，并形成多种类型的应用体系。p e t r i 网f 1 t 2 j 易于描述系 统的并发、竞争、同步等特征，基于p e t r i 网模型进行分析可以得到许多有关结构 和动态行为的重要信息，由此进行评价和改进系统。与其他系统相比，p e t r i 网有 下面的特点： ( 1 ) 时间之间的因果相关性和不相关性能够得到清楚的描述。相互独立的事 件不会被放在一个线性的时间段( t i m es c a l e ) 里；p e t r i 网理论中引入了一个不交 叉的、偏序的并发关系( 变迁序列) ，这种关系是整个p e t r i 网概念的基础。 ( 2 ) 对于一些系统而言，用顺序模型来描述是非常不方便的，会导致各种细 节不必要地分散。 ( 3 ) 可以在不改变描述语言的前提下以不同层次的抽象来表示系统。 f 4 ) p e t r i 网表示方法可以验证系统的属性，例如，状态的可达性、库所的有 界性、变迁的活性、初始状态的可逆达性和公平性等。一旦系统使用p e t r i 网来建 模，系统的属性便可以使用类似的方法表示和正确性证明。 因此，p e t r i 网理论在包括硬件、软件和社会领域等许多领域中都得到了广泛 基于p e t r i 网的时问知识推理算法的研究 的应用，已经大量地应用于各种系统的建模，例如，计算机的通讯控制、铁路系 统的实时指挥和监控、城市交通系统的实时指挥和监控、区域性供电网的调度和 监控等。 基于p e t r i 网的推理方法的研究有很多p ”，目前已有的推理方法有：在p e t r i 网中引入线性逻辑的推理，基于可达树的推理，等价矩阵方法，演绎或分解技术 等。由于p e t r i 网可以很好的表现出时间之间的因果相关性，基于p e t r i 网模型对 系统时间问题的分析是解决时间不确定性问题的一条有效途径。基于p e t r i 网的时 间知识推理是目前p e t r i 网研究领域的热点问题【6 叫2 1 。现有的时间知识表示方法大 多采用单一时间点或时间区间，已经与p e t r i 网理论相结合构建了各种时间p e t r i 网模型i m l6 1 ，例如，时间约束p e t r i 网，时间p e t r i 网，赋时p e t r i 网等。 时间知识具有一定的不确定性，在许多应用系统中起着重要作用，如智能交 通，电子商务、网络协议等模型的分析，如何恰当合理的表示这种不确定的时间 知识是众多应用系统的关键问题1 w 们。但目前的时间知识表示方法和时间知识推 理算法中，没有较精确的时间知识表示和快速清晰的算法对时间知识进行有效的 处理。例如，采用单一的时间点表示既不实际也不完整，而常用的时间区间的表 示也缺少定量的分析；时间知识的线性推理不易编程实现，已有的基于时间p e l x i 网的时间知识推理算法过程较为复杂。 针对目前的研究现状与应用需求，本文引入模糊集理论对时间不确定性知识 进行表示，构建模糊时间p e t r i 网，并给出对应时间知识表示方法的时间知识推理 算法的基本思想。 1 。2 研究意义 对于与时间相关的一类复杂系统，时间不确定性知识的表示方法是进行系统 分析的关键。时间知识在系统建模的过程中表现出不确定性，将模糊集理论用来 表示不确定性或主观时间信息，既是应用领域的需求，又是p e t r i 网建模研究的热 点问题【2 5 1 。本文针对复杂系统的时间不确定性问题，基于已有的时间p e t f i 网 i l m o 】，定义了一种对一类复杂系统进行形式化建模的模糊时间p e t r i 网，用基于时 间模糊集理论函数相关运算的时间知识推理算法对复杂系统的相关时间问题进行 了分析，与已有算法i s , 9 对比结果表现出该方法具有定量分析、计算简单、简化系 基于p e t r i 网的时间知识推理算法的研究 统和便于系统集成的特点。 基于p e t r i 网的时间推理算法的研究对与时间相关的复杂应用系统的建模和分 析有一定的现实意义。本文的模糊时间p e t r i 网能够有效地表示一类复杂系统在形 式化建模过程中存在的时间不确定性知识，相应的时间知识推理算法能够对时间 不确定性问题进行定量分析，可以应用于智能交通、计算机的通讯控制、区域性 供电网的调度和监控等。 本文用列车群运行算例验证了该算法的有效性，同时也说明了基于模糊时间 p e t r i 网的时间知识推理算法在铁路智能运输系统中的应用。随着列车群运行速度 的提高，以及一系列客观不确定性因素的影响，列车运行的时间参数的不确定性 问题的处理就显得目益突出伫1 2 3 1 ，其中列车运行的时间不确定问题的分析，对列 车运行过程中的动态控制、对站内的列车调度、对乘客的换乘、列车的货物中转、 铁路系统的资源分配等问题的处理都有很现实的意义。 另外，模糊时间p e t r i 网模型可以与a g e n t 技术结合，构成针对多a g e n t 的时 间知识推理算法，提供对分布式系统的时间问题分析；时间推理方法也丰富了不 确定性知识推理的研究，该方法可以应用于各种p e t r i 网分析工具，对各种智能专 家系统也有很现实的意义。 1 3 本文的研究内容 本文针对一类复杂系统建模过程中存在的时间不确定性问题，以及现有的时 间不确定性知识表示和推理算法的不足，在研究时间p e t r i 网【1 牝川的基础上，定义 了一种模糊时间p e t r i 网，采用时间模糊集理论函数 2 4 , 2 5 】表示不确定性时间知识； 根据时间知识的表示和计算方法提出相应的时间知识推理算法。具体的研究内容 如下： 1 模糊时间p e t r i 网的形式化定义：根据p e t r i 网的基本原理和所引入的模糊 时间函数的概念给出模糊时间p e t r i 网的定义。 2 时间不确定性的表示和计算：模糊时间函数之间的具体运算。 3 基于模糊时间p e t r i 网的时间知识推理算法的基本思想：在时间推理算法 中引入m u r a t a 提出的用模糊集理论来表示不确定性或主观时间信息的思 想，即引入时间模糊集理论函数，对算法的时间不确定性问题进行处理， 基于p e t r i 网的时间知识推理算法的研究 结合对p e t r i 网的遍历得到时间知识推理过程。 4 算法的实现：考虑算法的可移植性，为方便与其他p e t r i 网建模、属性分 析工具及推理算法集成，本算法用j a v a 语言实现；难点在于算法的数据 结构以及已有算法时间参数生成图存储结构的设计。 5 算法应用的有效性及与已有算法的对比分析：在实验中结合时间知识推理 算法在铁路智能运输系统中的应用进行研究，针对多个列车运行算例用已 有的时间知识推理算法和该算法进行实验对比。 下面是论文的组织结构： 第一章绪论 介绍本文的研究背景与现状、研究意义以及具体的研究内容。 第二章不确定性时间知识表示方法 本章讨论了不确定性知识的存在和可能性理论，并详细介绍了本文 所引入的模糊时间函数：模糊时间片、模糊使能时间、模糊发生时 间以及模糊延迟的定义。 第三章模糊时间p e t r i 网 首先给出了p e t r i 网的基本概念，然后重点介绍了模糊时间p e t r i 网 的定义和相关概念。 第四章基于f t p n 的时间知识推理算法 本章给出了f t p n 时间知识推理算法的基本思想，详细讨论了算法 中模糊时间函数之间相关运算的计算方法以及该算法和已有算法的 实现，并对算法进行了初步分析。 第五章与t p n 时间知识推理算法的对比分析 本章用已有的列车运行算例与稍作修改后较复杂的列车运行算例对 f t p n 时间知识推理算法进行有效性分析，基于时问不确定性问题的 处理，与基于时间p e t r i 网的时间知识推理算法进行了对比。 第六章总结与展望 对本文工作进行总结，并指出进一步的工作。 4 基于p e t r i 阿的时间知识推理算法的研究 第二章不确定性时间知识表示方法 2 1 不确定性的存在 在各种实际应用领域中，严格精确的和确定的知识并不多见，大量的知识是 不精确的和不确定的，需要采用不确定推理或称为不精确推理对不确定知识进行 处理。可以说，不确定性( u n c e r t a i n t y ) 是智能问题的本质特征3 2 3 4 1 ，因此，智能 系统的能力更主要反映在求解不确定性问题的能力上。 实际领域如医学诊断、故障诊断、探矿、天气预报、军事指挥、市场分析、 投资决策和调度控制等，这些领域中问题的求解可利用的知识、规则和证据常常 是不确定的。不确定性产生的原因有多种：随机性、模糊性、多义性等。 对于知识，造成其不确定性的客观因素，除了随机性和模糊性外，还有知识 之间的冲突( 不一致) 、经验知识形成的局限、知识获取的不完全等。在建立系统、 构造知识库的时候，也可能产生不确定性。任何事情都和很多复杂因素有关，并 不是孤立的，我们在建立系统模型的时候，需要严格的限定模型，抓住主要因素， 而忽略一些次要因素，这样得到的系统和知识库自然具有不确定性。其次，一些 经验知识，难于表达精确，实际上，有些问题只能是模糊表达。 对于推理过程，导致不确定性产生的主要原因在于知识不确定性的动态积累 和传递过程。在推理的每一步都需要综合证据和规则的不确定因素，为此，通常 要通过某种不确定的测度，寻找尽可能符合客观实际的计算模式，随着推理步骤 的展开和不确定测度的传递计算，最终得到结果的不确定测度。 总的来说，不确定性信息有以下几类：由于发生条件提供的不充分或偶然因 素的干扰所产生的随机不确定性；因信息的外延模糊导致的模糊不确定性；信息 的部分己知部分未知所导致的灰色不确定性和由于决策者在主观上的、认识上的 不足所产生的未确知不确定性。针对不同类型的不确定性信息，人们提出多种不 确定性的表示方法，如概率论、确定性理论、证据理论、模糊集合理论、可能性 理论以及灰色系统理论等。其中，处理随机性的理论基础是概率论，处理模糊性 的基础是模糊集合理论，可能性理论是在模糊集合理论的基础上提出来的。 实际上，每种知识表示方法并不仅仅是种表达知识的形式，还对应于相应 的知识应用方法，即推理方法，也就是如何使用以某种知识表达形式所表示的知 识进行智能计算，实现不确定信息的传递，得到所需要的判定和决策。 5 基于p e t r i 嘲的时间知识推理算法的研究 2 2 可能性理论 z a d e h 在其1 9 6 5 年提出的模糊集合论的基础上，于1 9 7 8 年又提出了可能性 理论【35 1 。可能性理论是处理不确定信息的一种方法，模糊集理论的发展使得该理 论具有较完善的理论基础，而经由d u b o i sd ，p r a d eh 等人的发展p 州2 i ，已经应 用到实际的专家系统和推理系统中，因为它较为符合人类的思维方式，且具有较 低的信息量和时间计算复杂度，因而得到了越来越多学者的关注。 可能性理论( p o s s i b i l i t yt h e o r y ) 的基本思想是要确定：可能性，可能性分布， 可能性分布函数，条件可能性分布函数，边缘可能性分布函数等几个度量和它们 之间的关系，以及各种模糊命题的转换规则和不精确命题的推理规则等等。 设a 是论域q 上的模糊集合，它对应的隶属函数为“a 的) 。如果a 表示变量y 取值的范围，a 就是变量y 的一个模糊限制( f u z z yr e s t r i c t i o n ) ，隶属函数u “( i ) ) 表示把m 赋给变量y 时满足限制a 的程度。 z a d e h 把可能性分布定义为在变量的给定值上有弹性的模糊限制。设变量y 表示年龄，并且在q = 【0 ，2 0 0 1 上取值。q 上的模糊集合y o u n g ( 年轻) 就是一个 对于y 在q 中取值的模糊限制。若y o u n g 对y = 2 8 的限制为v t ”。g ( 2 8 ) = 0 7 ，其意 义是y 取值为2 8 时，命题“y 是年轻人”成立的可能性为o 7 。 可能性理论的一般性定义及相关说明( 3 7 1 归纳如下： ( 1 ) 可能性分布函数( p o s s i b i l i t yd i s t r i b u t i o n ) ：设变量y 在论域q 中取值， a 是q 上的模糊集合，它的隶属函数为队。若a 是y 取值的模糊限制r ( y ) ，即 r ( y ) = a ，则命题“y 是a ”规定了变量y 的一个可能性分布兀y = r ( y ) 。y 的可 能性分布函数托y 可相应地定义为研= 队。 上述定义将可能性理论与模糊集合论联系起来。即元素t o 对a 的隶属度u a 佃) 代表命题“y 是a ”成立地可能性程度。若至少存在个q ，使得7 【y 细) 一1 ， 则称兀y 是正规可能性分布函数。 ( 2 ) 可能性测度( p o s s i b i l i t ym e a s u r e ) ：设a 是论域q 上的模糊集合，兀y 是 关于y 的可能性分布，则a 的可能性测度表示为 冗( a ) = s u p n v ( o ) l c o e a 托( a ) 表示“a 中存在某个0 ) 作为y 的值”的可能性程度。 ( 3 ) 可能性分布本质上是非统计的。处理模糊性的基础是模糊集台理论，处 6 基于p e t r i 网的时间知识推理算法的研究 理随机性的理论基础是概率论( p r o b a b i l i t y ) 。如果p y 是一个与y 有关的概率分布， 由于n y 和p y 之间仅有这样一种关系：不可能蕴含着概率为零的情况，反之则不 成立；所以n y 不能由p y 推导出来，p y 也不能由n y 推导出来。 ( 4 ) 可能性理论的基础是模糊集理论，因此具有以下优点： 对由于人类认识表达不精确而产生的一些问题是一个较好的解决方法； 模糊集技术相当灵活，可以有多种运算定义以及多种问题形式化的方法； 有较低的信息和时间复杂度。 ( 5 ) 采用可能性理论来表示不确定性知识可以较好的解决不确定性的表示问 题，但可能性的精确度量存在以下问题： 怎样构造合理的隶属函数并不总是十分清楚，而且确定隶属函数时只能是 针对某一具体问题或某一类实际情况进行构造。 选择适当的运算定义也有一定的问题，正如z a d e h 本人说的那样，不同的 情况下需要不同的定义，但不一定总是清楚应该使用什么样的定义。 若结果函数并不像系统开始预定的隶属函数，要解释由模糊逻辑蕴含规则 所得到的隶属函数是困难的。 本文所引入的时间模糊集理论函数是根据可能性理论来表示和计算时间的不 确定性的。这里给出一种模糊时间函数涉及的可能性分布定义：令y 是一个在x 中取值的变量，那么与y 有关的可能性分布l - i v x - 0 ，1 1 来表示。本文对于某一 事件发生的可能性测度用可能性度量p o s s 表示，即p o s s = s u p 兀y ( y ) l y e x ，p o s se 【o ，1 】。 具体的模糊时间函数的定义在2 4 小节中给出，在第四章算法的相关运算中 将给出针对时问不确定性问题的可能性分布的运算方法。 2 3 现有的时间知识表示 人工智能的研究领域中，常识知识的表示具有一定的重要性，但常识知识的 形式化描述也有一定的困难。例如，自然语言理解，空间的表示和推理，物理过 程和事件的形式化描述，以及时间知识的表示等等。 时间的描述本身具有不确定性，时间作为一种常识知识，其表示具有一定的 难度，如何恰当合理表示这种不确定的时间知识是众多应用系统的关键问题【 0 1 ， 基于p e t r i 网的时间知识推理算法的研究 也是知识表示领域研究的热点【4 3 4 9 1 。一般来说，事件、过程或者计算都发生在时 间里，系统中首先需要一个全局时间作为系统参数，时间知识表示方法或者将时 间作为事件或过程的“容器”，即作为一个区间，或者将时间作为事件或过程的一 种属性，即标记为一种属性的度量值。 现有的时间知识表示采用的方法有时间点和时间区间，二者都存在一定的局 限性。采用单一的时间点来表示应用系统的时间知识，不能表达出时间知识的不 确定性，既不实际也不完整：采用时间区间表示方法，对时间的不确定性缺乏定 量的分析。下面给出时问p e t r i 网( 见定义3 3 ) 中用到的时间区间的概念【8 , 9 1 ，以 便与模糊时间函数进行对比。 定义2 1 时间区间 在时间p e t r i 网中，每个变迁都关联一个时间区间【a ，b 】，且a m 2 。 定义3 6 事件 模糊时间p e t r i 网系统中的每个事件对应于系统中的一个变迁；事件与三种因 素有关，可以用三元组( ，b 。，6 。，) 表示和说明：，是事件关联的变迁，6 。是变迁r 触发所需的输入托肯的集合，b o u t 是变迁r 触发后产生的托肯的集合，集合均用 p ，托) i p 只n ( x ) e f t 并且不为o r 表示。对应变迁输出弧的模糊延迟时间， 是描述和分析事件的一种时间度量。 定义3 7f t p n 的变迁触发策略 本文所定义的f t p n 是面向一类复杂系统的时间不确定性的分析，变迁的触 发无延迟时间。在无冲突的情况下，变迁触发所需的托肯全部到达后，立刻触发 变迁；对于有冲突的变迁，系统要确定不同的触发策略，这是系统的决策问题， 面向不同的分析问题，可采用的触发策略有：( 1 ) 最早使能时间触发策略；( 2 ) 多触发条件优先策略；( 3 ) 高可能性优先策略；( 4 ) 混合策略等等。采用不同的 触发策略，可以凸现系统的关键事件、简化系统的建模和分析。 基于p e t r i 网的时间知识推理算法的研究 第四章基于f t p n 的时间知识推理算法 由于已有的基于时间p e t r i 网( t p n ) 的时间知识推理算法【8 2 】具有一定的局 限性，如知识表示的不精确、缺乏定量分析、算法推理过程复杂等。本文基于模 糊时间p e t r i 网( f t p n ) 提出一种新的时间知识推理算法。下面对f t p n 时间知 识推理算法的基本思想、主要运算以及算法相关实现进行说明。 4 1f t p n 算法思想 f t p n 时间知识推理算法是将模糊集合理论和p e t r i 网理论相结合提出的对时 间不确定性知识进行定量推理分析的一种方法。该算法的推理过程是基于模糊时 间函数的运算过程和对p e t r i 网( 作为有向图) 的遍历而得到的。下面是算法的基 本思想描述： 输入：p e t r i 网模型，时间知识 输出：最终模糊时间片和相关路径信息 过程： ( 1 ) 从初始库所开始，初始库所给定初始的时间片。得到不考虑时间约 束的变迁序列； ( 2 ) 从变迁序列首部中取出一个变迁，找到它的所有输入库所，根据模 糊时间函数的计算结果，判断该变迁是否发生，若发生则更新该变迁输出库 所的时间信息和路径信息然后从变迁序列中读取下一个变迁；若不发生， 则直接读取下一个变迁。直到遍历完变迁序列。 4 2 算法中相关运算说明 基于f t p n 的时间知识推理算法是根据模糊时间函数的相关运算方法得到的， 模糊时间函数中模糊使能时间、模糊发生时问涉及到最迟时间可能性分布的计算 l a t e s t 、最早时间可能性分布的计算e a r l i e s t 和最小操作m i n ，见公式( 1 ) ( 2 ) 。本 小节对l a t e s t , e a r l i e s t 和m i n 的计算方法进行了详细讨论。 4 2 1 最迟时间可能性分布的计算l a t e s t 最迟时间可能性分布用于计算事件的模糊使能时间。l a t e s t 是一个多元运算 1 4 基于p e t r 嘲的时间知识推理算法的研究 符，用于求多个模糊时间片的最迟可能性分布。设有n 个模糊时间片 兀i o ) = h i a i ，b i ，c i ，d i ，i = 1 ，2 ，n ，h i 是可能性度量p o s s ，则： l a t e s t h i ( x ) ，滓l ，2 ，n ) = l a t e s t l a t e s t t a t e s t r q 和) ，m ) j ，4 j 0 ) ，) 舳0 ) 其中，l a t e s t h i ( x ) ，砣o ) 的计算可以分以下情形进行讨论： ( 1 ) 当两个时间片的可能性度量值相同，或者较晚到达的时间片可能性度量 值较小时，如图4 1 中( a ) ( b ) 两种情况( 斜线相交的情况可近似归入该情形) 。 此时p o s s = m i n ( h i ，h 2 ) ，l a t e s t 的计算方法是求出这两个模糊时间片的四个分量各 自的最大值，组合成模糊时间函数的四元组，即： l a t e s t n 1 而 ) 2 m i n ( h l ，h 2 ) m a x ( a t ，a 2 ) ，m a x c o l ，5 2 ) ，m a x ( c 1 ，c 2 ) ，m a x ( d l ，d 2 ) 】 例如：对于一个需要两个托肯( 资源) 的事件，其相应的模糊时间片是 兀l ( t ) = 0 ，l ，5 ，6 】和耳2 = 【l ，2 ，3 ，4 】，则该事件的模糊使能时间e = l a t e s t n f f x ) , n 2 ( t ) ) = 1 ，2 ，5 ，6 】，p o s s = l ，如图4 1 ( a ) 所示：当m o ) = 【o ，l ，4 ，5 】和他0 ) = o 5 【1 ，2 , 5 ，6 】时， l a t e s t x 1 4 2 = o 5 d ，2 ，5 ，6 】，p o s s = 0 5 ，见图4 1 嘞。 12 345 6 t ( a ) 两个模糊时间片的可能性度量值相同 l234 5 6t ( b ) 较晚到达的时间片可能性度量值较小 图4 1 可能性度量值相同或较晚到达度量值较小时的l a t e s t 计算 ( 2 ) 当两个时间片的可能性度量值不同，可以分为图4 2 ( a ) c o ) ( c ) z 种情况 设h i h 2 ，则p o s s = h 2 ，三种情况的计算方法如下： l a t e s t x l ( t ) , u 2 ( t ) ) = h 2 m a x ( a 1 ，a 2 ) ，x ，m a x ( e l ，c 2 ) ，m a x ( d 1 ，d 2 ) ( 9l a t e s t h i ( x ) ，勋( t ) ) = h 2 m a x ( a i ，a 2 ) ，m a x ( b l ，b 2 ) ，y ，m a x ( d l ，d 2 ) 】 基于p e t r i 网的时间知识推理算法的研究 ( dl a t e s t n l ( x ) , 9 2 ( x ) = h 2 m a x ( as ，a z ) ，x ，y ，m a x ( d 1 ，d 2 ) 】 其中，x = a l + h 2 m l ( h i a t ) ，y = d l h 2 h l ( d l c t ) 例如，模糊时间片兀l o ) = o 5 0 ，l ，4 ，5 】和规0 ) = 【l ，2 , 5 ，7 】，如图4 ，2 ( c ) 所示。由 上述计算方法可得，p o s s = 0 ，5 ，x = 1 5 ，y = 6 ，则该事件的模糊使能时间函数为 e 0 ) = l a t e s t n l ( t ) , n 2 = 0 5 1 ，1 5 ，6 ，7 】，p o s s = o 5 ，如图4 2 ( c ) 粗线所示 ( a ) 计算左侧交叉的x 值 ( b ) 计算右侧的y 值 ( c ) 两侧均需要计算x 与y 值 图4 2 可能性度量不同时的l a t e s t 计算方法 4 2 2 最早时间可能性分布的计算e a r l i e s t 在计算模糊发生时间时，采用先来先服务原则给较早使能的事件赋予较高的 优先权，即需要计算所有事件的模糊使能时间中最早时间的可能性分布。本小节 讨论最早时间可能性分布e a r l i e s t 的计算方法。 e a r l i e s t 是用于求多个模糊时间片的最早可能性分布的操作。设有n 个模糊时 阳j 片7 【0 ) = h i 【a i ，b i ，c - i ，d i ，i = 1 , 2 ，n ，贝： 1 6 骥 矶 0 基于p c 仃i 网的时问知识推理算法的研究 e a r l i e s t h i ( x ) ，i = 1 ，2 ，n ) 2 e a r l i e s t e a r l i e s t e a r l i e s t r q ( x ) , n 2 ) ，再i ( t ) ，) ，k 0 ) 其中，e a r l i e s t ，h ( z ) ，砣0 ) ) 采用下面的计算方法： e a r t i e s t g l ( x ) , n 2 ( x ) = m a h l ，h 2 ) m i n ( a l ，a 2 ) ，m i b l ，b 2 ) ，m i n ( c l ，c 2 ) ，m i n ( d l ，d 2 ) 】 下面给出e a r l i e s t h i ( x ) ，啦) 的计算算例对上述计算方法进行说明： 算例：两个事件的使能时间为e l ( t ) = o 5 0 ，1 ，6 ，7 1 ，e 2 0 ) = 【1 ，3 ，3 ，5 】，模糊发生时 间的计算和e a r l i e s t 的计算如下，其中m i n 的计算方法在4 2 3 小节中有详细说明。 ( 1 ) 计算过程中可能性度量取较小值，即p o s s = m i n ( h l ，h 2 ) ，则 e a r l i e s t 扣l ，现0 ) ) 2r a i n ( h l ，h 2 ) m i n ( a l ，a 2 ) ，m i n ( b l ，b 2 ) ，m i n ( c l ，c 2 ) ，m i n ( d l ，d 2 ) e a r l i e s t z q ( z ) ，i = l ，2 ，n 2 e a r l i e s t e a r l i e s t g 研，招“ 7 【1 0 ) 冉2 0 ) ，兀i 0 ) ) ，) 皿n 0 ) 算例的计算结果如图4 _ 3 粗线所示： e a r l i e s t e l ，e 2 = 0 5 【o ，i ，3 ，5 】； o i 5 m i n e ，e a r l i e s t e l ( 0 ，e 2 ) ) - m i n o 5 0 ，1 ，6 ，7 】，o 5 【o ，l ，3 ，5 】 = o 5 1 0 ，1 ，3 ，5 】； o 撕) i m i n e a ( c ) ，e a r l i e s t e l ，e 2 2 m i n 1 ，3 ，3 ，5 】，o 5 【o ，1 ，3 ，5 】) 2 o 5 1 ，2 ，3 ，5 】 123 45 67t 图4 , 3 可能性度量取较小德对e a r l i e s t 的计算结果 ( 2 ) 计算过程中可能性度量取较大值，即p o s s = m a x 0 1 l ，h 2 ) ，则 e a r l i e s t 伽l o ) ，尬 2 m a x ( h i ，h 2 ) 【m i n ( a l ，a 2 ) ，m i n ( b l ，b 2 ) ，m i n ( c l ，c 2 ) ，m i n ( d l ，d 2 ) 】 e 训f 哪 氕，( t ) ，i 2 1 ，2 ，n ) = e a r l i e s t e a r l i e s t e a r l i e s t r q 小2 0 ) ) ，兀i 0 ) ) ，) ，兀。0 算例的计算结果如图4 4 所示： e a r l i e s t e 1 0 ) ，e 2 ( d = 【o ，1 ，3 ，5 】； o l 2 m e l ( 寸，e a r l i e s t e l ，e 2 ) ；m i n o 5 0 ，1 ，6 ，7 】， o ，1 ，3 ，5 】) = 0 5 0 ，l ，4 ，5 】； 0 2 ( x ) ：m i n e 2 ( x ) ，e a r l i e s t e l o ) ，e 2 ( d ) = m i n 1 ，3 ，3 ，5 】，【o ，1 ，3 ，5 j ) = 【1 , 3 ，3 ，5 】 1 7 基于p e t i i 网的时间知识推理算法的研究 l234567t 图4 4 可能性度量取较大值时e a r l i e s t 的计算结果 ( 3 ) 按照y iz h o u 在文献 2 5 1 q ，定义的e a r l