An evolutionary algorithm for identifying faults in t-diagnosable systems

The paper describes a novel approach to the problem of system-level fault diagnosis using genetic algorithms. Consider a system composed of n independent units, each of which tests a subset of the others. It is assumed that at most t of these units are permanently faulty. Such a system is said to be t-diagnosable if, given any complete collection of test results, the set of faulty units can be uniquely identified. Genetic algorithms have recently received much attention as a class of robust stochastic search algorithms for various optimization problems. An efficient method based on evolutionary algorithms is developed to solve the diagnosis problem. The representation of the search space used is in the form of a binary vector of length n. Each bit indicates the status (faulty or fault-free) of its corresponding unit. Genetic operators are adapted to the context of system-level diagnosis. The genetic algorithm was implemented and tested on random test graphs. The simulation results demonstrate the efficiency of the proposed diagnosis algorithm