下载文档原格式
长沙理工大学硕士学位论文基于时间Petri网的并行测试研究姓名：肖良清申请学位级别：硕士专业：计算机软件与理论指导教师：乐晓波20100301摘并行测试技术是ＡＴＳ（Ａｕｔｏ要ＴｅｓｔＳｙｓｔｅｍ）在进一步降低测试的时间、削减测试的成本的趋势下新兴的一项技术，它正以不可比拟的优势成为下～代ＡＴＳ发展的热点。
在运用并行测试技术时，要求分析系统执行过程中可能产生的冲突和竞争情况，特别是如何生成并行测试序列一直是一个复杂的、难于优化的ＮＰ难题。
Ｐｅｔｒｉ网作为一种图形化建模工具，可以很直观的表示系统并发、异步等系统常见现象，而引入时间Ｐｅｔｒｉ网，可以更便捷地描述实时系统。
因此，进一步发展并行测试技术理论和拓宽并行测试应用领域的关键在于：如何建立准确、可靠的并行测试时间Ｐｅｔｒｉ网模型，并在所建模型的基础上，探讨并行测试的任务调度算法。
本文在探讨时间Ｐｅｔｒｉ网构建过程中的约简步骤，并深入分析现今并行测试任务模型不足的基础上，提出了一种基于时间Ｐｅｔｒｉ网的并行测试建模方法。
为说明该方法的应用步骤，选用一雷达接收机的实例建立相应的时间Ｐｅｔｒｉ网，并对其进行了动态性质分析。
在此基础上，详细研究了群智能的各类优化算法，结合时间Ｐｅｔｒｉ网的特点和现有并行调度算法的局限，提出了一种基于遗传一蚁群算法的时间Ｐｅｔｒｉ网变迁序列求解算法，针对一雷达接收机的具体实例，快速地求得了最优调度方案。
仿真实验表明，与现有研究成果相比，本文所提出的算法效率更高，具有重要的实用价值。
关键词：并行测试；任务调度；时间Ｐｅｔｒｉ网；变迁序列；遗传一蚁群算法ＡＢＳＴＲＡＣＴＰａｒａｌｌｅｌｔｅｓｔｔｅｃｈｎｉｑｕｅｉｓａｎｅｗｔｅｃｈｎｉｑｕｅａｒｉｓｉｎｇｕｎｄｅｒｔｈｅｔｅｎｄｅｎｃｙｏｆｓｒｅｄｕｃｉｎｇｔｅｓｔｔｉｍｅａｎｄｌｏｗｉｎｇｔｅｓｔｃｏｓｔ，ｗｈｉｃｈｉｎｅｘｔｂｅｃｏｍｉｎｇｈｏｔｓｐｏｔｏｆｔｈｅＡＴＳｆｏｒｕｎｐａｒａｌｌｅｌｅｄａｄｖａｎｔａｇｅ．Ｔｈｅｐａｒａｌｌｅｌｔｅｓｔｓｙｓｔｅｍｒｅｑｕｉｒｅｓｔｈｅｒｕｎａｎａｌｙｓｉｓｏｆｃｏｍｐｅｔｉｔｉｏｎａｎｄｃｏｎｆｌｉｃｔｉｎｔｉｍｅ，Ｗｏｒｓｅｍｏｒｅ，ｔｈｅｏｐｔｉｍｉｚｅｄａｐａｒａｌｌｅｌｔｅｓｔｔａｓｋｓｃｈｅｄｕｌｉｎｇｓｅｑｕｅｎｃｅｈａｓｂｅｅｎＮＰｐｒｏｂｌｅｍ．Ｐｅｔｒｉｎｅｔ，ａｓａｃｏｍｐｌｉｃａｔｅｄａｎｄｄｉｆｆｉｃｕｌｔｃａｎｇｒａｐｈｉｃａｌｍｏｄｅｌｉｎｇｔｏｏｌ，ｗｈｉｃｈｒｅｐｒｅｓｅｎｔｃｏｎｃｕｒｒｅｎｃｅ，ａｓｙｎｃｈｒｏｎｙｉｎｉｎｔｕｉｔｉｖｅｗａｙ，ｈａｓｂｅｅｎｗｉｄｅｌｙｕｓｅｄｉｎｖａｒｉｏｕｓｃａｎｆｉｅｌｄｓ．Ａｔｔｈｅｓａｍｅｔｉｍｅ，ｔｈｅｉｎｔｒｏｄｕｃｔｉｏｎｏｆＴｉｍｅｄＰｅｔｒｉｎｅｔｃｏｎｖｅｎｉｅｎｔｔｏｄｅｖｅｌｏｐｍｅｎｔｂｅｍｏｒｅｄｅｓｃｒｉｂｅｔｈｅｒｅａｌ—ｔｉｍｅｓｙｓｔｅｍ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｅｋｅｙｏｆｆｕｒｔｈｅｒｏｆｔｈｅｔｈｅｏｒｙｔｅｓｔｏｆｉｓｐａｒａｌｌｅｌｈｏｗｔｏｔｅｓｔｔｅｃｈｎｏｌｏｇｙ，ａｎｄａｎｂｒｏａｄｅｎｔｈｅａｐｐｌｉｃａｔｉｏｎｏｆｐａｒａｌｌｅｌｅｓｔａｂｌｉｓｈｔｏａｃｃｕｒａｔｅａｎｄｒｅｌｉａｂｌｅｔｅｓｔＴｉｍｅｄＰｅｔｒｉｎｅｔｍｏｄｅｌｏｎｆｏｒｐａｒａｌｌｅｌｔｅｓｔ，ａｎｄｓｔｕｄｙｐａｒａｌｌｅｌｔａｓｋｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍＩｎｔｈｉｓｔｈｅｂａｓｉｓｏｆｔｈｅｍｏｄｅｌａｃｔｉｖｉｔｙ．ｏｎａｒｔｉｃｌｅ，ｂａｓｅｄａｎｄａｎａｌｙｚｉｎｇｄｉｓｃｕｓｓｉｎｇｔｈｅｐｒｏｃｅｄｕｒｅｏｆｓｉｍｐｌｉｆｙｉｎｇｓｈｏｒｔａｇｅｏｆｃｕｒｒｅｎｔａＴＰＮｍｏｄｅｌｐｒｏｐｏｓｅｄｏｒｄｅｒｔｏａｔｈｅｐａｒａｌｌｅｌｔｅｓｔｍｏｄｅｌ，ｍｏｄｅｌｉｎｇｍｅｔｈｏｄｆｏｒｐａｒａｌｌｅｌｔｅｓｔｂａｓｅｄｏｎＴｉｍｅｄＰｅｔｒｉｎｅｔ．Ｉｎａｎｅｘｐｌａｉｎｔｈｅｍｅｔｈｏｄｆｏｒａｐｐｌｉｃａｔｉｏｎｏｆｓｔｅｐｓ，ｕｓｅｄｉｎｓｔａｎｃｅｏｆｒａｄａｒｒｅｃｅｉｖｅｒｔｏｅｓｔａｂｌｉｓｈｔｈｅｃｏｒｒｅｓｐｏｎｄｉｎｇＴｉｍｅｄＰｅｔｒｉｎｅｔ，ａｌｓｏｓｔｕｄｉｅｄｔｈｅｄｙｎａｍｉｃｎａｔｕｒｅｏｆｔｈｅｍｏｄｅｌ．Ｏｎｔｈｉｓｂａｓｉｓ，ａｄｅｔａｉｌｅｄｓｔｕｄｙｏｆｖａｒｉｏｕｓｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｓｏｆｓｗａｒｍｉｎｔｅｌｌｉｇｅｎｃｅｃｏｍｂｉｎｅｄｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆＴｉｍｅｄＰｅｔｒｉｎｅｔｗｉｔｈｔｈｅｌｉｍｉｔａｔｉｏｎｓｏｆｅｘｉｓｔｉｎｇｐａｒａｌｌｅｌｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍｓ，ａｎａｌｇｏｒｉｔｈｍｏｆｅｘｐｌｏｒｉｎｇｔｒａｎｓｉｔｉｏｎｓｅｑｕｅｎｃｅｏｆＴｉｍｅｄＰｅｔｒｉｎｅｔｂａｓｅｄｏｎｇｅｎｅｔｉｃ—ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｉｓｏｒｉｇｉｎａｌｌｙｐｒｏｐｏｓｅｄ．Ｔｈｅｏｐｔｉｍａｌｃａｎｓｃｈｅｄｕｌｉｎｇｂｅｆｏｕｎｄｉｎｏｎａａｖｅｒｙｓｈｏｒｔｐｅｒｉｏｄｏｆｔｉｍｅｗａｓｐｒｅｓｅｎｔｅｄｉｎｔｅｒｍｓｏｆｃｏｍｐａｒｅｄａｎｅｘａｍｐｌｅｔｈｅｒａｄａｒｒｅｃｅｉｖｅｒ．Ｓｉｍｕｌａｔｅｄｅｘｐｅｒｉｍｅｎｔｓｈｏｗｓｔｈａｔｒｅｓｅａｒｃｈｒｅｓｕｌｔｓ，ｔｈｅｇｉｖｅｎｗｉｔｈｅｘｉｓｔｉｎｇａｌｇｏｒｉｔｈｍｈａｓＩｌｉｍｐｏｒｔａｎｔｐｒａｃｔｉｃａｌｖａｌｕｅｆｏｒｍｏｒｅｅｆｆｉｃｉｅｎｃｙ．Ｋｅｙｗｏｒｄｓ：ｐａｒａｌｌｅｌｔｅｓｔ；ｔａｓｋｓｃｈｅｄｕｌｉｎｇ；ＴｉｍｅｄＰｅｔｒｉｎｅｔ；ｔｒａｎｓｉｔｉｏｎｓｅｑｕｅｎｃｅ；ｇｅｎｅｔｉｃ－ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｎｌＩＩＩ长沙理工大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。
Petri网的原理及应用1. 什么是Petri网Petri网是一种用于描述并发系统和并发性行为的图形化工具和形式化方法。
它由德国数学家Carl Adam Petri于1962年提出，被广泛应用于系统建模、并发系统分析、协议验证等领域。
Petri网可以模拟并发系统的并发行为、状态转换以及资源分配等关键方面，通过图形化的方式直观地展示系统的结构和行为，并支持形式化的数学分析。
2. Petri网的基本元素Petri网由以下基本元素组成：2.1. 位置（Place）位置表示系统中的状态或者条件，通常通过一个圆圈表示。
位置可以存储某种资源或者表示某种变量的取值。
2.2. 过渡（Transition）过渡表示系统中的某种事件或者操作，通常通过一个矩形表示。
过渡可以触发或消耗位置中的资源，改变系统的状态。
2.3. 弧（Arc）弧表示位置和过渡之间的联系，通常通过一条带箭头的线表示。
弧可以表示资源的流动或者触发条件的关系，连接位置和过渡。
2.4. 标识（Marking）标识是位置中的资源的数量，可以通过在位置内部的小圆圈中填写数字来表示。
标识表示系统的状态，在Petri网中可以不断变化。
3. Petri网的建模方法Petri网可以通过以下步骤完成建模：3.1. 确定系统的功能和行为首先，需要明确系统的功能和行为，清楚系统中的位置、过渡以及它们之间的关系。
例如，一个简单的交通信号灯系统中可以有位置表示红绿灯状态、过渡表示信号灯变换的事件或操作。
3.2. 绘制Petri网图根据系统的功能和行为，使用标识符绘制位置和过渡，并用弧表示它们之间的联系。
根据需要，可以使用不同的符号和颜色来表示不同类型的位置和过渡。
3.3. 设定初始标识确定初始状态下位置中的资源数量，填写在位置的小圆圈中。
这可以表示系统的初始状态，即Petri网的初始标识。
3.4. 定义触发条件和行为规则根据系统的功能和行为，定义位置和过渡之间的触发条件和行为规则。
模糊Petri网在汽车故障诊断中的应用研究的开题报告一、选题背景随着现代汽车电子技术的快速发展，尤其是OBD(On-Board Diagnostic，车载诊断)系统的广泛应用，汽车故障诊断技术已经成为了汽车维修领域的一个重要问题。
传统故障诊断方法主要依赖于专业技师的经验，对于某些复杂的故障诊断只能通过不断尝试和调试来寻找问题，造成不必要的时间和精力的浪费。
如何提高汽车故障诊断的精确度和效率，成为了汽车维修界的新课题。
Petri网是一种描述并发系统的图形语言和分析工具，已经广泛应用于各种领域。
Petri网是一个有向图，分为两类元素：位置和变迁，能够用来描述对象（如汽车）的状态和对象之间的关系。
Petri网具有可视化、易于理解和形式化分析的特点，是一种有效的工具。
模糊理论是一种能够处理不确定性问题的数学理论，其核心思想是用隶属度函数来描述事物之间的模糊关系。
模糊Petri网是将模糊理论与Petri网相结合进行建模，能够更好地描述系统的模糊性和不确定性。
本研究将探讨将模糊Petri网应用于汽车故障诊断中的可行性，并尝试建立模糊Petri网模型用于汽车故障诊断，以提高汽车故障诊断的精确度和效率。
二、研究目的本研究的主要目的是探讨模糊Petri网在汽车故障诊断中的应用，建立模糊Petri 网模型并验证其可行性。
具体研究目标如下：1.了解汽车故障诊断的相关理论知识和现状；2.研究Petri网与模糊理论的基本原理和相关技术；3.分析汽车故障诊断问题的特点和复杂度，探讨模糊Petri网在该领域中的应用；4.建立基于模糊Petri网的汽车故障诊断模型，验证其可行性和有效性；5.在现有汽车故障诊断方法中比较模糊Petri网模型的优劣，总结模型的特点和优点。
三、研究内容和方法本研究的主要内容是探讨模糊Petri网在汽车故障诊断中的应用，并建立模糊Petri网模型用于汽车故障诊断。
具体的研究内容和方法如下：1.文献研究法。
基于面向方面的Petri网在实时系统中的应用摘要：petri网作为一种图形化的建模方法，具有直观易用的特点，是业务流程建模常用方法。
面向方面建模的基本思想是按系统特征划分程序模块。
传统的实时系统与时间密切相关。
我们分离实时系统时间方面，然后用时间petri网来建模，最后通过实例来简单地说明建模过程。
关键词：时间petri网；面向方面；实时系统；关注点aspect-oriented petri net applications in real-time systems cai rewen,zhang lichen,yang min(faculty of computer,guangdong university of technology,guangzhou510006,china)abstract:petri net as a graphical way of modeling is frequently used in business process model,for its presentation is visualized and its operation is simple.the basic idea of aspect-oriented modeling is to divide the modules according to the features of the system.the traditional real-time system is strictly related to the time.first,we separate the aspect of the time in the real-time system.then we use time petri net to model it.finally, we introduce the modeling process according a use case. keyword:time petri net;aspect-oriented;real-timesystem;concernspetri网在数学上是建模和检验软件产品的基本技术。
成绩Petri网在生物信息学中的应用摘要:生物信息学是一门正在快速发展的使用数学和计算机技术来构造和分析生物学模型的学科．Petri网是近来被用于生物信息学的有效工具，但是应用的深度和广度还有待深入研究．文中综述了Petri网在生物信息学领域应用的最新研究进展，主要包括三个方面：应用位置／变迁网定性分析生物学对象的结构性质；应用随机Petri网将随机性加入到生物学建模和分析中；应用混合Petri网描述和分析同时具有离散特性和连续特性的生物系统．最后对Petri 网在生物信息学领域的应用情况进行总结并展望了未来的研究方向．关键词:生物信息学；Perti网；生物学网络；拓扑分析；生物学模拟Application of Petri Nets to BioinformaticsAbstract: Bioinformatics is a rapidly developing discipline that takes advantage of mathematics and computer technology to construct and analyze biological models．Petri nets are efficient tools used in Bioinformatics recently，while their application needs to be further expanded．The survey which this paper provides of the application of Petri nets in Bioinformatics study includes three parts：Using place／transition system to qualitatively analyze structural properties of biological objects；using stochastic Petri nets to add stochastic properties to biological modeling and analysis；using hybrid Petri nets to represent and analyze biological systems with both discrete and continuous properties．Finally，the application of Petri nets in Bioinformatics is summarized and the research directions and open probIems in this area are also discussed．Keywords:bioinformatics；Petri nets；bi0109ical networks；topological analysis；biological simulationPetri网是对信息处理系统进行描述和建模的数学工具之一．Petri网的主要特性包括并行性(concurrency)、不确定性(nondeterminacy)、异步(asychronization)以及对分布式系统的描述能力和分析能力，因而可以应用到很多实际的系统和领域中去．Petri网是一种动态的图形工具，它除了具有类似流程图、框图和网图的可视化描述功能外，还可以通过标记(token)的流动来模拟实际系统的动态行为．[1]Petri网还是一种数学工具，可以通过状态方程、代数方程和其它数学方法来分析系统的行为.生物学的快速发展积累了大量的科学数据，但是人们对这些数据进行挖掘、提取知识的速度却极为缓慢．海量的数据和缓慢的知识增长之间构成了巨大的矛盾．生物信息学正是在这一矛盾下催生的．美国在人类基因组计划实施五年后的总结报告中，对生物信息学做出了如下定义：生物信息学是一门交叉科学，它包含了生物信息的获取、处理、存储、分发、分析和解释等在内的所有方面，它综合运用数学、计算机科学和生物学的各种工具，来阐明和理解大量数据所包含的生物学意义．[2]Petri网可以将直观的图形化表达和成熟完善的数学分析工具很好地结合在一起，相对于其它的建模工具有一定的优势，在生物信息学领域有广泛的应用．一个Petri网口1的结构元素包括：位置(place)、变迁(transition)和弧(arc)．位置用于描述可能的系统局部状态；变迁用于描述修改系统状态的事件；弧用于描述局部状态和事件之间的关系．标记(token)是包含在位置中的一种标识，用于描述Petri网的状态．Petri网的状态通常也称为Petri网的标识(marking)．一个Petri网模型的动态行为是由它的实施规则(firing rule)所规定和控制的．位置／变迁(position／transition)系统在Petri网的基础上做了如下扩展：对位置赋予了位置容量函数.[3] Petri网是一种图形化的，并且有严格数学基础的建模方法，因而基于Petri网的生物信息学模型不仅形象、直观；而且便于验证，没有二义性．[4]在Petri网应用于生物学网络分析以前，有人采用图论的方法描述反应系统，但是这些方法表达能力有限，只能表达单个反应物单个产物的反应，如果遇到多种分子参与的反应，模型的表达就会变得很复杂，并且需要加入很多文字说明，可能会有歧义，不容易分析．进程代数是近年来应用于生物信息学的一种工具，和Petri网一样，进程代数也是一种可以表达并行性、不确定性的数学方法，但是进程代数没有直观的、图形的表达方式．尽管建立定量的模型要比建立定性的模型要求严格，但是定量模型在模拟现实世界方面能提供更多的细节，另外，通过定量模型，可以得到对系统丰富的定性认识.对细胞内生命过程构成的网络的定量建模方法有确定性模型和随机性模型两大类．传统的定量模型是确定性模型，其特点是初始条件完全决定了后继的结果．最常用的确定性模型是微分方程组．依照反应关系，由浓度作用定理(mass action law)等定理得到一组耦合的微分方程．通过解析的方法(只有在方程简单的情况下可行)和数值的方法可以计算微分方程组随时间的演化情况．[5] Petri网在生物信息学中的应用前景是正在逐步发展的，很有希望的．当前Petri 网在生物信息学中应用的研究并不深入，大多数是初步的工作，对生物系统的描述停留在结构水平，没有上升到功能水平．造成这个现象的原因是两方面的，一方面是当前实验技术的限制，获得大量完整的生物学数据有难度，另一方面是Petri 网理论需要改进以适合生物信息学的应用．对将来Petri网在生物信息学中的发展展望，一方面可以为Petri网在生物领域寻找新的应用点，另一方面可以改进计算工具，使Petri网适合生物信息学的应用，例如可以考虑将模型抽象和精化设计、分解和压缩技术引入建模中，以降低模型的复杂性；可以将混合Petri网与随机Petri网结合起来，使Petri网的建模能力更强大．将来基于Petri网的生物信息学模型不仅能刻画细胞内的新陈代谢过程，而且可以在模型中整合细胞的基因调节机制、新陈代谢网络和基因调节过程；根据给定的染色体组信息可以提取出基因信息，进而模拟和预测有机体的行为和功能；不仅能描述单个细胞内的生命过程，而且能描述细胞与细胞之间的关系，乃至生物体内各部分之间的紧密联系．参考文献:[1] Petri c A．Kommunikation mit Automaten．Bonn：schriftendes Instituts fur InstrumentelIeMathematik,1962,87(3)：298-413.[2] 王正华，周婷婷．大规模代谢网络分饵的生物信息学研究[J]．国防科技大学学报，2006，30(3)：48-53．[3] Jacques Cohen．Bioinformatics—An introduction for computer scientists．ACM ComputingSunreys，2004，36(2)：122—158.[4] Murata T．Petri nets：Properties，analysis and applications．Proceedings of the IEEE，1989，77(4)：541—580.[5] Peterson James L Petri Net Theory and the Modeling of Systems．Englewood Cliffs，NJ：Prentice-Hall，1981,45(9)：124-135.。
