Research Of Genetic Algorithm And Relative Algorithms For Minimal Hitting Sets

Model-based diagnosis is a new type of intelligent reasoning technology, overcoming traditional fault-diagnosis methods'shortcomings. And model-based diagnosis is one of the active branches of Artificial Intelligence, and more and more widely applied.　nowadays, MBD has been applied to more practical aspects, such as automotive systems diagnosis, monitoring of gas turbines, and so on.Traditional rule-based diagnosis mainly depends on experts'experiences. And it has strict domain-dependency too. However, model-based diagnosis has strong device-independency. In model-based diagnosis, domains and system models are apart, so that it can be used to diagnosis another system, with the corresponding system model be replaced only.Generally, there are several steps towards to the final diagnosis results: diagnosis generation, diagnosis testing and diagnosis authentication. First, diagnosis generation is according to discrepancies between practical behaviors and anticipative behaviors of system and deduces the faulty component sets by the system model and logical reasoning. There are more than one component sets. Second, diagnosis testing eliminates illogical sets by reasoning. There are some component sets left behind which can explain practical behaviors. Third, by additional information, diagnosis authentication can eliminate the component sets which exist after diagnosis testing.For a system diagnosis, first, It is a very important step of building a fittest model, according to corresponding domain knowledge, which should be able to express the relationship of the components in a system, and be simulated and forecasted when the real system is running, in order to infer and diagnosis. Reiter gave a formal description of model-based diagnosis in 1-order logic. Moreover, some scholars made use of qualitative equation to build system models.Dignosis generation, Candidate generation, which is a procedure of generating all minimal hitting sets (MHSs), is proved as an NP-complete problem. Many researchers have studied the problem. However, some solutions may be lost by pruning in some methods, or a tree or a graph needs to be constructed, and the corresponding data structure and algorithm are quite complex, or computing by recursion, which is rather inefficient in some methods, etc. In order to overcome the shortcomings mentioned above, we propose a novel method of judging hitting sets by genetric algorithm(GA) and equalent component sets(EC). GA can gain 95% solutions within 100 generation by recursive computation and EC can devide lots of sets into some clusters so that it simplify computation and promote efficiency. The EC-GA is easy to be understood and implemented. Comparing with other effective algorithms with completeness in some experimental tests, results show that the diagnosis efficiency is higher, particularly for single- and double-fault diagnosis.The virtue of SE-tree is helpful to generate all minimal hitting sets(MHSs): that is to extend a tree in a best-first fasion, then we can gain all MHSs in a smaller depth. Furthermore, the procedure is formalized by combining SE-tree with closed nodes to generate all MHSs. Combined with GA and EC, we propose other methods: SEHS-GA and SEHS-EC. The two methods adopt the solution proposed by Rymon: The SE-HS. With the virtue of it, also combined with GA, EC, the two methods promote computation's efficiency highly , compared with SE-HS.Based on BHS-tree which generate MHSs promoted by Jiang Yuefei, it has the following three virtue: first, the nodes generated by a tree are smaller than the HS-tree, so its efficiency is high; second, it does not need to prune tree sothat the solutions are not able to be lost; last, when some conflict sets are added, the new hitting sets can be computed based on old hitting sets and new conflict sets. Based on them, combined with GA, EC and SE-tree, we introduce some new methods: BHSGA-tree, BHSEC-tree and BHSSE-tree. They improve the BHS-tree method. First, BHSGA-tree has the virtue of radom and optimal selection; second, BHSEC-tree has the virtue of equalent components; third, BHSSE-tree has the virtue of extention in a best-first fasion. Above of them can promote the computation efficiency higher. For comparing with the efficient method BHS-tree, we have found when the number of the same components of one set is largest in hitting sets, our method is more efficient. In addition, we have compared their virtue. Considering the similarity of generation of all MCSs and all MHSs, a uniform framework for deriving all MCSs and MHSs is discussed accordingly. Furthermore, all the correct methods can also be used computing both prime implicants and prime implicates. We have implemented all the three algorithms and compared the efficiencies of them, and then analysed the fittest situation for each of them. Furthermore, we gave a brief summary about nearly all the methods so far. And we have a simply discussion finally.There may be many groups of candidate results after the step of candidate generation. In order to reduce the candidate results, it needs to differentiate all the candidate ones by measurements to find the real diagnosis results, and the procedure is called diagnosis authentication. However, there may be many observable components in a system generally, how to choose a good order of the measurements by the least cost in order to discover the real diagnosis? So that it is related to an optimization problem. Many researchers have studied it, such as methods based on entropy, method based probability, etc. And we firstly gave some correction of BHS-tree proposed by Jiang Yunfei applied to a real example. And then we presented some improvement of the algorithm and its application on the example, considering the order of the measurements. Finally, we have a simply discussion about methods of optimization of choosing the order of measurements.