分类号 密级 UDC 编号
中国科学院研究生院
硕士学位论文
Petri网系统的可达性研究
吴 文 渊
指导教师 杨 路 研究员
中国科学院成都计算机应用研究所
申请学位级别 硕 士 学科专业名称 计算机软件及理论 论文提交日期 论文答辩日期
培养单位 中国科学院成都计算机应用研究所 学位授予单位 中国科学院研究生院
答辩委员会主席
摘 要..........................................................................................................................II ABSTRACT ............................................................................................................. IV 前 言........................................................................................................................ VI 第一章
背景知识 ................................................................................................ 1
§1.1 历史与发展.................................................................................................. 1 §1.2 研究方法及应用.......................................................................................... 1 §1.3 Petri网的直观理解 ..................................................................................... 2 §1.4 Petri网的形式化描述 ................................................................................. 2
第二章 Petri网与代数系统的关系............................................................... 6
§2.1 Petri网模型映射到代数系统 ..................................................................... 6 §2.2 基于Grobner基的Petri网系统性质分析................................................. 8 §2.3 Maple符号计算软件介绍[14].................................................................. 12 §2.4 计算代数方法的局限性............................................................................ 14
第三章 能量优化模型 ....................................................................................... 15
§3.1 Petri网系统映射到线性空间 ................................................................... 15 §3.2 弱可达性及其分析.................................................................................... 17 §3.3 能量优化模型建立和分析........................................................................ 20
第四章 可达性的神经网络解法 .................................................................... 24
§4.1 神经网络介绍[15] ..................................................................................... 24 §4.2 Hopfield网络模型 .................................................................................... 26 §4.3 能量优化模型的神经网络解法................................................................ 30 §4.4 算法的实现................................................................................................ 32
第五章 综合分析方法 ....................................................................................... 34
§5.1 几种方法的综合比较................................................................................ 34 §5.2 综合分析方法描述.................................................................................... 34 §5.3 综合分析方法总结.................................................................................... 36
第六章 应用实例分析 ....................................................................................... 38 结尾 问题与展望 ................................................................................................ 48
致 谢....................................................................................................................... 49 附 录....................................................................................................................... 50
I
Petri网系统的可达性研究
作者：吴文渊 专业方向：计算机软件及理论 导师：杨路研究员
摘 要
本文对Petri网系统的可达性问题做了综合性的阐述和分析， 提出了利用能量优化方法来解决可达性问题，并在此基础上结合计算代数方法和神经计算模型对可达性问题做了进一步的研究。作者的主要工作在以下四个方面：1. 给出了Petri网到线性空间的映射规则及其可达性的等价性定理；2. 建立了能量优化模型, 将可达性判断化为优化问题；3. 用神经网络来求解能量优化模型；4. 最后综合了计算代数方法和能量优化模型的优点给出一个基于计算代数和神经计算的方法。本文的特点就在于提出了一种利用基于硬件的大规模并行的神经计算来代替基于软件的串行的数字计算的可达性判断解决方案。
在前言中，着重阐述了可达性问题的研究意义，主要困难和目前使用的五类研究方法，在做了简单的评价后，引出我们的研究目的和研究成果。在第一章，简要回顾了Petri网模型的背景知识和研究的历史与发展状况，研究方法和应用范围等背景知识。之后，又介绍了Petri网模型以及相关知识，将该领域的知识框架做了大体说明。
在第二章，主要介绍了计算代数方法。先描述了将Petri网模型映射到代数系统的基本思想，Petri网模型的行为特征对应的代数表示，将可达性问题归结为代数问题。接着讲解了必要的计算代数方面的基础知识，主要讲解了计算代数方法的核心工具－Grobner基，以及计算Grobner基的著名数学软件Maple的使用方法和Grobner基软件包。最后，分析了计算代数方法的局限性。
从第三章开始大部分是作者的工作，在第三章中主要给出了利用能量优化模型及其可达性的等价性定理来解决可达性问题。先说明了该方法思想的出发点和形成过程，之后在该模型下自然诱导出弱可达性概念及其性质。提出利用整数规划方法来处理弱可达性条件，并介绍了相关的数学软件。最后描述了能量优化模型建立的过程和方法。
第四章是针对第三章的能量优化模型提出神经网络的模型计算方案。首先，叙述了神经网络的基础知识，神经计算的特点和应用。之后介绍了神经网络的一种全连接模型－Hopield神经网络，及Hopield网络在能量优化模型的应用。接着对Hopield网络求解能量优化模型的能量函数和相关参数做了计算和分析。最后对神经计算的软件硬件实现做了简单的说明。
II
第五章总结了前几章叙述的各类方法，对其优缺点进行分析比较后提出了综合分析方法，给出了综合分析方法的算法流程。在第六章，以停等协议的Petri网模型为例利用综合分析方法对可达性问题做了分析。最后，本文结尾对Petri网模型的可达性研究的存在问题和将来需要做的工作做了简要阐述和展望。
在附录中给出了用Matlab编写的利用Hopield网络求解能量优化模型的算法程序。
关键词：Petri网模型；可达性；Grobner基；能量优化模型；Hopield神经网络；
弱可达性；综合分析方法；
III