基于逆向搜索的模糊Petri网分层算法

向寅鸿，周恺卿，杨森宇，张轩宇，康棣文

基于逆向搜索的模糊Petri网分层算法

向寅鸿，周恺卿*，杨森宇，张轩宇，康棣文

（吉首大学 通信与电子工程学院，湖南 吉首 416000）（∗通信作者电子邮箱kqzhou@jsu.edu.cn）

模糊Petri网（FPN）是知识库系统（KBS）表示、建模与分析的主要工具之一。针对部分FPN层次结构不清晰、库所/变迁间从属关系不明确的问题，提出一种基于逆向搜索的FPN分层算法（HFPN-RS）以实现非层次化FPN到层次化FPN（HFPN）的自动转换。首先，从终结库所开始对整个FPN进行逆向搜索，将所有输入库所的前集、输出库所的后集分别划分在同一层；其次，通过添加虚库所-虚变迁对的方式明确整个模型的层次结构；同时提出两条相关定理以明确HFPN分层层数的下确界和层次化操作中需要添加的最少虚库所-虚变迁对数，并给出经层次化操作后具有完整分层结构的FPN模型关联矩阵维度计算公式。在实验部分，通过对几类各具特点的FPN模型进行层次化操作，并利用所提定理进行验证。实验结果表明，添加虚库所-虚变迁对后新FPN模型具有清晰的层次结构，为下一步FPN泛化能力等研究内容的深入提供了理论基础。

模糊Petri网；层次化；逆向搜索；虚库所-虚变迁对；关联矩阵

0 引言

模糊Petri网（Fuzzy Petri Net， FPN）是一类向后拓展的高级Petri网（Petri Net， PN）拓扑结构，它在继承PN描述异步并发和图形表示能力的基础上，还具有对知识库系统（Knowledge Based System， KBS）或专家系统（Expert System， ES）建模与执行模糊推理的能力［1-3］。目前，FPN被广泛应用于生物系统［4-5］、能源系统［6-7］、制造业系统［8-9］和交通控制系统［10-11］等领域，但FPN仍存在部分参数难以精确获得、泛化能力弱等不足［1］。针对这一问题，围绕FPN自适应能力的泛化展开了一系列研究：文献［12-13］中结合FPN与神经网络，系统地研究了一类动态自适应FPN（Adaptive FPN， AFPN），并应用于表示动态知识，使得FPN模型初步具备了自适应能力；文献［14］中将改进的遗传粒子群算法应用于模糊知识动态表示（Dynamic Representation of Fuzzy Knowledge， DRFK）模型，一定程度上增强了FPN自学习能力；文献［15］中提出一种结合直觉模糊抑制弧PN（Intuitionistic Fuzzy Inhibitor Arc PN， IFIAPN）和误差反向传播算法的电网故障诊断方法，利用BP（Back Propagation）神经网络算法训练模型的权重参数，提高推理精度；文献［16］中提出了一种加权模糊神经PN（Weighted Fuzzy Neural PN，WFNPN），并应用于微电网的故障诊断，缓解了FPN对人工经验的过度依赖，提高了泛化能力；文献［17］中提出了一种基于PN、模糊理论和神经网络算法的神经FPN（Neural FPN， NFPN），并应用于电机故障诊断；文献［18］中设计了一种递归小波Petri模糊神经网络（Recurrent Wavelet Petri Fuzzy Neural Network， RWPFNN）控制器，用于快速响应控制电网事故，减小故障对电网的影响。

由上述文献可知，将FPN神经网络化后，采用相应优化算法优化参数，提高FPN的自适应能力，以提高推理精度是FPN的研究热点之一。作为一类有向二分图，FPN可将库所分为输入库所集、中间库所集和输出库所集这3类，该结构天然对应神经网络固有的输入层、隐藏层、输出层这3层结构［19］。FPN的这一结构特点为FPN模型神经网络结构化提供了可能，为充分利用神经网络的相关成果拓展FPN的应用领域奠定了基础。

