使用SAT求解器产生所有极小冲突部件集

产生所有的极小冲突部件集为基于模型诊断中的一个重要步骤.本文将待诊断系统的行为模型及观测分别使用合取范式(CNF)形式的文件描述,从而提出将判定系统组件子集是否为冲突集的问题转化为:首先提取相关组件的CNF模型及观测,然后调用成熟的SAT求解器判定可满足性.随后,通过有效地结合CSISE-tree等方法来产生所有的极小冲突集.为进一步提高效率,给出了充分利用系统输入/输出结构信息的启发式策略.实验结果表明,使用结合SAT求解器及CSISE-tree等方法能够较快产生所有极小冲突集,并且启发式策略使得求解效率进一步提高(平均提高约21%,最高者甚至达到约48%).

基于模型的诊断中产生所有极小冲突集的新方法

首先提出一个基于SE-tree产生所有极小冲突集的方法(CSSE-tree)。然后给出翻转的SE-tree(ISE-tree)的概念,并提出基于ISE-tree产生所有极小冲突集的方法(CSISE-tree)。最后对提到的几种方法进行了比较分析,指出这几种方法都可用于候选产生阶段,即产生所有的极小冲突集的极小碰集,还可用于计算本原蕴涵/蕴涵式。

可用于诊断产生的计算碰集的新方法

提出一种利用与元素相关联的冲突集个数计算碰集的新方法,并结合带有终止节点的集合枚举树SE-tree形式化地表达计算过程,逐步生成所有的极小碰集.由于在SE-tree中添加了终止节点,因而能够较大提高搜索效率.实验结果表明,该算法程序容易编制,且效率较好,对于复杂的被诊断对象系统可以满足实时性.

动态系统基于模型诊断的研究进展与展望

基于模型诊断是为了克服传统故障诊断方法的缺点而兴起的一项新型的智能推理技术,其应用也越来越广泛。介绍了动态系统基于模型诊断的诊断过程,综述了建模诊断方法、时序基于模型诊断方法。通过与静态诊断的比较,指出动态系统基于模型诊断的各种定义及其研究意义,并指出有待解决的问题。

离散数学双语教学问题与对策

针对离散数学双语教学的实际,分析现存的一些常见问题,以浙江师范大学软件工程(中英合作)专业为例,阐述相应的改进策略及具体的实践方案。

离散事件系统基于模型诊断的研究进展

近年来,针对离散事件系统的基于模型诊断方法在大型通讯网络、电网故障诊断等领域获得了成功应用,成为人工智能与控制工程领域的热门研究课题。介绍了针对离散事件系统的基于模型诊断的基本思想与建模方法,从不同的角度对使用自动机建模的各种主要诊断方法进行了评析与比较;讨论了系统可诊断性判定方法的研究进展。从系统建模、分布式在线诊断、不完备模型下的诊断以及系统实现等方面,展望了针对离散事件系统的基于模型诊断领域中有待解决的问题。

数据结构全英文教学问题与对策探索

针对数据结构全英文教学,分析一些现存的常见问题,以浙江师范大学软件工程全英文专业为例,阐述相应的改进策略及可供参考的具体实践方案。

一种结合时间区间代数建模的主动系统的故障诊断方法

研究了在全局时钟、线性观测、串行事件触发的主动系统的故障诊断,在原有主动系统的自动机建模的基础上,引入时间区间代数表达更为详细的时间约束信息,构成带有时间的自动机对系统组件建模;同样在所得观测中也加入相应的更为详细的时间信息。由于加上了时间的约束,可使得诊断的解释空间进一步缩小,从而在一定情况下可提高诊断效率。最后讨论了非线性不确定观测或并发等一般情形下的处理方法。

基于因果关系的模型诊断

提出一种基于因果关系的思想求解所有极小诊断的新方法。此方法与Reiter的模型诊断方法有着本质的不同,不用求解冲突集及冲突集的碰集,一次直接求出所有的极小诊断,避免了由于调用ATMS时的组合爆炸引起的NP-完全问题。并根据因果关系的思想提出了极小诊断组成原理和极小诊断元件个数原理,可直接求出所有的极小诊断,避免了非极小诊断的产生,提高了诊断效率,并且不会丢失正确的解。该算法程序容易编制,且效率较好,可以满足复杂被诊断对象的实时性要求。

不完备离散事件系统的可诊断性

在离散事件系统的建模过程中,由于系统行为的复杂,存在物理系统向逻辑系统映射的不完全性,因此产生了不完备模型的概念.提出在模型不完备的前提下,判断模型可诊断性的方法.提出可诊断性的在线判定方法,同时将不完备的行为加入模型,使模型完备.用经典的双树方法判断离线可诊断性,根据观测序列的时序及语言的前缀判断并处理不完备行为.提出判定不完备行为的方法,向模型中添加不完备行为,并根据不完备行为增量地在双树中判定在线可诊断性.通过在线的可诊断性判定,当前系统能够得到在有限观测内唯一判定故障发生与否的结论.该方法适用于具有离散性质的系统.

