Computing Minimal Hitting Sets with Genetic Algorithm
Lin Li, Yunfei Jiang · 2002
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.