与神经网络模型相比，FPN中的库所/变迁存在嵌套使用情况，使FPN结构层次不清晰、库所/变迁间从属关系不明确，导致FPN的类神经网络层次化操作难以自动实现；因此如果将神经网络的相关研究成果充分运用于FPN模型，则需要对FPN模型进行层次划分，从而明确库所/变迁间的从属关系。文献［20］中提出的分层算法对部分情形考虑欠缺，如具有多输入/多输出库所结构的FPN模型，无法得到清晰的层次结构等。为解决这一问题，本文针对无环结构的FPN模型提出了一种基于逆向搜索的FPN分层算法（Hierarchical algorithm of FPN by Reverse Search， HFPN-RS）。本文算法首先从终结库所开始对整个FPN逆向搜索，利用前后集、可达集和直接可达集等概念，将所有输入库所的后集、输出库所的前集分别划分在同一层；其次通过添加虚库所-虚变迁对明确整个模型的层次结构；同时，本文提出相关定理明确了层次化FPN（Hierarchical FPN， HFPN）的分层层数的下确界和层次化操作中需添加的最少虚库所-虚变迁对数，并给出了经层次化操作后具有完整分层结构的FPN模型关联矩阵维度计算公式；最后，对提出的分层算法编程实现，通过相关案例，分别从实验结果和理论验证两方面验证HFPN-RS的正确性和鲁棒性。

1 FPN及相关定义

本章介绍HFPN-RS涉及的相关概念［13，21-23］。

定义1 FPN。

定义2 前集、后集。

定义3 输入库所、输出库所、中间库所、输入库所集、中间库所集和输出库所集。

定义4 虚变迁、虚库所。

图1　库所和变迁、虚库所和虚变迁

在分层过程中，虚库所和虚变迁仅起中间过渡作用，除了增加模型的规模，对模型的知识表示和推理没有造成其他影响。

定义5 直接可达集、可达集。

定义6 关联矩阵。

定义7 路径、最长路径。

2 HFPN‑RS

若FPN具有清晰的层次结构，需要满足以下两个条件：1）输入库所集的后集集合、输出库所集的前集集合分别划分在同一层；2）除第一层和最后一层，其他每层变迁集合的后集等于下一层的前集，变迁集合的前集等于上一层的后集。因此，HFPN-RS的核心思想判断当前库所或变迁集合及其对应的后集集合是否在同一层，若不在同一层则通过添加虚库所-虚变迁对调整层次结构。具体地，HFPN-RS通过添加虚库所-虚变迁对实现层次划分，可以分为以下3个步骤：

1）首先判断当前变迁是否有额外的输出，若存在，则在该变迁及其后集库所间添加虚库所-虚变迁对。

2）其次判断当前库所是否有额外的输出，若存在，则在该库所及其后集变迁间添加虚库所-虚变迁对。

3）最后判断当前层的前集是否等于输入库所集，若不相等，则需要在对应的输入库所及其后集变迁间添加虚库所-虚变迁对。

2.1　HFPN-RS的步骤

结合上述算法设计思想，HFPN-RS的详细步骤如算法1所示。

算法1 HFPN-RS。

输入 库所集、变迁集、输入矩阵和输出矩阵。

2.2　本文相关定理

在HFPN-RS的基础上，给出两个相关定理以确定FPN分层层数的下确界和最少需要添加的虚库所-虚变迁对数。

由上述分析可知，无论给定的FPN层次是否明确，经层次化操作后均可得到一个含有层的层次化明晰的FPN模型，即是一个确界。

综上所述，为保证任意给定FPN满足层次化要求的最小分层层数，即FPN模型分层层数的下确界等于最长路径长度。 证毕。

定义8 覆盖路径。

在求解最少添加的虚库所-虚变迁对数时，通过计算当前路径的覆盖路径在该路径上添加的虚库所-虚变迁对数避免重复计算需添加的虚库所-虚变迁对，以保证整个FPN模型需添加的虚库所-虚变迁对数最少。

2.3　HFPN-RS时间复杂度分析

3 实验与结果分析

通过Java语言编程实现HFPN-RS，并通过4个实验案例验证本文算法的有效性。由于虚库所和虚变迁只起中间过渡作用，且相应的权值、阈值和确信度都已确定，因此本文实验只验证FPN模型的结构，未涉及其他FPN相关参数。实验环境为Windows 11操作系统，JDK 1.8。编程语言为Java。

由第2章可知，若FPN模型具有清晰的层次结构，需要满足以下两个条件：

1）输入库所集的后集集合、输出库所集的前集集合分别划分在同一层。

2）除第一层和最后一层外，其他每层变迁集合的后集等于下一层的前集，变迁集合的前集等于上一层的后集。

