论文部分内容阅读
基于模型的诊断(Model-Based Diagnosis)是人工智能领域重要的研究分支,这种诊断方式克服了传统诊断的问题,不需要借助专家的经验,不需要过多的人力消耗,诊断过程相对独立,诊断效率普遍较高,能够应对新兴工业中设备日渐复杂的现状。目前,基于模型的诊断方法已经广泛应用于机械、医疗、通讯、航天等各个领域。求解极小碰集是基于模型诊断过程中至关重要的步骤,其效率会对整个问题的求解时间产生极大的影响。另外,求解极小碰集的算法在众多理论和实际问题中有广泛应用。因此,国内外专家学者踊跃研究极小碰集问题,先后提出了多种求解极小碰集的算法。为了满足日益复杂的需求,还需要不断提出新算法,优化已知算法,提高求解效率。本文围绕求解极小碰集的问题展开研究,提出几种新的极小碰集求解算法,主要内容如下:(1)提出了基于矩阵运算求解极小碰集的算法。本算法将冲突集簇、候选解和碰集簇表示为不同的矩阵,通过矩阵的乘法运算揭示碰集的特性,从而找到候选解中的碰集。该算法在求解过程中不需要生成树形结构,只需进行简单的数学计算,数据结构较简单,求解过程较简便,具有较高的求解效率。(2)提出了基于范式转换求解极小碰集的算法。本算法将冲突集簇和极小碰集分别描述为合取范式和析取范式,通过合取范式转换为析取范式的过程求出所有极小碰集。该算法在运算过程中优先使用幂等律和吸收律进行约简,减少冗余项,提高了求解速度。同时,该算法是一种增量式算法,在新增冲突集时不需要重新计算,只需要在已知结果的基础上继续计算,为故障诊断提供了较为实用的算法。(3)提出了基于极小覆盖求解极小碰集的算法。本算法引入极小覆盖的概念,逐步求解,直到求出全体极小碰集。该算法只需要重复进行递归运算,数据结构稳定简单;在求解过程中不会产生超集,减少求解规模提高求解效率;直接得到极小碰集,不需要对得到结果进行去超集的运算,减少了求解时间。(4)提出了基于属性矩阵求解极小碰集的算法。本算法用冲突集矩阵代替冲突集簇,利用队列结构分步求解极小碰集。该算法在每次队列运算后会进行约简,减少后续运算规模,提高运算效率,而且算法的空间复杂度较低,不会占用过多内存。综上所述,本文针对基于模型诊断过程中求解极小碰集的问题,探索了多种求解的新方法,为求解极小碰集提供新的思路。