基于故障行为的模型诊断方法

提出一种利用故障行为求解所有极小诊断的新方法,并结合带有终止节点的集合枚举树形式化地表达计算过程,逐步生成所有的极小诊断。该方法不用求解冲突集及冲突集的碰集,一次直接求出所有的极小诊断,避免了由于调用基于假设的真值维护系统时的组合爆炸而引起的NP-完全问题。在集合枚举树中添加了终止节点,从而避免了非极小诊断的产生,且不会因剪枝而丢失正确的解。实验结果表明,该算法程序容易编制,且效率较好,可以满足复杂的被诊断对象的实时性要求。

基于ACM-ICPC训练模式的数据结构实践教学探索

针对目前数据结构课程实践教学上的不足,提出基于ACM-ICPC训练模式的数据结构课程系统化的实践教学方案。

一种基于ATMS的求解所有极小冲突集的新方法

在Reiter算法的基础上,本文提出一种基于ATMS的求解所有极小冲突集的新方法。其中,对每个元件模型最多调用一次就可求出所有的极小冲突集,防止了ATMS的多次调用,因而能够提高效率。本文提出了极小依赖集的概念,并据此对ATMS求得的极小冲突集进行了分类;分析了算法的复杂度,并将新方法与相关工作进行了比较。该算法程序容易编制,而且效率高。

基于ATMS的冲突识别及诊断测量方法

依据General Diagnostic Engine(GDE)思想并基于Assumption-based Truth Mainte-nance System(ATMS)技术实现了一种产生所有极小冲突集的方法,并通过定义负节点和新的规则解决了ATMS在使用时完备性丢失的问题。在此基础上实现了基于粗略概率的简化熵诊断测量方法,并提出了基于动态ε策略的简化熵测量方法及测量后动态更新诊断结果的算法。该方法通过环境的传播进行增量的计算,具有正确性、完备性、一致性、极小化的特点,并减小了测量时产生的诊断代价,具有较强的通用性,易于实现和扩展。

一种高阶离散事件系统的诊断方法

为了保证诊断结果的正确性及唯一性,提出了高阶离散事件系统的可诊断性定义和可诊断性判定算法。在待诊断系统的诊断过程中,构建了可同时用于可诊断性判定的诊断机,对每个状态编译故障行为,所以不需在每次重构系统行为后遍历全部模型进行故障判断,并且在不影响诊断结果的前提下,根据约束条件对诊断机状态之间的转移进行限制,减少不必要节点的产生。

在离散事件系统中寻找诊断路径的方法

利用简单的编码理论提出一种在离散事件系统的故障诊断中快速找到诊断路径的方法.该方法通过状态编码,降低了在离散事件系统诊断同步过程中的时间复杂度,消减了诊断路径冗余.能够在给定的观测集合上快速提取诊断路径,更适合实际观测事件较少的系统.在模型完备假设下,除首次根据观测集合进行诊断需要指数级时间外,后续观测诊断时间降低到多项式级.实验验证了方法的有效性.

离散事件系统的同步诊断算法

针对传统系统建模方法需要假设模型完备的缺点,提出一种通过同步各部件模型的方法来解决不完备建模所导致的不完全诊断。对于离散事件系统的动态诊断进行优化,利用分布式的思想与Petri网的性质,使得各部件可以独立、并行地进行诊断,提高了诊断的速度。同时对提出的同步方法进行了可行性分析和简单实现,得到了较好的结果。

求极小碰集的遗传算法

采用改进的遗传算法求解极小碰集问题。在标准遗传算法的基础上,引入了精英策略以提高算法的搜索效率;在进化过程中加入了极小化操作,使得得到的结果都是极小碰集。同时通过实例,验证了极小化操作的有效性。最后,将此算法与其他求极小碰集的算法进行了比较。

用CHS-tree基于集合势的方法计算极小碰集

在基于模型的故障诊断理论中,为了根据所有冲突部件集计算全体极小碰集,提出基于集合势的方法,每次选择当前集合簇中势最小的集合进行扩展,并借助集合簇中元素出现的频率作为辅助判断,不断将大问题逐渐分解成子问题,然后依次求出不包含该扩展集合中各元素的集合簇的所有极小碰集。实验结果表明,CHStree方法生成树的过程较简单,能产生较少的节点,比经典的碰集树方法、二分法和集合枚举法等具有更高的求解效率。在某些情况下,其效率也高于当前效率最高的Boolean方法。

一种改进的基于结构抽象的分层模型诊断方法

基于分层模型诊断算法,提出一种改进的方法,对每层进行抽象时,根据分层表示和抽象条件,同时实现固定和动态两种抽象过程.该方法进一步解决了基于模型诊断计算复杂性的问题.在最终抽象层候选空间相同的前提下,减少了分层的层次数和诊断问题的个数;在一定条件下,第l(l>0)层的诊断可以不必细化到最底层,即可得到最终的诊断结果.实验结果表明,该算法在多数情况下比以往的分层模型诊断方法效率更高.