（管理科学与工程专业论文）基于着色petri网在案例推理中应用研究.pdf

基于着色p e t r i 网模型的案例推理应用研究 摘要 目前，案例推理( c a r ) 是一种相似推理方法，其核心在于用过去的实例和经 验来解决问题。它能把提交给系统的新案例同系统内先前的案例相比较，根据 异同性来进行推演，最后来解释或者帮助解决新案例的问题。 对于一个c b r 系统已经有不同的模型和方法来描述它的存储结构和推演算 法，本文在c b r 的基础上引入p e t r i 理论，用着色p e t r i 网来模拟c b r 系统。 不仅能建立直观的图形，还可以将大型复杂的系统层次化，模块化，简化了整 个系统的框架。通过着色的特性，用定义好的颜色集来解决c b r 中复杂特征属 性的表示问题，大大降低c b r 系统的复杂性。形象直观的描述了c b r 系统的 案例推理的过程，同时重要的是通过着色p e t r i 网的分析和验证技术可为c b r 系统的推演提供有效的方法。具体的研究内容有： 1 文中讨论分析了c b r 系统的工作过程和原理，通过对c b r 系统的不足 的分析，在此基础上引入p e t r i 网理论，并提出了基于c b r 系统的p e t r i 网模型 的理论基础和构建步骤。 2 讨论分析了案例的知识表示，将p e t r i 网模型映射为x m l 语言结构， 以及将案例库以x m l 语言描述，并还原成p e t r i 网结构的方法。对p e t r i 网的 连接弧赋予权重，进行案例的模糊匹配。 3 本文着重分析了c b r 的案例检索的特点和检索的方法，并提出基于c b r 的着色p e t r i 网在案例检索中的应用性研究，建立c p n 模型，案例检索的算法 和推理的步骤。 4 本文以白内障诊断的应用为例，用以上的理论构建基于白内障的诊断 c p n 模型，并对模型进行了正确的分析和验证，论证了该模型的可行性和合理 性。 关键词：案例推理；着色p e t r i 网；x m l 语言；案例表示：案例检索； a p p l i c a t i o nr e s e a r c hi nc a s e - b a s e dr e a s o n i n gb a s e d o nc o l o r e dp e t r in e t sm o d e l a b s t r a c t c u r r e n t l y , e a s e b a s e dr e a s o n i n g ( c b r ) i sas i m i l a rr e a s o n i n g ，a n dt h ec o r el i e s w i t ht h ep a s te x a m p l e sa n de x p e r i e n c et os o l v et h ep r o b l e m i tc a l ls u b m i tc a s e st ot h e n e ws y s t e mw i t l lt h es y s t e mc o m p a r e dt ot h ep r e v i o u sc a s e a c c o r d i n gt os i m i l a r i t i e sa n d d i f f e r e n c e sa n dt oc a r r yo u td e d u c t i o n s ，o rt h el a s tt oe x p l a i nt h ec a s et oh e l ps o l v en e w p r o b l e m s f o rac b r s y s t e m sh a v ed i f f e r e n tm o d e l sa n dm e t h o d st od e s c r i b ei t ss t o r a g es t r u c t u r e a n dp u s ha l g o r i t h m s ，t h ep a p e ri nt h ec b ro nt h eb a s i so ft h ei n t r o d u c t i o no fp e t r it h e o r y ， w i t hc o l o r e dp e t r in e tt os i m u l a t ec b r s y s t e m n o to n l yt ob u i l di n t u i t i v eg r a p h i c s ，a l s ob e l a r g ea n dc o m p l e xs y s t e ml e v e l ，m o d u l a r , w h i c hs i m p l i f i e st h ew h o l es y s t e mf r a m e w o r k c o l o r e db yt h ec h a r a c t e r i s t i c so fag o o dd e f i n i t i o no fc o l o r su s e dt os o l v et h ec b rs e ti n t h ec o m p l e xc h a r a c t e r i s t i c so ft h ea t t r i b u t e st h a tp r o b l e ma n dg r e a t l yr e d u c et h ec o m p l e x i t y o ft h ec b r s y s t e m d e s c r i b e st h ev i s u a li m a g eo ft h ec b rs y s t e mo fc a s e - b a s e dr e a s o n i n g p r o c e s s ，i m p o r t a n ti st h a tt h r o u g ht h en e t w o r ko fc o l o r e dp e t r ia n a l y s i sa n dv e r i f i c a t i o n t e c h n o l o g yc a nb ed e d u c e d t op r o v i d ee f f e c t i v em e t h o d t h er e s e a r c ha sf o l l o w s ： 1 i td i s c u s s e st h ec b r s y s t e mi nt h ep r o c e s sa n dp r i n c i p l e so ft h ec b rs y s t e m t h r o u g ht h el a c ko fa n a l y s i so nt h i sb a s i s ，t h ei n t r o d u c t i o no fp e t r in e tt h e o r y , a n d p o i n t e do u tt h a tt h ec b rs y s t e mb a s e do np e t r in e tm o d e lf r o mt h et h e o r e t i c a l f o u n d a t i o na n db u i l ds t e p s 2 i td i s c u s s e st h ec a s eo fk n o w l e d g et h a tw i l lp e t r in e tm o d e lf o rm a p p i n gt h e s t r u c t u r eo fx m l ，a n dt h ec a s ew i l lb ed e s c r i b e di nx m ll a n g u a g ea n dr e s t o r et h e s t r u c t u r eo fp e t r in e tm e t h o d ，g i v et h ew e i g h tt oc o n n e c t e d - a r co fp e t r in e tt oc a r r y o u tt h ef u z z ym a t c h i n gc a s e 3 t h ea r t i c l ef o c u s e so nt h ec b rc a s er e t r i e v a lf e a t u r e sa n dr e t r i e v a lm e t h o d sa n d r a i s e dt h ec o l o r - b a s e dc b rp e t r in e ti nc a s er e t r i e v a lo fa p p l i e dr e s e a r c h , t h ee s t a b l i s h m e n t o fc p nm o d e l ，t h ec a s er e t r i e v a la l g o r i t h m sa n dr e a s o n i n gs t e p s 4 t h ea r t i c l et a k e sd i a g n o s i so fc a t a r a c ta sa ne x a m p l e ，晰t l lm o r et h a n t h e o r e t i c a lc o n s t r u c tb a s e do nt h ed i a g n o s i so fc a t a r a c tc p nm o d e l ，a n dm o d e lt h ec o r r e c t a n a l y s i sa n dv e r i f i c a t i o n , t h em o d e lp r o v e dv i a b l ea n dr a t i o n a l i t y k e y w o r d s ：c a s e b a s e dr e a s o n i n g ；c o l o r e dp e t r in e t s ；x m ll a n g u a g e ；c a s e k n o w l e d g e ；c a s er e t r i e v a l 插图清单 图2 1p e t r i 网基本结构9 图2 2c p n 应用研究概念图1 8 图3 1c b r 系统基本结构图2 2 图3 2c b r 的基本工作流程图2 3 图3 3 案例检索流程图2 5 图3 4c b r 与c p n 结合原理图一2 9 图3 5c p n 应用案例推理流程图3 l 图3 6p e t r i 网d o m 树结构图3 3 图3 7 加权p e t r i 网结构图3 6 图4 1 眼科疾病病例库逻辑结构图4 0 图4 2 案例库检索流程c p n 图4 1 图4 3c p n 模型简化主干图4 3 图4 4c p n 可达树图4 3 表格清单 表4 1 库所、变迁意义表4 1 v i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得金起工些太堂 或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 咒 、 厶， 。 学位论文作者签字：渤力劢 签字日期： 学位论文版权使用授权书 p a 。6 e 易 本学位论文作者完全了解金罡工业太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被 查阅或借阅。本人授权 金目巴王些太堂可以将学位论文的全部或部分论文内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇 编学位论文。 ( 保密的学位论文在解密后适用本授权书) 一厂? 学位论文者签名：国乃 导师签名： 色名阪 签字日期：沙，8 ，c 易 签字日期：乒矽彦占f 莎 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 致谢 写到这里，我的论文终于完成了，掩卷之际，不禁惊叹学海的博大与浩瀚， 并深感自己知识的贫瘠与浅陋。虽然，学生生涯即将结束，但对于知识的追求 与探索，我却不敢止步，“路漫漫其修远兮，吾将上下而求索 。 本论文是在我的导师毛雪岷副教授的悉心指导下完成的。他渊博的科学知 识、严谨的治学态度、一丝不苟的工作作风和精益求精的科研精神，一直是我 学习中的楷模和榜样，都深深地感染和激励着我。三年来，毛老师在学业上给 了我无微不至的关心和帮助，从课题选择到论文的最终完成，毛老师都始终给 予我细心的指导和不懈的支持。在这里，谨向毛老师致以衷心的感谢和崇高的 敬意。 在此，感谢倪志伟老师，张公让老师等其他老师，正是由于各位老师的全 力指导，才能使我克服许多困难和疑惑，从而顺利完成论文的写作。各位老师 渊博的知识、严谨求实的态度、一丝不苟的作风、永远追求卓越的精神为我树 立了一个榜样，是我终身学习的典范。 同时，感谢参加我论文审阅和答辩的各位老师，感谢他们在百忙之中帮助 我完成论文的最后一个过程，这是我莫大的荣幸! 我还要感谢传授我知识的老师和三年同窗的同学们，他们在学习上、工作 上给我不断的支持和鼓励，让我顺利完成了学业。在这里，请接受我诚挚的谢 意! 由于本人水平有限，文中疏漏和错误难免，敬请各位专家对此批评指证! 作者：高方方 2 0 0 8 年6 月9 日 第一章绪论 基于案例推理c b r ( c a s e b a s e dr e a s o n i n g ) 是一种类比推理方法，它提供 了一种近似人类思维模型的建造专家系统的新的方法学，这与人对自然问题的 求解相一致。c b r 专家系统的基本原理是把以前的案例按一定的方式组织起来， 存储到案例知识库中，即以案例知识库模拟人脑的记忆，按一定的组织方式存储 一些过去的相关经历( 案例) ，在求得新解时，通过检索案例知识库，找出与新问题 相似的一个或几个案例，当被检索出的案例与新问题的情况不一致时，对旧的案 例做出修改，以满足新的情况或问题的解。p e t r i 网是信息处理系统描述和建模 的有力工具之一，可以应用到很多系统和领域，p e t r i 网除了具有类似流程图、 框图和网图的可视描述功能外，还可通过t o k e n 的流动来模拟系统的动态和活 动行为。p e t r in e t 具有直观、易懂和易用的优点，它对描述和分析并发现象具 有独到的优越之处；同时又有严格的数学定义，借助数学工具开发的p e t r i 网 分析方法和技术既可以用于静态的结构分析，又可以用于动态的行为分析。目 前随着p e t r i 网理论的成熟和发展，p e t r i 网的应用已经涉及到计算机学科的各 个领域，例如线路设计、软件工程、人工智能、形式语言、操作系统、并行编 译、数据管理等等，可以说所有需要对动态系统进行数学建模的领域，都可以 用它作为分析和研究的工具。 1 1 背景 1 1 1c b r 的产生 推理机制是知识系统中重要组成部分，目前知识系统中的推理机制有三 种：【1 】【2 】 一、基于规则的推理机制r b r ( r u l e - b a s e dr e a s o n i n g ) 基于规则的推理也就是基于领域专家知识和经验的推理，它将专家的知识 和经验抽象为若干推理过程中的如下的规则： i f t h e n 或 它是专家系统中目前普遍采用的推理模式，许多知识系统的开发工具也都 采用这种推理机制，它的优点是比较直观，对推理过程易于理解，同时推理的 效率也比较高。但是r b r 的专家知识和经验的获得比较困难，特别是对于比较 复杂且规则的条件多解的系统，欲比较全面地收集领域专家知识和经验，困难 更大。因此r b r 这种推理机制主要适应于系统不太复杂、领域专家的知识和经 验比较容易收集的中小型知识系统，如维修、教学类知识系统。目前我国大部 分人工智能，特别是专家系统等有关方面的书籍、文献及所建立的人工智能系 统所采用的大都是r b r 推理机制。 二、基于模型的推理机制m b r ( m o d e l b a s e dr e a s o n i n g ) 基于模型的推理是利用作为待解决问题的系统结构或组成要素等的特性、 原理或原则，建立数学模型，然后再利用数学模型结合问题的条件，对系统作 推理、判断，以达到解决系统的目的专家系统中专家知识的语义网络( s e m a n t i c n e t w o r k ) 表示法就是一种模型表示法。显然，并非所有系统都适合采用m b r ， 有些复杂的系统根本无法建立起相应的数学模型。因此m b r 的应用受到了一 定的限制。 三、基于案例的推理机制c b r ( c a s e b a s e dr e a s o n i n g ) 鉴于r b r 和m b r 在应用过程中所遇到的一些困难，特别是在复杂系统中 所遇到的困难迫切需要寻找一种新的推理机制。同时在现实系统中有一些医学 信息系统复杂大系统，在这类系统中有许多分形系统，每一个分形系统通过几 十年的大展，产生了许多适合于不同条件的固定模式，并且在现实工作中往往 根据所给定问题的条件对其模式稍加修改就可得到问题的解。同时对于不同的 模式，都有许多成功案例，这案例是进行系统推理的重要基础。但若将这些案 例中的专家知识和经验抽出作为系统推理的基础有时是非常困难的，甚至是不 可能的，而将这些案例( 环境和模式的组合体) 作为推理的基础，反而会使问题 变得更加简捷。由此便产生了c b r 推理机制，所谓c b r 推理机制就是直接利 用与所给出问题相似的过去的成功实例或失败实例来推理出所求问题的解。 1 1 2c b r 的理论背景 c b r 的形成和发展有着很强的理论背景，主要表现在两个方面p 儿4 j ： 一、c b r 的心理学模型。c b r 是人类的一种认知行为，它是基于记忆的 推理。心理学家提出的语义网络记忆模型只表示了关于世界的静态知识。 t u l v i n g 提出情景记忆作为补充，情景记忆是人对一定时间内发生的事件的记 忆。同时，研究人员在语言理解的任务中发展了类似的理论，如联想记忆等。 s c h a n k 提出了概念记忆理论。概念记忆结合了语义和情景记忆。 二、c b r 与思维模拟。基于案例的推理是人类三种思维德一种综合表现形 式。基于案例的推理符合人类的思维活动。当遇到一个新事物时，专家不仅仅 看到一个具体问题，还会产生联想，然后把事物分类，从中找出以往处理过的 类似问题的经验和相关知识，经过一定的修正处理去解决新事物。对于简单的 问题，案例的检索和匹配主要是形象思维的过程。而对于复杂的问题，往往难 以通过简单匹配检索到一个相似案例；这是我们可以将问题分解，使每个子问 题能映射到一个相似的案例，或从不同角度出发，抽取不同的类似问题，最后 运用逻辑思维和创造性思维把匹配的子案例集成起来，形成解决当前问题的新 方法。 2 1 2c b r 的提出与发展现状 1 2 1c b r 的提出与应用发展历史 c b r 推理机制最早是由美国耶鲁大学的s c h a n k 在1 9 8 2 年出版的专著 d v n a r n i c m e m o r y ；at h e o r yo fk e r n i n d i n ga n dl e a r n i n g i nc o m p u t e r sa i d p e o p l e ) ) 中提出的，在这本专著中s c h u n k 提出了利用专家的经验和知识及利用 专门的实例两种方法来实现专家系统的推理过程的设想。并且k o l o d n e r l 等人 1 9 8 5 年在他们的文献中首次使用了c b r ( c a s e b a s e dr e a s o n i n g ) 这一术语，为 c b r 的建立奠定了基础，其中a s e h 及h a m m o n d ，k j 等人对c b r 也进行了 详细的研究。c b r 的实质是利用过去的实例来引导类推出所求问题的解。因此 c u r l r o n e l l i g 将这种推理方式也称之为“引导类推 ( d e r i v a t i o n a la n a l o g y l 。 c b r 出现以后，美国在8 0 年代后期就这一推理机制的理论与方法进行了 较为系统的研究。初步建立了c b r 的基本结构，并在分类、诊断、计划及设计 等领域内开发了数百个应用实例。例如，用于战斗计划制定与评价的b p a ( b a t t l e p l a na d v i s o r ) 系统，该系统通过系统中包含的6 0 0 个战争案例，通过所给出的 问题条件对类似案例取出进行分析和修正，以得出所求问题的解。1 9 8 8 年 n u v i n c h a n d r a ，d 研制的用于景观设计的c y c l o p s 系统，只要输入目标( 例如： 在农田中盖房子及相应要求) 就能输出可行的方案。目前美国是开展c b r 研究 与开发最普遍的国家。日本在几年前开始c b r 系统的研究与开发，经过近几年 的努力。也建立了数十个用c b r 推理的知识系统。例如，中村孝太郎和小林重 信建立的用于机械调整的支持系统，这种系统采用了用户与系统的对话方式来 对过去的案例进行调整，以求得所求问题的解。我国c b r 的研究与系统开发起 步比较晚。目前国内尚未发现系统地介绍c b r 及其应用软件的报道，但随着人 们认识的提高，这一推理机制必将在我国的人工智能领域中发挥重要的作用。 1 2 2 基于案例推理的研究现状 c b r 克服了传统知识处理系统及工具的一些缺陷【2 儿引，例如当基于规则的 系统遇到一个新问题时，总是试图用规则库中规则的前提或结论进行匹配；当 匹配不成功时，实际上就等于该问题无解。对于c b r 系统，在给定输入的情况 下，系统将搜索案例库，以寻找一个匹配输入特征的现有案例。最好的情况是， 找到完全匹配输入问题的案例，而直接得到对问题的解答，最坏的情况也可能 检索到一个与输入说明相似的案例或案例集，系统或用户可将输入案例作为新 案例存入案例库，使系统具有学习能力。c b r 系统建立重点是案例的表示与组 织，它在相当程度上检索与匹配策略。检索策略的设计要达到两个目的：( 1 ) 检索出的案例尽可能少；( 2 ) 检索出的案例尽可能与当前输入相关或相似。c b r 系统以其知识组织的灵活性、推理设计的综合性、归纳输出的可读性、与多种 诊断方式的互补性及自学习能力而成为人工智能领域中一个极具发展潜力的方 面。与人工智能的其它技术相比，c b r 所需归纳训练系统的时间远少于神经网 络，知识获取要比基于规则的系统容易，推理效率也高，且具有学习的能力。 c b r 技术进一步的研究方向包括：案例库的组织、索引和检索技术、两个 案例相似的概念和模型及相似度的定义、新案例的消化吸收、与其它多种人工 智能技术的综合集成。 1 2 3c b r 目前存在的问题 在c b r 的研究中更多的是方法层次上的研究。应该说，目前c b r 的研究 各方面都有待加强，如事例的录人、表示、检索、重用等方面具体的方法等。 从宏观一点的角度看，c b r 存在的根本问题在于： ( 1 ) 没有严密的理论。尽管c b r 有认知科学和人工智能等一些相关的支持， 但依然没有严格意义上的理论。这也导致了诸如事例重用很难有较通用的技术。 ( 2 ) 没有真正意义上的智能。目前的系统和技术，使得在实际的系统运行中， 一定要有人的参与才行，除了在事例检索上比较成熟外，其他各个方面均需大 力发展，事例的检索也需不断的改进。 ( 3 ) c b r 对噪音数据敏感，错误及冗余数据容易影响系统的检索效率和求 解效果。 ( 4 ) 对于提取案例有困难的领域，需要建立案例工程，但目前案例工程过程 自动化程度不够，案例修正知识和修正规则获取同样存在瓶颈问题。 这些方面要解决的问题不仅仅是c b r 本身要解决的问题，有些涉及的问题 也是人工智能中的一些瓶颈。随着认知科学和脑科学以及人工智能本身的研究 的深入和突破，这些问题也有望随之而解。 1 3p e t r i 网应用研究现状 p e t r i 网是一种用网状图形表示系统模型的方法，它以描述系统中各元素之 间的关系为基础，用网络来表示系统中同时发生、次序发生或循环发生的各种 活动 6 - 9 j 。简单的说，p e t r i 网是一种加权有向网络，其中节点又被分割成两个 非空有限集合，分别称为库所( p l a c e ) 和变迁( t r a n s i t i o n ) ，节点直接用加权的有向 弧连接起来。网络结构是静态的，网络的动态性质通过p l a c e 中t o k e n 的数目及 t r a n s i t i o n 的激发来体现出来。p e t r in e t 的输入是其各p l a c e 中t o k e n 的初始数目， 如果此时一个t r a n s i t i o n 的激发条件能够满足，那么该t r a n s i t i o n 就是使能的， 可以随时被激发，激发后其输出p l a c e 的t o k e n 增加相应弧的权值，这个过程称 为p e t r in e t 的一次状态变化。当一个p e t r in e t 再没有t r a n s i t i o n 可以被激发时， 它就进入了稳定状态。值得注意的是，p e t r in e t 的状态变化过程不但可以用图 形直观的表示出来，而且可以用矩阵运算来描述。这一点使得它可以对同时发 4 生，次序发生或循环发生等各种活动过程进行定性和定量的分析，所以p e t r in e t 是研究内部存在同时发生，次序发生或循环发生等各种活动关系的系统的理想 工具。 1 3 1p e t r i 网的应用 p e t r i 网模型就是一个基于图的数形式化描述模型，用来分析离散的并发 系统，或者说p e t r i 网模型用来描述非同步的因果和非因果行为，包括并行和不 确定选择。p e t r i 网理论研究的主要内容是系统模型的行为特征【l 们，包括：可逆 性( r e v e r s i b i l i t y ) 、有界性( b o u n d e d n e s s ) 、活性( 1 i v e n e s s ) 、可达性( r e a c h a b i l i t y ) 、 可覆盖性( c o v e r ) 、公平性( f a i m e s s ) 等。p e t r i 网以研究模型的组织结构和动态行 为为目标，着眼于系统中可能发生的各种状态变化及变化之间的关系。p e t r i 网 模型的主要分析方法依赖于对诸如关联矩阵、可达树、状态方程、库所不变量、 变迁不变量等的研究与分析。 p e t r i 网模拟以及数学分析方式已广泛应用于网络协议、人工智能、形式语 义、操作系统、并行编译、数据管理等计算机学科的各个领域【1 1 1 。它在多处理 器计算机系统，计算机网络，交通控制系统，柔性制造等方面都有深入、广泛 的应用。发展p e t r i 网计算机是p e t r i 网模型的必然要求和最终目标。 p e t r i 网是可应用到很多系统和领域的图形和数学模型工具 1 2 , 1 3 j 。p e t r i 网 是信息处理系统描述和模型的有力工具之一，作为图形工具，p e t r i 网除了具有 类似流程图、框图和网图的可视描述功能外，它还可通过标记( t o k e n ) 的流动描 述系统的动态和活动行为，所以可以说，p e t r i 是动态图以建立状态方程、代数 方程和其它数学模型来描述系统的行为。p e t r i 网既可为理论工作者也可为工程 人员所使用。它可以作为理论者和实践者之间的通信媒介，以便于人们进行交 流和理解。 随着信息处理的日益庞大和复杂化，人们越来越需要采用系统工程的方法 来设计和维护信息处理流程。在信息处理的整个流程内，采用图形化的数学工 具来完成整个流程的形式描述、正确性验证、性能的分析和目标的实现是必要 的。 1 3 2p 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 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 e t r i 网理论也 在不断地充实和完善，其抽象和描述能力也不断的朝着横向纵向发展。它的纵 向扩展表现为：从基本的条件事件( c e ) n ，库所变迁( p t ) 网，发展到谓词变 迁网和着色网等高级网。它的横向扩展表现为：从无参数的网，发展到时间p e t r i 网和随机p e t r i 网。 1 4 - 1 6 1 4 研究意义 我们之所以用着色p e t r i 网来模拟系统，是因为着色p e t r i ( c p n ) 网最重要 的两大特性【1 7 】：一是具有层次结构，可以从整体到局部、由粗到细地把复杂的 系统分层，逐步细化，突出重点；二是标记的颜色可以是任意复杂的数据，大 大简化了网络的复杂度，提高整体运行的正确性和效率；在p e t r i 网的基础上 引入了颜色的概念，对同类的个体赋予相同的颜色，不同类的个体以不同的颜 色加以区分。这样，一个库所中就可以包含几种对象，或者表达一个复合条件， 一个变迁也可以表达几种不同的变化。另外t o k e n 也增加了颜色，可以描述对 象的属性信息。用这样的有色p e t r i 网来描述c b r 系统过程，可以大大降低 c b r 系统的复杂性，而又易于理解。更重要的是着色p e t r i 网的分析技术可为 c b r 的推演提供有效的方法。 1 5 本文组织及章节安排 c b r 系统是一个复杂的系统，成功地分析和研究需要强有力的建模和分析 手段，案例检索是c b r 中一个重要的环节。本文首先对c b r 系统和p e t r i 网的 一些基本知识进行概述，然后提出构建基于c b r 系统结构的着色p e t r i 网模型 的理论和方法，建立着色p e t r i 网模型。并深入地分析和验证模型。本文的内容 安排如下： 第一章：绪论。先介绍了c b r 的背景及国内外研究现状，c b r 的存在的 问题和不足。然后介绍了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 e t r i 网分析的基本方法。这为文章后面的着色p e t r i 网模型提供了理论依据和方法基 础。 第三章：c b r 及其在c b r 上的着色p e t r i 网应用。本章介绍了案例推的理 论基础和主要工作流程，案例的表示方法，重点介绍了c b r 的检索技术。本章 的重点是在c b r 理论基础上提出了着色p e t r i 网模型的构建的理论和方法，并 建立了c b r 系统结构的c p n 模型。 第四章：基于c b r 的c p n 模型在案例推理中的实际应用。本章主要通过 对案例推理的实例白内障病人诊疗的过程，根据第三章的理论和方法进行着色 6 p e t r i 网模型的建立。模型的分析和验证。 第五章：结论和展望。主要对本文的研究结果进行了总结，并且对以后在 p e t r i 网理论应用于c b r 系统上作进一步的研究提出了设想和展望。 第二章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 e t r i 网在柔性制造系统、通信、机器人任务规划、 计算机并行处理和人工智能等领域得到广泛的应用，在保留了基本p e t r i 网模型 结构和表示方法的基础上，其网络结构也得到不同的扩展模型，主要有：模糊 p e t r i 网( f u z z yp e t r in e t s ) 、随机p e t r i 网( s t o c h a s t i cp e t r in e t s ) 、时序p e t r i 网 ( t i m e dp e t r in e t s ) 、有色p e t r i 网( c o l o r e dp e t r in e t s ) 等。高级p e t r i 网( 包含有色 网和谓词网) 的国际标准正式版已颁布，p e t r i 网理论相关的书籍、期刊、会议、 工具软件和应用方面的资料可以在由德国汉堡大学维护的p e t r i 网专业网站查 看。本章参考文献【7 j 【1 8 , 1 9 l ，给出p e t r i 网基础理论的定义，基本性质和分析方法 等。 2 1p e t r i 网理论 2 1 1p e t r i 网的描述 一、p e t r i 网 p e t r i 网是c a p e t r i 博士于1 9 6 0 年提出的，p e t r i 网以研究系统的组织结 构和动态行为为目标，着眼于系统中可能发生的各种变化及变化之间的关系， 它只关心变化所需条件和变化对系统状态的影响。经典p e t r i 网【9 】【1 6 1 ：经典的 p e t r i 网是简单的过程模型，由两种节点：库所和变迁，有向弧，以及令牌等元 素组成的。如图2 1 所示： 8 t 2 ” 、1 1 图2 1p e t r i 网基本结构 - p e t r i 网的结构 - ( 1 ) p e t r i 网的元素： 库所( p l a c e ) 圆形节点 变迁( t r a n s i t i o n ) 方形节点 有向弧( c o n n e c t i o n ) 是库所和变迁之间的有向弧 令牌( t o k e n ) 是库所中的动态对象，可以从一个库所移动到另一 个库所。 ( 2 ) p e t r i 网的规则是： 有向弧是有方向的 两个库所或变迁之间不允许有弧 库所可以拥有任意数量的令牌 一 行为 如果一个变迁的每个输入库所( i n p u tp l a c e ) 都拥有令牌，该变迁即为 被允许( e n a b l e ) 。一个变迁被允许时，变迁将发生( f i r e ) ，输入库所 ( i n p u tp l a c e ) 的令牌被消耗，同时为输出库所( o u t p u tp l a c e ) 产生令牌。 变迁的发生是原子的 有两个变迁都被允许的可能，但是一次只能发生一个变迁 如果出现一个变迁，其输入库所的个数与输出库所的个数不相等， 令牌的个数将发生变化 p e t r i 网络是静态的 p e t r i 网的状态由令牌在库所的分布决定 - p e t r i 网的形式化定义 一个经典的p e t r i 网由四元组( 库所，变迁，输入函数，输出函数) 组 成。任何图都可以映射到这样一个四元组上，反之亦然。 9 p e t r i 网流程建模 一个流程的状态是由在场所中的令牌建模的，状态的变迁是由变迁建模 的。令牌表示事物( 人，货物，机器) ，信息，条件，或对象的状态；库 所代表库所，通道或地理位置；变迁代表事件，转化或传输。 一个流程有当前状态，可达状态，不可达状态。 - 经典p e t r i 网的局限性 没有测试库所中零令牌的能力 模型容易变得很庞大 模型不能反映时间方面的内容 不支持构造大规模模型，如自顶向下或自底向上 2 1 2p e t r i 网形式化定义 1 定义2 1 ：p e t r i 网( p n ) p n 是一个三元组，即p n = ( p t ，a ) ，其中相应符号的含义为： ( 1 ) p - - p l ，p 2 ，p 3 ，p 。) 为有限的库所集； ( 2 ) t = t l ，t 2 ，t 3 ，t n 为有限的变迁集； ( 3 ) p n t = a ( 集合p 和集合t 不相交) ，p u t a ( 集合p 和集合t 不同时 为空) ； ( 4 ) a ( p x t ) u ( t x p ) 是有限的弧的集合( 流关系仅存在元素p 和t 之间) ； 2 定义2 2 ：普通p e t r i 网系统 一个带标记的普通p e t r i 网系统是六元组= ( 尸，t ，a ，w ，k ，m o ) ，其中： ( 1 ) ( p t a ) 是一个网； ( 2 ) k ：p 一 l ，2 ，3 ， 是库所容量函数； ( 3 ) w ：f 专 l ，2 ，3 ，) 是弧权函数； ( 4 ) m o ：p - - - 0 ，1 ，2 ，3 ， 是初始标识，满足：砌p ：坂( p ) k ( p ) 。 2 1 3p e t r i 网性质 一、相关定义和定理 1 定义2 3 ：关联矩阵和不变量 令艺= ( p ，t ，f ，k ，w ，m o ) 是一个有限的p t 系统，且p = p l ，p 2 ， p n ) ，t = t l ，t 2 ，t m 。 ( 1 ) 矩阵c = h 】( 1 f 玎，1 j m ) 是的关联矩阵当且仅当 c f ，= w ( f ，p f ) 一w ( p f ，t ，) ( 2 ) 一个n 元整数列向量x 叫作的一个p 不变量当且仅当 c r x = 0 ， 其中c r 为c 的转置矩阵。 ( 3 ) 一个m 元整数列向量y 叫作乙的一个t - 不变量当且仅当c y = o 。 1 0 假定m 元非负整数行向量。是。的变迁实施计数向量，亦即a 的第f 元素表 示变迁f 从m o 到m 转换过程中的实施次数，则有：m = m o + c x o 2 定理2 1 ：一个n 维向量x 是的一个p 不变量当且仅当m r 工= 眠r x ， 其中m o 是的初始标识。 3 定理2 2 ：一个m 维向量x 是艺的一个t 不变量当且仅当存在乞的一 个标识m m o ( m o 是e 的初始标识) 和一个变迁实施序列g 从m 回到m ，亦 即，m 专m ，o 的实施计数向量。等于x 。 许多应用问题都关心系统可能的状态，可达标识集是p e t r i 网任何可能发生 序列所能进入的全部状态的集合。可达标识集是解决这类问题的关键，因为用 p e t r i 网模拟协议的正确性的许多问题都可转化为可达性问题。p t 系统的若干 重要性质可以用可达标识集来定义。 4 定义2 4 ：p t 系统乞= ( p ，t ，f ，k ，w ，m o ) 的可达标识集【m o 是 满足下列条件的最小集合： ( 1 ) m o 【m o ； ， ( 2 ) 若有m 【 ，f r ) 使m i t m ，则m m o ； 由以上定义可得： 5 定理2 3 ：若m 【m o ，则存在序列。o = m o t i m l 乞m 2 厶m 。，使得v f ：