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

Hierarchical algorithm of fuzzy Petri net by reverse search

模糊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.