基于这两点设计如下实验：首先根据待分层的FPN模型得到它对应的输入矩阵、输出矩阵，并利用定理1、2预估新FPN模型的规模；其次将输入矩阵、输出矩阵作为HFPN-RS的输入，运行分层算法（算法1）验证定理，并输出每一层的变迁集合、新FPN模型的关联矩阵和矩阵的维度；最后根据关联矩阵得到图形化FPN，直观展示新FPN清晰的层次结构。

从以下4种不同角度分别验证HFPN-RS的正确性和鲁棒性：

1）单输入库所FPN模型。

2）FPN模型库所/变迁层次关系已经明确。

3）多输入/输出库所，且输入库所、输出库所层次从属关系不同。

4）中间库所集、变迁的层次结构不明确，存在嵌套使用。

案例详细实验如下：

案例1 单输入库所FPN模型。待分层的FPN图2所示。

图2　案例1的FPN模型

新生成的FPN如图3所示。

图3　案例1层次化后的FPN模型

案例1得到的分层结果与文献［20］中FPN的结构相同，都建立了清晰的层次结构，说明HFPN-RS同样适用于模糊推理算法中连续函数的建立。

案例2 FPN模型库所/变迁层次关系已经明确。待分层的FPN如图4所示。

图4　案例2的FPN模型

案例3 多输入/输出库所，且输入库所、输出库所层次从属关系不同。待分层的FPN如图5所示。

新的FPN如图6所示。

图6　案例3层次化后的FPN模型

案例4 中间库所集、变迁的层次结构不明确，存在嵌套使用。待分层的FPN如图7所示。

新的FPN如图8所示。

图8　案例4层次化后的FPN模型

上述4种不同角度（单输入库所FPN模型；FPN模型库所/变迁层次关系已经明确；多输入/输出库所，且输入库所、输出库所层次从属关系不同；中间库所集、变迁的层次结构不明确，存在嵌套使用）的实验案例都通过运行HFPN-RS得到了结构清晰、规模最小的HFPN，充分体现了HFPN-RS的正确性与鲁棒性。同时，针对任意给定的FPN模型，由定理1、2预测得到HFPN的最小分层层数和添加虚库所-虚变迁对的个数与实验得到的完全一致，验证了定理1、2的正确性。

4 结语

针对部分FPN不具有清晰的层次结构、库所/变迁间从属关系不明确的问题，本文提出了HFPN-RS以实现将非层次化FPN到HFPN的自动转换。该算法从终结库所出发，对整个FPN进行逆向搜索，将所有输入库所的后集、输出库所的前集分别划分在同一层，再通过添加虚库所-虚变迁对的方式最终使整个模型建立明确的层次结构。同时，相关定理的提出和证明从理论上明确了层次化FPN分层层数的下确界以及保证在得到的HFPN模型中添加的虚库所-虚变迁数最少。在实验部分，通过对几类各具特点的FPN模型进行层次化操作，并利用所提定理进行验证。下一步，将基于HFPN-RS深入研究提高FPN泛化能力的方法。

[1] ZHOU K-Q， ZAIN A M. Fuzzy Petri nets and industrial applications： a review［J］. Artificial Intelligence Review， 2015， 45（4）：405-446.

[2] JIANG W， ZHOU K-Q， SARKHEYLI-HÄGELE A， et al. Modeling， reasoning， and application of fuzzy Petri net model： a survey［J］. Artificial Intelligence Review， 2022， 55（8）： 6567-6605.

[3] LIU H-C， YOU J-X， LI Z， et al. Fuzzy Petri nets for knowledge representation and reasoning： a literature review［J］. Engineering Applications of Artificial Intelligence， 2017， 60：45-56.

[4] LIU F， SUN W， HEINER M， et al. Hybrid modelling of biological systems using fuzzy continuous Petri nets［J］. Briefings in Bioinformatics， 2021， 22（1）：438-450.

[5] HAMED R I. Quantitative modeling of gene networks of biological systems using fuzzy Petri nets and fuzzy sets［J］. Journal of King Saud University — Science， 2018， 30（1）：112-119.

[6] YUAN C， LIAO Y， KONG L， et al. Fault diagnosis method of distribution network based on time sequence hierarchical fuzzy Petri nets ［J］. Electric Power Systems Research， 2021， 191：106870.

