Research And Improvement Of PSO Algorithm For Minimal Hitting Sets

Model-based diagnosis technology is an important topic of artificial intelligence, it isproposed to overcome the severe defects existing in the traditional fault diagnosis methodsand to identify the faulty components. The basic idea of Model-based diagnosis technology isto simulate the system problem with logical model. According to the system model and input,we can derive the expectation under the normal condition of the system model. Compared theexpectation and the result we observed, if there are some difference, it proves some faultycomponents exist in the system, and we need to find out these faulty components by logicalreasoning. There are essential difference between model-based diagnosis technology andtraditional diagnosis technology. The shortcoming of traditional diagnosis technology ismainly manifested in three aspects: depend on expert’s experience; knowledge acquisition isrelatively difficult; strong dependence on equipment. Model-based diagnosis technology islargely overcome these limitations. MBD need not depend on expert’s experience, it canestablish a reasonable logical model according to the system’s information. In addition,model-based diagnosis technology improves the equipment dependent of traditional diagnosistechnology, when the system components change, we just need make some relevant change tothe logical model before it used to new equipment. Model-based diagnosis technology isincreasingly used in model industry, such as automobile fault diagnosis, spacecraft faultdiagnosis, circuit troubleshooting, medical fault diagnosis, etc.In the process of model-based diagnosis, computing minimal hitting sets is the last andkey step to show the final result of diagnosis. In general, we need to compute all minimalconflict set cluster, then compute the minimal hitting set, in other words, the minimaldiagnosis. In reality, a lot of practical problems can be converted into minimal hitting setsproblem, such as teachers and curricula problem, minimum covering sets problem, etc. Since1972, the computer expert Richard. manning. karp from the university of California, Berkeleyproposed the minimal hitting sets problem, it attracted many international experts’ attentionand intensive study, and many classical algorithms for computing minimal hitting sets were proposed. These algorithms can be roughly divided into two categories according to theintegrity of solution, complete algorithms and incomplete algorithms. Complete algorithmscan find out all minimal hitting sets, but these algorithms’ structure are complex, they are notsuitable for solving large-scale problem. Incomplete algorithms can’t guarantee to find out allminimal hitting sets, but can greatly reduce the space complexity and time complexity ofminimal hitting sets computation. With the rapid development of science and technology, theminimal hitting sets problem present to be more complex, the complexity of computingminimal hitting sets with complete algorithms will increase drastically, so an algorithm thatcan keep good balance between completeness and complexity is very important.This paper introduces several typical algorithms for computing minimal hitting sets, takesome example to explain the calculation process and made some analysis and comparison.And this paper focuses on the algorithm for computing minimal hitting sets with particleswarm optimization(PSO). Then by studying the characteristics of minimal hitting sets,combining with the original PSO algorithm of computing minimal hitting sets, this paperproposes a new algorithm to guide the minimal hitting sets computation: introducing alearning mechanism，which can provide two hitting sets’ length to cut down some search ofthe no-solution space; adding a flipping strategy to accelerate some solving of solution space.To compute minimal hitting sets base on PSO algorithm not only because the PSO algorithmhas simpler data structure and less calculated amount, even compare with some otherincomplete algorithms such as genetic algorithm, it’s program is also simpler becauseavoiding introducing some other operator. Abundant experimental results show a significantimprovement of this algorithm in computing minimal hitting sets.