Learning Disjunctive Concepts by Means of Genetic Algorithms

Abstract

REGAL is a Distributed Genetic Algorithm designed for learning concept descriptions from examples, in First Order Logic. In particular, each individual in the population represents a conjunctive formula in VL2 language. In order to increase the efficiency of the generalization process, REGAL has been provided with a new selection operator, called Universal Suffrage operator, which guarantees (in probability) to maintain a population covering all the learning events. As generalization mostly takes place when two individuals covering different sets of examples are crossed, the global generalization capability of the system is increased. Moreover, in the case of disjunctive or multiple concepts, the universal suffrage algorithm allows the formation of different species, each one corresponding to a different disjunct. In this way, all the disjuncts can be learned in parallel obtaining, in average, more general solutions than by learning them one at a time. A formal analysis of the universal suffrage operator is presented, providing theoretical explanations of the experimentally observed behaviour. A comparison with the classical selection algorithm and with the sharing function method is also made. Finally, a long term control strategy, called “Tories and Whigs”, is proposed in order to overcome the problem of lethal matings between uncompatible disjuncts. The effectiveness of REGAL is demonstrated on several learning problems.