[7] 刘敦楠，张潜，李霄彤，等. 基于云模型与模糊Petri网的电力市场潜在危害行为识别［J］. 电力系统自动化， 2019， 43（2）：25-33.（LIU D N， ZHANG Q， LI X T， et al. Identification of potential harmful behaviors in electricity market based on cloud model and fuzzy Petri net［J］. Automation of Electric Power Systems， 2019， 43（2）：25-33.）

[8] 胡涛，马晨辉，周晓柳婷，等. 航天复杂系统的加权模糊Petri网故障诊断建模［J］. 计算机集成制造系统， 2019， 25（10）：2580-2586.（HU T， MA C H， ZHOU X L T， et al. Fault diagnosis method for complex aerospace systems based on weighted fuzzy Petri net［J］. Computer Integrated Manufacturing Systems， 2019， 25（10）：2580-2586.）

[9] WU Z， HSIEH S-J. A realtime fuzzy Petri net diagnoser for detecting progressive faults in PLC based discrete manufacturing system［J］. The International Journal of Advanced Manufacturing Technology， 2011， 61： 405-421.

[10] CHENG Y-H， YANG L-A. A fuzzy Petri nets approach for railway traffic control in case of abnormality： evidence from Taiwan railway system［J］. Expert Systems with Applications， 2009， 36（4）：8040-8048.

[11] 戴晨曦，刘志刚，胡轲珽，等. 基于模型与模糊Petri网融合的高铁牵引变压器故障诊断［J］. 电力系统保护与控制， 2016， 44（11）：26-32.（DAI C X， LIU Z G， HU K T， et al. Fault diagnosis for traction transformer of high speed railway on the integration of model-based diagnosis and fuzzy Petri nets［J］. Power System Protection and Control， 2016， 44（11）： 26-32.）

[12] LI X， LARA-ROSANO F. Adaptive fuzzy Petri nets for dynamic knowledge representation and inference［J］. Expert Systems with Applications， 2000， 19（3）：235-241.

[13] LI X， YU W， LARA-ROSANO F. Dynamic knowledge inference and learning under adaptive fuzzy Petri net framework［J］. IEEE Transactions on Systems， Man and Cybernetics， Part C （Applications and Reviews）， 2000， 30（4）：442-450.

[14] WANG W-M， PENG X， ZHU G-N， et al. Dynamic representation of fuzzy knowledge based on fuzzy Petri net and genetic-particle swarm optimization［J］. Expert Systems with Applications， 2014， 41（4）：1369-1376.

[15] TAN M， LI J， XU G， et al. A novel intuitionistic fuzzy inhibitor arc Petri net with error back propagation algorithm and application in fault diagnosis ［J］. IEEE Access， 2019， 7：115978-115988.

[16] JIANG T， DU C， GUO S， et al. Microgrid fault diagnosis model based on weighted fuzzy neural Petri net ［C］// Proceedings of the 2020 IEEE 4th Information Technology， Networking， Electronic and Automation Control Conference. Piscataway： IEEE， 2020： 2361-2365.

[17] WANG C， LI J， ZHU X， et al. Adaptive neural fuzzy Petri net algorithm for motor fault diagnosis［J］. IOP Conference Series： Earth and Environmental Science， 2020， 446：042063.

[18] LIN F-J， LIAO J-C， CHEN C-I， et al. Voltage restoration control for microgrid with recurrent wavelet Petri fuzzy neural network［J］. IEEE Access， 2022， 10：12510-12529.

[19] ZHOU K-Q， MO L-P， JIN J， et al. An equivalent generating algorithm to model fuzzy Petri net for knowledge-based system ［J］. Journal of Intelligent Manufacturing， 2019， 30： 1831-1842.

[20] 鲍培明. 基于BP网络的模糊Petri网的学习能力［J］. 计算机学报， 2004， 27（5）：695-702.（BAO P M. Learning capability in fuzzy Petri nets based on BP net ［J］. Chinese Journal of Computers， 2004， 27（5）： 695-702.）

[21] ZHOU K-Q， ZAIN A M， MO L-P. Dynamic properties of fuzzy Petri net model and related analysis ［J］. Journal of Central South University， 2015， 22：4717-4723.

[22] 孙晓玲. 直觉模糊Petri网的双向模糊故障推理算法［J］. 计算机科学与探索， 2017， 11（6）：1006-1013.（SUN X L. Bidirectional fuzzy fault reasoning algorithm of intuitionistic fuzzy Petri net［J］. Journal of Frontiers of Computer Science and Technology， 2017， 11（6）： 1006-1013.）

