Computing Minimal Hitting Sets with Genetic Algorithm
Proceedings of the 13th International Workshop on Principles of Diagnosis, page 77-80. (2002)Abstract
A set S that has a non-empty intersection with every set in a collection of sets C is called a hitting set of C. If no element can be removed from S without violating the hitting set property, S is considered to be minimal. Several interesting problems can be partly formulated as ones that a minimal hitting set or more ones have to be found. Many of these problems are required for proper solutions, but sometimes the approximate solutions are enough. A genetic algorithm and advantaged algorithms were devised for computing minimal hitting sets. An improvement makes them get most minimal hitting sets efficiently. Furthermore, they are smaller, i.e., fewer rules.