基于参数矩阵和增量策略求解极小碰集的算法研究

作     者：魏霞 

作者单位：烟台大学 

学位级别：硕士

导师姓名：赵相福

授予年度：2023年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：基于模型的诊断 极小碰集 极小冲突集 参数矩阵 极小势 增量策略 

摘      要：基于模型的诊断是人工智能领域中一个十分重要的研究分支,因其基于“深知识的新型智能化诊断推理技术,可以有效地克服传统专家系统诊断方法的局限性,从而在诸多领域有着广泛的应用。其中,根据冲突集合簇求解所有的极小碰集是基于模型诊断推理过程的一个关键步骤,极大地影响了整个故障诊断过程的最终效率。至今,不少国内外专家和学者仍在积极研究高效的极小碰集求解算法,力求在更短的时间内完成求解,以提高故障诊断的效率。此外,许多生产实际问题也可以转化为极小碰集问题进行求解,进而满足日益复杂的生产需求。本文通过深入研究极小碰集求解问题,结合问题特征加入相应的去超集策略,提出了一种效率较为优良的完备极小碰集求解算法;除此之外,针对增量算法在求解极小碰集过程中的不足,提出了一种效率更高的优化增量策略。具体有以下工作:(1)提出一种基于动态极小势的参数矩阵计算极小碰集的算法。本算法利用参数矩阵描述冲突集合簇中元素与集合的关系。在每一轮计算中,选取当前矩阵中势最小的集合进行分解,将大问题逐步分解成规模更小的子问题。在碰集求解过程中,通过加入剪枝策略和启发式信息,避免了对无解空间的搜索;在对每一个碰集进行极小化时,根据原始冲突集合簇的矩阵特性,可以快速找到特定元素所在的集合,从而提升极小化的速度。实验结果表明,本算法相较于其他经典的极小碰集求解算法具有更高的求解效率。(2)针对增量算法在求解过程中不仅需花费大量时间进行极小化,而且会产生过多冗余节点,造成严重的空间内存消耗问题,提出了一种新型的优化增量策略。在原有极小冲突集合簇与极小碰集簇的基础上,充分考虑了它们与新增冲突集中元素的关系。在原有极小冲突集簇中,首先通过启发式策略抽取部分集合进行极小化,从而大幅度缩短求解时间;然后通过优化的增量策略快速补全并更新解集,进而提高整体求解效率。为进一步提升算法的效率,提出按冲突集的势从小到大增量排序,利用新型优化的增量策略依次递归计算,并最终求得原始问题集合簇所有解集的全增量算法。理论及实验表明,该算法较其他极小碰集求解算法在求解时间上具有显著优势,可减少1至3个数量级的运行时间。以上两种方法分别从不同角度对现有的极小碰集完备求解算法进行了优化和改进,理论及实验表明所提出的两种方法具有较好的求解效果。前者从参数矩阵的结构特征出发,利用极小势将参数矩阵的问题规模大幅缩小,并利用矩阵的结构特征对碰集进行极小化处理;后者通过对解集簇和新增集合进行细化分类,减少子超集极小化过程的计算时间,而且通过利用集合的势依次进行增量计算,提高了求解效率。