[23] 莫礼平，乐晓波，周恺卿，等.带抑制弧Petri网的保性变换［J］.计算机应用， 2012，32（11）：3071-3074.（MO L P， YUE X B， ZHOU K Q， et al. Property preserving operation for simplifying Petri nets with inhibitor arcs ［J］. Journal of Computer Applications， 2012，32（11）：3071-3074.）

Hierarchical algorithm of fuzzy Petri net by reverse search

XIANG Yinhong， ZHOU Kaiqing*， YANG Senyu， ZHANG Xuanyu， KANG Diwen

（，，416000，）

Fuzzy Petri Net （FPN） is one of the main tools to represent， model， and analyze the Knowledge-Based System （KBS）. For clear hierarchical structures and uncertain affiliations between places/transactions in some FPNs， a Hierarchical algorithm of FPN by Reverse Search （HFPN-RS） was proposed to realize the automatic conversion from a non-hierarchical FPN to a Hierarchical FPN （HFPN）. Firstly， a reverse search of the entire FPN was launched starting from the output place（s） at first. The front set of input place（s） and the back set of output place（s） were divided into the same layer. Then， the hierarchical structure of the entire FPN was clarified by adding virtual place-virtual transition pairs. Meanwhile， two theorems were proven to define the infimum of the number of hierarchical layers of FPN and the minimum number of virtual place-virtual transition pair（s） that need to be added in the hierarchical operation， respectively. Moreover， the dimension calculation formula of the incidence matrix of the complete hierarchical structure was also introduced. In the experimental part， hierarchical operation was performed on several types of FPN models with different characteristics and the proposed theorems were used to verify the HFPN-RS algorithm. The experimental results show that the new FPN has a clear hierarchical structure by adding the virtual place-virtual transition pair（s）. It provides a theoretical base to further study the FPN generalization ability.

Fuzzy Petri Net (FPN); hierarchy; reverse search; virtual place-virtual transition pair; incidence matrix

This work is partially supported by National Natural Science Foundation of China （62066016）， Scientific Research Project of Education Department of Hunan Province （22B0549，22C0282）， Science Program Project of Xiangxi Prefecture （Prefecture Financial Education Index ［2022］ No.5）， Postgraduate Scientific Research Innovation Project of Hunan Province （CX20231088）.

XIANG Yinhong， born in 1998， M. S. candidate. His research interests include fuzzy Petri net， clinical assistant decision-making system.

ZHOU Kaiqing， born in 1984， Ph. D.， associate professor. His research interests include fuzzy Petri net， clinical assistant diagnosis system， swarm intelligence algorithm.

YANG Senyu， born in 1999， M. S. candidate. His research interests include clinical assistant diagnosis system， swarm intelligence algorithm.

ZHANG Xuanyu， born in 1997， M. S. candidate. His research interests include fuzzy Petri net， clinical assistant diagnosis system.

KANG Diwen， born in 1997， M. S.， assistant experimentist. His research interests include fuzzy Petri net， clinical assistant diagnosis system， swarm intelligence algorithm.

TP301

A

1001-9081（2023）12-3676-07

10.11772/j.issn.1001-9081.2022121851

2022⁃12⁃15；

2023⁃02⁃15；

2023⁃02⁃20。

国家自然科学基金资助项目（62066016）；湖南省教育厅科学研究项目（22B0549， 22C0282）；湘西州科学计划项目（州财教指［2022］5号）；湖南省研究生科研创新项目（CX20231088）。

向寅鸿（1998—），男，湖南常德人，硕士研究生，CCF会员，主要研究方向：模糊Petri网、临床辅助决策系统；周恺卿（1984—），男，湖南长沙人，副教授，博士，CCF会员，主要研究方向：模糊Petri网、临床辅助诊断系统、群智能算法；杨森宇（1999—），男，湖南吉首人，硕士研究生，主要研究方向：临床辅助诊断系统、群智能算法；张轩宇（1997—），男，湖南长沙人，硕士研究生，CCF会员，主要研究方向：模糊Petri网、临床辅助决策系统；康棣文（1997—），男，湖南长沙人，助理实验师，硕士，CCF会员，主要研究方向：模糊Petri网、临床辅助诊断系统、群智能算法。