-
题名基于遗传算法的最小初始标识估计
- 1
-
-
作者
卞宏亚
-
机构
中国石油大学(华东)计算机科学与技术学院
-
出处
《计算机技术与发展》
2024年第7期154-160,共7页
-
基金
山东省自然科学基金资助项目(ZR2020MF094)
国家自然科学基金资助项目(61402216)。
-
文摘
在考虑标注序列时,计算带有不可观测变迁的标注Petri网的最小初始标识集是一个复杂的任务。现有解决这一问题的方法存在多种限制。该文采用一种基于遗传算法的方法来估计最小初始标识。由于可能存在多个初始标识(通常是无限多个),关注点在于获得Petri网中的最小初始标识集,其中满足以下条件:初始标识允许至少一种触发序列与观察到的标注序列和网络结构一致;初始标识具有最小的托肯总数(即在所有库所上的托肯总数最小);对于每次观测到的标注,允许每个可观测变迁发生之前至多一个不可观测变迁发生。鉴于最小初始标识的估计属于NP-hard类别,因此采用此类算法是合理的。通过实验证明了该方法的有效性。与现有算法相比,该算法能够以更小的计算代价获得最小初始标识。
-
关键词
离散事件系统
PETRI网
初始标识估计
不可观测变迁
变迁触发序列
-
Keywords
discrete event systems
Petri nets
initial marking estimates
unobservable transition
transition firing sequence
-
分类号
TP301.1
[自动化与计算机技术—计算机系统结构]
-
-
题名标注Petri网中的最小初始标识估计
被引量：2
- 2
-
-
作者
徐淑琳
周广瑞
岳昊
-
机构
青岛大学自动化学院
青岛大学复杂性科学研究所
-
出处
《计算机工程》
CAS
CSCD
北大核心
2021年第4期285-290,297,共7页
-
基金
国家自然科学基金(61402216,61673228)。
-
文摘
为获得制造系统初始化时的最小资源以实现最优资源分配,利用标注Petri网对系统进行建模,并研究标注Petri网的最小初始标识估计问题。给定一个标注Petri网,在不可观测变迁组成无环子网的情况下,基于动态规划提出一种新的最小初始标识估计算法。在观察到给定的标注序列后,放宽不可观测变迁发生个数的限制,并根据该算法构建节点的演化过程。当出现相同的发生数向量时,仅保留当前极小的初始标识估计,并通过节点的演化过程对极小初始标识估计的托肯总数进行对比。为验证算法的有效性,给出一个制造系统的标注Petri网模型实例,最终得到的最小初始标识为[1000]~T,且对应的变迁发生序列为t_1t_3t_4t_6,满足给定标注Petri网的结构要求。实验结果表明,与传统基于动态规划的算法相比,该算法获得的最小初始标识估计具有更小的托肯总数。
-
关键词
离散事件系统
初始标识估计
PETRI网
不可观测变迁
动态规划
-
Keywords
discrete event systems
estimation of initial marking
Petri nets
unobservable transitions
dynamic programming
-
分类号
TP393
[自动化与计算机技术—计算机应用技术]
-
