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

Hierarchical algorithm of fuzzy Petri net by reverse search

作　　者：向寅鸿 周恺卿 杨森宇 张轩宇 康棣文 XIANG Yinhong;ZHOU Kaiqing;YANG Senyu;ZHANG Xuanyu;KANG Diwen(School of Communication and Electronic Engineering,Jishou University,Jishou Hunan 416000,China)

机构地区：[1]吉首大学通信与电子工程学院,湖南吉首416000

出　　处：《计算机应用》2023年第12期3676-3682,共7页journal of Computer Applications

基　　金：国家自然科学基金资助项目(62066016);湖南省教育厅科学研究项目(22B0549,22C0282);湘西州科学计划项目(州财教指[2022]5号);湖南省研究生科研创新项目(CX20231088)。

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

关 键 词：模糊PETRI网 层次化 逆向搜索 虚库所-虚变迁对 关联矩阵 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]