摘要
在考虑标注序列时,计算带有不可观测变迁的标注Petri网的最小初始标识集是一个复杂的任务。现有解决这一问题的方法存在多种限制。该文采用一种基于遗传算法的方法来估计最小初始标识。由于可能存在多个初始标识(通常是无限多个),关注点在于获得Petri网中的最小初始标识集,其中满足以下条件:初始标识允许至少一种触发序列与观察到的标注序列和网络结构一致;初始标识具有最小的托肯总数(即在所有库所上的托肯总数最小);对于每次观测到的标注,允许每个可观测变迁发生之前至多一个不可观测变迁发生。鉴于最小初始标识的估计属于NP-hard类别,因此采用此类算法是合理的。通过实验证明了该方法的有效性。与现有算法相比,该算法能够以更小的计算代价获得最小初始标识。
When considering label sequences,computing the minimal initial marking set of a labeled Petri net with unobservable transitions is a complex task.Existing methods to address this issue come with various limitations.We employ a genetic algorithm-based approach to estimate the minimal initial markings.Due to the potential existence of multiple initial markings(often infinite),the focus lies in obtaining a minimal initial marking set in the Petri net,satisfying the following conditions:the initial markings allow at least one firing sequence consistent with the observed label sequences and network structure;the initial markings have the minimum total token count(i.e.,the lowest sum of tokens over all places),and for each observed label,allowance is made for at most one unobservable transition firing before each observable transition firing.Given that estimating the minimal initial markings falls within the NP-hard category,the adoption of such algorithms is reasonable.We demonstrate the effectiveness of the proposed method through practical experiments.Compared with the existing algorithm,the proposed algorithm can obtain the minimum initial marking estimate with a lower computational cost.
作者
卞宏亚
BIAN Hong-ya(School of Computer Science and Technology,China University of Petroleum(East China),Qingdao 266580,China)
出处
《计算机技术与发展》
2024年第7期154-160,共7页
Computer Technology and Development
基金
山东省自然科学基金资助项目(ZR2020MF094)
国家自然科学基金资助项目(61402216)。
