Research On The Method Of Minimal Hitting Sets With Improved Firefly Algorithm Combined MaxSAT Technology

As a new intelligent fault diagnosis technology,the Model-Based Diagnosis(MBD)overcomes the serious defects of traditional fault diagnosis methods and becomes a research hotspot in the field of Artificial Intelligence.MBD has been widely used in many fields.The calculation of the minimal hitting set is a key step in MBD.These relative algorithms could be divided into a complete part and an incomplete one.The complete algorithm can get all the solutions,but usually,that is too complex to solve large-scale problems.The incomplete algorithm sacrifices the completeness and accuracy,and does not need to find out all the minimal hitting sets.Because of the reduction of computational complexity,the incomplete algorithm is suitable for solving large-scale systems,which is of great significance to practical problems.In this paper,based on the depth study of the problem of minimal hitting sets,an incomplete algorithm for solving the minimal hitting set based on Firefly Algorithm(FA)is proposed for the first time,and the corresponding improvement strategy is also proposed for the deficiency of the algorithm.(1)For solving the problem of the minimal hitting set,the standard FA algorithm is discretized to arrive at the Discrete Firefly Algorithm(DFA).The location of fireflies is described by a binary vector,and that of each firefly represents a feasible solution of the optimization problem.The corresponding fitness function is introduced to guide the evolution and update of fireflies,and then the hitting sets are obtained.After deleting the superset by subset detection,one gets the minimal hitting sets.Comparing the experimental results with the current mature Particle Swarm Optimization(PSO),DFA has faster convergence speed and can get more minimal hitting sets under the same iteration times.When the number of minimal hitting sets is larger,DFA can get more minimal hitting sets in unit time.(2)In order to further improve the efficiency of the algorithm,this paper proposes the Skipping strategy and the Flipping strategy for the solution space and the nonsolution space,respectively.In the solution space,this Skipping method reinitializes variables randomly,so that it makes the firefly individuals in the solution space skip out of the cycle,prevents the solution from falling into a stagnation state,and increases the randomness of the solution.Besides,it flips one variable according to the least frequent,for reducing the cases that some elements are not selected for a long time and increasing the diversity of the solution.In the non-solution space,the Flipping method flips some variables from 0 to 1 and it will stop when that solution becomes a hitting set.In this way,one can reduce the search for the non-solution space.(3)It presents a trend of development that the solution of minimal hitting set problem is more and more complicated.For the problem of less evolution and low efficiency when the DFA is used to solve large-scale problems,this paper calls the maximum satisfiability(MaxSAT)solver based on DFA.In the process of solving the hitting set problems with DFA,it introduces the unweighted partial MaxSAT technology and assigns the result of that to a firefly individual as a minimal hitting set with a short length.Hence,it is achieved to reduce the size of hitting set clusters.Compared with the original algorithm,the DFA-MaxSAT method can improve the accuracy of solutions and reduce the running time.