Learning Structured Concepts Using Genetic Algorithms

Abstract

Inducing concept descriptions in first order logic is inherently a complex task which can be managed only by using heuristics. In this paper, we show that there are problems which cannot be properly solved, using the well known information gain heuristics, because the true concept descriptions are outside the space explored by the search strategy. Therefore, more powerful search strategies are necessary and Genetic Algorithms are suggested as a possible alternative. In fact, Genetic Algorithms are able to explore large domains because they make use of a multipoint search strategy and are suitable to exploit massive parallelism. An experimental system called GA-SMART, capable of inducing concept descriptions in Conjunctive Normal Form, is described. By properly restricting the concept description language, first order logic formulae can be mapped on a fixed length bit string representation. Then, a variant of a simple genetic algorithm is used to search for concept descriptions. The genetic algorithm is guided by a fitness function which trades off completeness, consistency and simplicity of the hypotheses. The system has been experimented on several test cases taken from the international machine learning database and, in all cases, the results compare favourably with those obtained by classic inductive systems. Finally, it is shown how an induction problem, deceptive for a system guided by information gain heuristics, can be easily solved by a Genetic Algorithm.