基于模型诊断中计算碰集的方法

《基于模型诊断中计算碰集的方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第25卷第4期增刊仪器仪表学报2004年8月基于模型诊断中计算碰集的方法‘欧阳丹形‘,z欧阳继红‘.z程晓春，刘杰‘.z‘(吉林大学计算机科学与技术学院长春130012)2(吉林大学符号计算与知识工程教育部重点实验室长春130012)'(DepartmentofComputerScience，UniversityofReading,RG66AY，Reading,England)摘要基于模型诊断是为了克服传统故障诊断方法的缺点而兴起的一项新型的智能推理技术。人们已经建立了基于模型诊指断与本原蕴涵/蕴涵式的直接关系。这里论证了极小碰集与本原蕴涵/蕴涵式

2、的关系。提出了碰集计算方法一NEWHS-tree,而出:该算法需要搜索的结点数比Greiner的HS-DAG算法需要搜索的结点数大大减少，而且能够处理多故障诊断问题，Slagle等学者提出的算法不能处理多故障诊断问题。关键词AMethodofComputingHittingSetinModel一basedDiagnosisOuyangDantong"OuYangJihong"ChengXiaochun3LiuJie''(SchoolofComputerScienceandTechnology,JilinUniversity,Changchun130

3、012,China)'(KeyLaboratoryofSymbolicComputationandKnowledgeEngineeringofMOE,JinliuUniv,Changchun130012,China)3(DepartmentofComputerScience,UniversityofReading,RG66AY,Reading,England)AbstractModel-baseddiagnosisisanewintelligentdiagnosistechniqueraisedtoovercometheshortcomingsof

4、traditionaldiagnosticmethods.Thedirectrelationshipmodel-baseddiagnosisandimplicants八mplicateshasbeenestablished.Therelationshipamongminimumhittingsetandprimeimplicants八mplicatesisdemonstrated.ThealgorithmNEWHS-treeofcomputinghittingsetisgiven.It'salsopointedoutthatthenumberofn

5、odesneedtobesearchedbythisalgorithmislessthanthatofbyGreiner'salgorithm.Furthermore，thisalgorithmcandealwithmulti-faultdiagnosis，whereasthealgorithmbySlagleetal.can't.KeywordsModel-baseddiagnosisHittingsetPrimeimplicant/implicate文献[4^-7]分别建立了基于一致性诊断、溯因诊1引一言断、基于模型诊断与本原蕴涵/蕴涵式的直接

6、联系。在此笔者证明了极小碰集与本原蕴涵之间有一一对应关基于模型诊断是为了克服传统诊断方法的严重缺系，因此，计算极小碰集的方法可用于计算本原蕴涵。陷而兴起的一项新型智能推理技术，在20世纪80年而本原蕴涵和本原蕴涵式又是互为对偶的两个概念，代中期成了热门研究课题，其应用也越来越广泛。其基因此，计算碰集的方法既可用于计算本原蕴涵又可用本观点是可以使用系统的模型(即内部结构与行为的于计算本原蕴涵式，即可用于计算诊断。知识)进行诊断，这是该方法与传统诊断方法的本质区早在1972年，Karp18J即提出了碰集(hitting-set)别，被AI专家誉为诊断理

7、论和技术上的革命["'.Con一问题，到了1987年，Reiter[']在计算基于一致性极小诊sole和Dressler[21指出:基于模型诊断对整个AI领域断过程中利用了碰集的概念来计算极小冲突部件集簇的研究起着重要推动作用。StrussE3〕称基于模型诊断是的所有极小碰集，同时提出了HS-tree算法。然而，Re-对AI的一个重要挑战和检验。iter提出的HS-tree方法存在着一些问题，他提出的关本文系国家自然科学基金(69903005)、国家高技术研究发展计划(2003AA118020)经费资助项目。606仪器仪表学报第25卷闭结点策略和剪

8、枝策略共同作用后，在有些情况下可本原蕴涵与本原蕴涵式是对偶的，如果一个算法能够能导致删去极小碰集，因此丢失了可能的诊断解。