Font Size: a A A

Improved Algorithms For Computing All Minimal Hitting-sets

Posted on:2018-10-27Degree:MasterType:Thesis
Country:ChinaCandidate:X W SheFull Text:PDF
GTID:2348330518475042Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
At present,with the development of science and technology,model-based fault diagnosis has been an important research topic in fault diagnosis.Given a description of a system,the difference between the observed behavior and the system's assumed correct behavior,we can infer the system worked normally or not to find the system faults.Generating candidate diagnoses is one of the most critical steps in finding diagnosis.In recent years,there have been lots of approaches for generating all cardinate diagnoses(i.e.minimal hitting-sets,MHSes).Artificial intelligence expert Reiter proposed HS-tree algorithm in 1987,which is the most classical algorithm.However when we use HS-tree algorithm to compute all MHSes,we find the pruning process is cumbersome,and in some cases the correct solutions will be lost.HS-tree algorithm generates many redundant nodes,and then it is not suitable for large-scale systems.In this paper,we proposed three improved algorithms for computing all MHSes.(1)A new method computing all MHSes for all conflict sets is proposed,MDMC-HS-tree(shorten for Max-Degree-Min-Cardinality-based Hitting-sets-tree).First,the sets with minimal cardinality are selected from the current conflict set cluster to be expanded,so as to reduce the width of the tree.Then,the largest degree element in the minimal cardinality set is chosen to reduce current conflict set cluster.Experimental results show that the algorithm can generate all MHSes and produce a smaller number of nodes,even for a large number of conflict sets.The algorithm is feasible for computing all MHSes in model-based diagnosis.(2)An improved algorithm based on the dynamic maximum degree was proposed to compute all MHSes.All necessary collections are generated by enumeration,according to the degree of the elements.Although the sets are generated by enumeration,many sets are avoided by reducing the elements with degree 0 in the extending process.(3)An improved of Matrix-based algorithm M-MHS was studied for computing all MHSes.The elements in the cluster are stored in a set S and are arranged by degree.By finding the element corresponding to the 0 column in the initial matrix and the element to be found is formed into a hitting-set.This algorithm through the number of the remaining set of elements in the S to determine whether to terminate the algorithm.The calculate process of the improved algorithm is more simple,and improved calculation efficiency.Finally,the three new improved algorithms are compared with several classical algorithms,and they are compared by some examples.
Keywords/Search Tags:Model-Based Diagnosis, MDMC-HS-tree, Parameter Matrix, Max Degree, Minimal Cardinality
PDF Full Text Request
Related items