基于参数矩阵计算全体极小碰集的方法

极小碰集计算是基于模型诊断的关键步骤之一.针对参数化求解方法的局限性,以及大型系统诊断中由于状态空间规模增加导致诊断能力下降甚至无法诊断等问题,研究了一种非参数化极小碰集求解算法M-MHS(Matrix-based Minimal Hitting Set)算法.该算法利用参数矩阵描述元素与集合的关系,通过矩阵分解将原始问题逐步分解为多个子问题,并采用有效的剪枝规则避免对无解子问题的计算.仿真结果表明:该算法能够计算全体极小碰集,且在进行较大规模碰集计算时性能优于HSSE(Hitting Set-Set Enumeration)算法和去参数化后的BNB-HSSE(Branch and Bound-HSSE)算法,并对不同规律数据能够维持性能稳定,从而为大型系统基于模型诊断提供了可行方法.

Parameter matrix-based approach to computing all minimal hitting sets

Computing all minimal hitting sets is one of the key steps in model-based diagnosis.Because of the limitations of parameterized algorithms and the low capabilities due to the expansion of state space in large-scale system diagnosis,a generalized minimal hitting-set algorithm named matrix-based minimal hitting set(M-MHS) algorithm was proposed.The parameter matrix was used to record the relationships between elements and sets,and the initial problem was broaken into several sub-problems by matrix decomposition.The computation of the sub-problems without solutions was avoided by the efficient prune rules.The simulation results show that all minimal hitting sets can be found.Compared with HSSE(hitting set-set enumeration) and de-parameterized BNB-HSSE(branch and bound-HSSE),the proposed algorithm has advantages in large scale computations and can keep relatively stable when data changes.The algorithm is a feasible means for computing all hitting sets in model-based diagnosis of large-scale systems.