基于Petri网紧密度的模型相似性分析——以电力系统为例

孙书亚，叶 静，李 朋

(1.滁州学院数学与金融学院，安徽 滁州 239000； 2.安徽城市管理职业学院公共教学部，合肥 230000；3.滁州职业技术学院电气工程学院，安徽 滁州 239000)

0 引言

业务流程管理是对企业行为执行的一种抽象描述，因此，研究业务流程模型的相似性不仅有利于指导企业的运营发展、优化流程，而且也是部分数据挖掘任务：比如聚类算法、关联规则、贝叶斯分类等的核心研究内容。因此，当前对于模型的相似性分析逐渐成为Petri网业务流程管理系统中的研究重点。

已有的模型相似性度量研究主要集中在以下3个方面：

1)基于模型结构的相似性度量。文献[1]提出了测量参考模型与源模型适合度的度量方法，并以此搜索出符合参考模型的流程模型。文献[2]提出了有效管理业务流程模型的方法，能够根据模型结构或行为有效地查询出大量业务流程模型，进而计算出与候选模型最相似的流程模型。图匹配算法[3]主要应用于模型相似性搜索问题，得出快速贪婪算法获得的平均精度与最穷举算法获得的平均精度较接近的相关结论。

2)基于变迁发生序列的相似性度量。文献[4]定义了相似性和距离的概念，提出了一种使用模型约简技术进行相似性度量的有效计算算法。为了提高模型的检索效率，提出了基于变迁紧邻关系的相似度算法，取名为TAR++算法[5]。文献[6]提出了一种变迁映射关系的相似性度量方法，通过测量不同流程中相同变迁节点的结构相似性来计算过程相似性。

3)基于变迁发生关系的流程相似性度量。文献[7]提出基于活动发生关系的流程相似性度量方法以及基于活动发生关系的流程相似性算法(AOR)，进行业务流程的相似性度量。文献[8]提出了节点编号算法以及最近公共前驱计算方法，在此基础上定义了任务间3种基本的发生关系：因果、并行和互斥，并给出这些关系的高效计算方法和模型相似度计算公式。

综前所述，已有的流程模型相似性研究大多集中在模型结构、变迁序列和变迁活动关系等方面。所研究内容均在参考模型和源模型变迁活动完整表达的情况下，而对于源流程模型与抽象模型相似性的研究较少。因此，本文主要贡献如下：1)利用已有的模型抽象方法，计算出源模型的抽象模型；2)利用变迁后继关系及模型紧密度计算方法计算源模型与抽象模型的紧密度，进一步通过紧密度值判断抽象模型与源模型的相似性程度。

1 基本概念

定义1[9](工作流Petri网)一个网N=(S，T；F，i，o)称为工作流Petri网，当且仅当满足条件：

1)该Petri网有唯一的源库所i：•i=φ；

2)该Petri网有唯一的终止库所o：o•=φ；

3)该Petri网上的每一个节点都属于i到o的一条路径上，即Petri网是强连通的。

(1)

网系统S′与S的紧密度定义为

(2)

2 基于流程模型的行为紧密度计算方法

模型紧密度计算结果取值范围在0～1之间，数值的大小反映了模型相似性程度的大小。一般认为ρ>0.7，模型相似性较高。接下来，以工作流网为例阐述模型紧密度计算过程。工作模型如图1～2所示。

图1 工作流模型M0

图2 工作流模型M0′

3 抽象模型与源模型相似性验证分析

基于第2部分模型紧密度计算方法的介绍，本部分在其基础上首先提出了模型相似性分析算法，其次通过具体的例子分析抽象模型与源模型相似性程度的大小。

算法1：模型相似性分析算法(Model Similarity Analysis Algorithm，简记为MSAA算法)

输入：源模型M1。

输出：抽象模型M2，紧密度数值ρ(M2，M1)。

Step1：首先利用模型抽象化简方法[11]，将源模型M1抽象化简为M2。

