Learning disjunctive concepts with distributed genetic algorithms

Inducing concept descriptions from examples is a machine learning task that can be formulated as a search problem. Recently, genetic algorithms proved to be an appealing alternative for searching concept description spaces, because of their great exploration power and their suitability to exploit massive parallelism. In order to exploit genetic algorithms for searching the space of formulas φ (the elements of the population), we must reformulate the set covering problem by suitably defining the representation scheme for the formulas, the genetic operators and the fitness function. The system described in this paper, REGAL (Giordana and Saitta, 1993), encodes first order logic (FOL) formulas φ into bit strings of fixed length. In order to make this possible, REGAL´s representation language, L, has been constrained to be finite, by defining a language template, Λ, which represents the maximally complex formula in L. The resulting language contains FOL formulas built up with conjunction, disjunction, negation, internal disjunction and existential and universal quantification