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

王冬; 冯文全; 李景文; 赵琦

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

北京航空航天大学电子信息工程学院, 北京 100191

详细信息

中图分类号: TP306
计量
- 文章访问数: 1605
- HTML全文浏览量: 85
- PDF下载量: 631
- 被引次数: 0
出版历程
- 收稿日期: 2011-09-20
- 网络出版日期: 2012-09-30

Parameter matrix-based approach to computing all minimal hitting sets

School of Electronics and Information Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100191, China

摘要

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

HTML全文

参考文献(14)

[1]	de Kleer J,Williams B C.Diagnosing multiple faults[J].Artificial Intelligence,1987,32(1):97-130
[2]	Williams B C,Ragno R J.Conflict-directed A^* and its role in model-based embedded systems[J].Discrete Applied Mathematics,2007,155(12):1562-1595
[3]	李绍华,王建新,冯启龙,等.Set Cover 和 Hitting Set 问题的研究进展[J].计算机科学,2009,36(10):1-4 Li Shaohua,Wang Jianxin,Feng Qilong,et al.Set cover and hitting set:a survey[J].Computer Science,2009,36(10):1-4 (in Chinese)
[4]	蔡烜.d-Hitting Set问题的固定参数化算法. 上海:上海交通大学计算机科学与工程系,2009 Cai Xuan.Fixed-parameter algorithms for d-Hitting set problems. Shanghai:Department of Computer Science and Engineering,Shanghai Jiao Tong University,2009(in Chinese)
[5]	Reiter R.A theory of diagnosis from first principles[J].Artificial Intelligence,1987,32(1):57-95
[6]	Wotawa F.A variant of Reiter-s hitting-set algorithm[J].Information Processing Letters,2001,79(1):45-51
[7]	Greiner R,Smith B A,Wilkerson R W.A correction to the algorithm in Reiter-s theory of diagnosis[J].Artificial Intelligence,1989,41(1):79-88
[8]	姜云飞,林笠.用对分HS—树计算最小碰集[J].软件学报,2002,13(12):2267-2274 Jiang Yunfei,Lin Li.Computing the minimal hitting sets with binary HS-tree[J].Journal of Software,2002,13(12):2267-2274(in Chinese)
[9]	姜云飞,林笠.用布尔代数方法计算最小碰集[J].计算机学报,2003,26(8):919-924 Jiang Yunfei,Lin Li.The computing of hitting sets with boolean formulas[J].Chinese Journal of Computers,2003,26(8):919-924(in Chinese)
[10]	黄杰,陈琳,邹鹏.一种求解极小诊断的遗传模拟退火算法[J].软件学报,2004,15(9):1345-1350 Huang Jie,Chen Lin,Zou Peng.A compounded genetic and simulated annealing algorithm for computing minimal diagnosis[J].Journal of Software,2004,15(9):1345-1350(in Chinese)
[11]	Zhao Xiangfu,Ouyang Dantong.A method of combining SE-tree to compute all minimal hitting sets [J].Progress in Natural Science,2006,16(2):169-174
[12]	陈晓梅,孟晓风,乔仁晓.基于BNB-HSSE计算全体碰集的方法[J].仪器仪表学报,2010,31(1):61-67 Chen Xiaomei,Meng Xiaofeng,Qiao Renxiao.Method of computing all minimal hitting set based on BNB-HSSE[J].Chinese Journal of Scientific Instrument,2010,31(1):61-67(in Chinese)
[13]	林笠.基于模型诊断中用逻辑数组计算最小碰集[J].暨南大学学报:自然科学与医学版,2002,23(1):24-27 Lin Li.Computing minimal hitting sets with logic array in model-based diagnosis[J].Journal of Jinan University:Natural Science & Medicine Edition,2002,23(1):24-27(in Chinese)
[14]	Fijany A,Vatan F.New approaches for efficient solution of hitting set problem//Proceedings of the Winter International Symposium on Information and Communication Technologies.Cancun,Mexico:Trinity College Dublin,2004