Research And Improvement Of Genetic Algorithm For Minimal Hitting Sets

Model-based diagnosis is one of branches of Artificial Intelligence.It is anew type of intelligent diagnosis technology for overcoming traditionalfault-diagnosis technology'shortcomings.Since many advantages, model-baseddiagnosis is researched and applied widely.Traditional diagnosis technology mainly depends onexperts'experiences.It is difficult to obtain knowledge.And it has strictdomain-dependency.However,model-based diagnosis use structure andbehavior information of the systems. It can be obtained in the design orproduction stage of equipment.We can establish a system logic model. Ifmodel is reasonable, we can diagnose most faults of system, furthermore wecan give a reasonable explanation for diagnosis.When some components arereplaced, logic model can be used on new system after some modifications.Soit has strong device-independency, overcoming traditional fault-diagnosistechnology'shortcomings.Generally speaking,diagnosis process is divided into Four parts:systemmodeling, conflict identification, candidate generation and measurement.System model can be builded using standards artificial intelligence technologyincluding predicate logic, frames, and constraints,and so on. Conflict sets can be identifyed by the system model and the observations reasoning. The objectof candidate generation is to find all minimal hitting sets from conflict sets. Byadditional detection information,measurement distinguish candidate,find thereal fault components.The procedure of generating minimal hitting sets,has been proved as anNP-complete problem.Many researchers have studied the problem.However,there are some shortcomings for existing algorithms: result may be lost bypruning,or complex data structures needs to be constructed such as tree orgraph, or computing by recursion,which is inefficient,etc.In order to overcomethe shortcomings mentioned above,LinLi gave a method of using GeneticAlgorithm to calculate minimal hitting sets,GA improve the complicacy ofminimal hitting sets both in time and space,and can find more than ninety fivepercent result at most of time.However Simple Genetic Algorithm depends oncrossover and variation to produce new filial generation, going withprematurity the ability of search for result will reduce with evolvement. Inorder to overcome the shortcomings this paper propose a function of hittingdegree as follows:(1) H(e) means the number of conflict set which contains e.(2) SH(X) means the sum of H(e) for each e in X.For individual X, if SH (X) is less than the number of conflict set, then X isnot a hitting set, this is a necessary condition. If the function value ofindividual is too high,it means the individual has plunge in local infinite result.The new algorithm include operation to jump from local infinite area,soit can keep the search process in a efficiency area,and generate minimal hittingsets more efficiency. The process of the above compose accelerate operator,The fact that this operator plays the role well has been proved by experiment,with less searching time and high ratio.Intelligent optimization algorithm is important research content inartificial intelligence area. Except classical Genetic Algorithm, many newintelligent agent has presented,such as Immune algorithms,simulatedannealing , Particle Swarm Optimization and so on.This paper propose a newmethod for generating minimal hitting sets using Immunity GeneticAlgorithm.For a set which has intersect with some conflict set, We should firstconsider those high-frequency elements in other conflict set. This greedystrategy can not ensure global optimality, However,it can be regarded as alocal optimal solution.Based on basic frame of Genetic Algorithm,using thecharacter of minimal hitting sets problem to inoculate bacterin for individuals,experiment prove this method improve efficiency. Simulated annealingAlgorithm has excellent ability search for results in domain of neighbor,andavoid from local results. This paper propose a new method for generatingminimal hitting sets using Simulated annealing Genetic Algorithm, experimentprove this method improve efficiency.At last, This paper design a fault diagnose system for a sort of combinedcircuit using the idea of model-based diagnosis.The system include four part:first of all, establish the model of circuit using appropriate datastructure.Second,find all minimal conflict set of fault circuit using the idea ofassumption-based truth maintenance system. Third, find all minimal hittingsets from all minimal conflict set. Fourthly,find the real components whichbroken-down using reasonable method of measure.