基于遗传算法的最小初始标识估计

来源：计算机技术与发展杂志2024年第07期北京时间：

作者：卞宏亚

摘要：在考虑标注序列时,计算带有不可观测变迁的标注 Petri 网的最小初始标识集是一个复杂的任务。 现有解决这一问题的方法存在多种限制。 该文采用一种基于遗传算法的方法来估计最小初始标识。 由于可能存在多个初始标识(通常是无限多个),关注点在于获得 Petri 网中的最小初始标识集,其中满足以下条件:初始标识允许至少一种触发序列与观察到的标注序列和网络结构一致;初始标识具有最小的托肯总数(即在所有库所上的托肯总数最小);对于每次观测到的标注,允许每个可观测变迁发生之前至多一个不可观测变迁发生。 鉴于最小初始标识的估计属于 NP-hard 类别,因此采用此类算法是合理的。 通过实验证明了该方法的有效性。 与现有算法相比,该算法能够以更小的计算代价获得最小初始标识。

关键词：离散事件系统;Petri网;初始标识估计;不可观测变迁;变迁触发序列