Step2：计算模型M1，M2的紧密度数值。

Step2.1：对于任意的变迁对(xi，yj)若满足条件：

1)(xi，yj)⊂M2(T×T)(i=1，2，3，…，n；j=1，2，3，…，n)；

2)(xi，yj)⊂M1(T×T)(i=1，2，3，…，n；j=1，2，3，…，n)；

则可利用公式(1)计算得出c(xi，yj)的值。

Step3：输出模型紧密度数值ρ(M2，M1)并判断源模型与抽象模型的相似性大小，算法结束。

接下来，利用模型抽象化简规则[11]，首先对图3所示模型进行抽象化简；其次，利用变迁后继关系及模型紧密度计算方法进一步度量抽象模型与源模型的相似性。

图3 源流程模型M1

图3所示模型包含了顺序块、并发块和选择块3种块结构，因此以图3为源模型，研究其与抽象模型的相似性具有一定的代表性。对图3源流程模型进行抽象化简得如图4所示模型。

接下来计算ρ(M2，M1)的值，由公式(1)～(2)，首先遍历出模型M2中后继关系为1的变迁对，分别为(C，F)，(F，K)，(F，H)，(H，I)，(H，J)，(I，L)，(J，L)，(K，L)，(L，R)，(L，Q)(R，Q)。代入公式(2)得：

图4 抽象模型M2

抽象模型M2与源模型M1的紧密度值为0.89，最大程度地保留了源模型的结构特征。从一定程度上说明了抽象模型M2与源模型M1的相似性较高，也进一步验证了文献[11]中所提出的抽象规则的有效性。

4 实例分析

4.1 基于电力系统的模型抽象化简及相似性分析

随着社会经济的发展，人们对电能质量及可靠性的要求逐步提高。为了降低电网故障带来的影响，需要充分利用故障信息进行快速、准确的故障诊断。Petri网作为离散事件数学表示和行为分析的一种方法，在电力故障诊断领域发挥了巨大的作用。但是，针对目前电力系统结构相对复杂的情况，如果将其抽象为Petri网模型进行研究，能够大大简化模型推理的复杂程度。

接下来以典型的电网络拓扑结构图为例进行分析，将其转化为Petri网模型，如图5所示。

图5 电网络拓扑结构Petri网转化模型M3

在图5电网络系统中，库所si(i=1，2，…，13)主要是使电流传输后电器元件发生作用，如：发电机、刀开关、断路器以及继电保护元件等；变迁ti(i=1，2，…，24)在电网络系统中主要是使电流传输后电器元件发生作用，如：变压器动作、母线及输电线流能和用电器工作等。图5中变迁及库所的具体表示见表1。

表1 图5中的符号表示

表1(续)

运用已有的模型抽象规则[11]对图5进行抽象化简得图6。

图6 抽象模型M4

4.2 结果分析

本实例以电网络拓扑结构系统为例，将电网络拓扑结构转化为Petri网模型M3，并进一步计算其抽象模型M4，最后根据紧密度数值ρ(M4，M3)得出目标模型M4与源模型M3之间的相似性较高。对于大型的电网络系统，目标模型相较于源模型行为及结构都相对简单。当电网络系统出现故障时，在满足目标模型与源模型相似性较高的要求下，即目标模型最大程度地保留了源模型的结构及行为特征的前提下，选择目标模型作为研究对象，在简化了模型推理的复杂程度的同时提高了故障诊断的效率。

5 结语

本文提出了利用模型紧密度度量抽象模型与源模型相似性大小的方法。这种方法更适宜于模型抽象领域的相似性分析，不仅能够从新的角度度量模型相似性，而且能够验证模型抽象的有效性。

本文选取的模型大都结构简单，对于大型且复杂的抽象模型相似性比较在本文中未有体现，这也是本文的不足之处。未来将针对大型的具有代表性的Petri网模型进行相似性分析。