极小碰集求解算法的性能分析与比较
|
摘要
基于模型的诊断为人工智能领域中一个重要的研究分支,极小碰集即候选诊断的求解过程极大影响最终的诊断效率.本文关注当前主要的极小碰集求解算法,简要介绍了它们的基本思想,从算法描述和实例比较了它们的异同和复杂性,并设计实现了一个统一的实验平台,测试并比较了它们的实际执行效率,为实际选择合适的算法提供了重要参考依据.
Model-based diagnosis is an important branch of research in the field of artificial intelligence.The efficiency for generating all minimal hitting sets,i.e.,candidate diagnoses,considerably affects the final diagnostic process.This paper focuses on the current major algorithms for computing minimal hitting sets.First,the basic ideas of algorithms were briefly introduced.Then,the similarities and differences,and complexity of them were compared by simple algorithm description and examples.An integrated experimental platform was implemented for testing and comparing their time efficiency,which provides an important reference for the actual selection of an appropriate algorithm in practice.
Model-based diagnosis is an important branch of research in the field of artificial intelligence.The efficiency for generating all minimal hitting sets,i.e.,candidate diagnoses,considerably affects the final diagnostic process.This paper focuses on the current major algorithms for computing minimal hitting sets.First,the basic ideas of algorithms were briefly introduced.Then,the similarities and differences,and complexity of them were compared by simple algorithm description and examples.An integrated experimental platform was implemented for testing and comparing their time efficiency,which provides an important reference for the actual selection of an appropriate algorithm in practice.
引文
[1] Zhao X,Ouyang D,Zhang L.Computing all minimal hitting sets by subset recombination[J].Applied Intelligence,2018,48(2):257-270.
[2] Zhao X,Ouyang D.Deriving all minimal hitting sets based on join relation[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems,2015,45(7):1063-1076.
[3] 赵相福,欧阳丹彤.使用SAT求解器产生所有极小冲突部件集[J].电子学报,2009,37(4):804-810.ZHAO Xiang-fu,OUYANG Dan-tong.Deriving all minimal conflict sets using satisfiability algorithms[J].Acta Electronica Sinica,2009,37(4):804-810.(in Chinese)
[4] 欧阳丹彤,刘伯文,周建华,张立明.结合问题特征利用SE-Tree反向深度求解冲突集的方法[J].电子学报,2017,45(5):1175-1181.OUYANG Dan-tong,LIU Bo-wen,ZHOU Jian-hua,ZHANG Li-ming.A method ofcomputing minimal conflict sets combining the structure property with the anti-depth SE-tree[J].Acta Electronica Sinica,2017,45(5):1175-1181.(in Chinese)
[5] 刘梦,欧阳丹彤,刘伯文,张立明,张永刚.结合问题特征的分组式诊断方法[J].电子学报,2018,46(3):589-594.LIU Meng,OUYANG Dan-tong,LIU Bo-wen,ZHANG Li-ming,ZHANG Yong-gang.Grouped diagnosis approach using the feature of problem[J].Acta Electronica Sinica,2018,46(3):589-594.(in Chinese)
[6] Reiter R.A theory of diagnosis from first principles[J].Artificial Intelligence,1987,32(1):57-95.
[7] Wotawa F.A variant of Reiter’s hitting-set algorithm[J].Information Processing Letters,2001,(79):45-51.
[8] 王肖,赵相福.用CHS-tree基于集合势的方法计算极小碰集[J].计算机集成制造系统,2014,20(2):401-406.Wang Xiao,Zhao Xiangfu.Computing minimal hitting sets with CHS-tree method[J].Computer Integrated Manufacturing Systems.2014,20(2):401-406.(in Chinese)
[9] 姜云飞,林笠.用对分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)
[10] 姜云飞,林笠.用布尔代数方法计算最小碰集[J].计算机学报,2003,26(8):919-924.Jiang Yunfei,Lin Li.The computation of hitting sets with Boolean formulas[J].Chinese Journal of Computers,2003,26(8):919-924.(in Chinese)
[11] Zhao X F,Ouyang D T.A method of combining SE-tree to compute all minimal hitting sets[J].Progress in Natural Science,2006,16(2):169-174.
[12] Han,B,Lee,S J.Deriving minimal conflict sets by CS-trees with mark set in diagnosis from first principles[J].IEEE Transactions on Systems,Man,and Cybernetics,1999,29(2):281-286.
[13] Zhao X F,Ouyang D T.Improved algorithms for deriving all minimal conflict sets in model-based diagnosis[A].Lecture Notes in Computer Science[C].springer.2007,4681:157-166.
(1)IsHS算法用于判定给定的一个集合H是否给定集合簇F的碰集,即判定H是否和F中每一个集合交集是否都非空.
(2)注:初始情况下,给定冲突集合簇F时,C={e|e∈S,S∈F},后面提到的CSSE-Tree方法、CSISE-Tree方法、CS-tree with Mark Set方法初始情况与之相同.
[2] Zhao X,Ouyang D.Deriving all minimal hitting sets based on join relation[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems,2015,45(7):1063-1076.
[3] 赵相福,欧阳丹彤.使用SAT求解器产生所有极小冲突部件集[J].电子学报,2009,37(4):804-810.ZHAO Xiang-fu,OUYANG Dan-tong.Deriving all minimal conflict sets using satisfiability algorithms[J].Acta Electronica Sinica,2009,37(4):804-810.(in Chinese)
[4] 欧阳丹彤,刘伯文,周建华,张立明.结合问题特征利用SE-Tree反向深度求解冲突集的方法[J].电子学报,2017,45(5):1175-1181.OUYANG Dan-tong,LIU Bo-wen,ZHOU Jian-hua,ZHANG Li-ming.A method ofcomputing minimal conflict sets combining the structure property with the anti-depth SE-tree[J].Acta Electronica Sinica,2017,45(5):1175-1181.(in Chinese)
[5] 刘梦,欧阳丹彤,刘伯文,张立明,张永刚.结合问题特征的分组式诊断方法[J].电子学报,2018,46(3):589-594.LIU Meng,OUYANG Dan-tong,LIU Bo-wen,ZHANG Li-ming,ZHANG Yong-gang.Grouped diagnosis approach using the feature of problem[J].Acta Electronica Sinica,2018,46(3):589-594.(in Chinese)
[6] Reiter R.A theory of diagnosis from first principles[J].Artificial Intelligence,1987,32(1):57-95.
[7] Wotawa F.A variant of Reiter’s hitting-set algorithm[J].Information Processing Letters,2001,(79):45-51.
[8] 王肖,赵相福.用CHS-tree基于集合势的方法计算极小碰集[J].计算机集成制造系统,2014,20(2):401-406.Wang Xiao,Zhao Xiangfu.Computing minimal hitting sets with CHS-tree method[J].Computer Integrated Manufacturing Systems.2014,20(2):401-406.(in Chinese)
[9] 姜云飞,林笠.用对分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)
[10] 姜云飞,林笠.用布尔代数方法计算最小碰集[J].计算机学报,2003,26(8):919-924.Jiang Yunfei,Lin Li.The computation of hitting sets with Boolean formulas[J].Chinese Journal of Computers,2003,26(8):919-924.(in Chinese)
[11] Zhao X F,Ouyang D T.A method of combining SE-tree to compute all minimal hitting sets[J].Progress in Natural Science,2006,16(2):169-174.
[12] Han,B,Lee,S J.Deriving minimal conflict sets by CS-trees with mark set in diagnosis from first principles[J].IEEE Transactions on Systems,Man,and Cybernetics,1999,29(2):281-286.
[13] Zhao X F,Ouyang D T.Improved algorithms for deriving all minimal conflict sets in model-based diagnosis[A].Lecture Notes in Computer Science[C].springer.2007,4681:157-166.
(1)IsHS算法用于判定给定的一个集合H是否给定集合簇F的碰集,即判定H是否和F中每一个集合交集是否都非空.
(2)注:初始情况下,给定冲突集合簇F时,C={e|e∈S,S∈F},后面提到的CSSE-Tree方法、CSISE-Tree方法、CS-tree with Mark Set方法初始情况与之相同.