First-Order Concept Learning Using Genetic Algorithms

摘要

A framework for combining first-order concept learning with Genetic Algorithms is introduced. This framework includes: 1) a novel binary representation for clauses 2) task-specific genetic operators 3) a fast evaluation mechanism. The proposed binary representation encodes the refinement space of clauses in a natural and compact way. It is shown that essential operations on clauses such as unification and anti-unification can be done by simple bitwise operations (e.g. and/or) on the binary encoding of clauses. These properties are used for designing task-specific genetic operators. It is also shown that by using these properties individuals can be evaluated at genotype level without mapping them into corresponding clauses. This replaces the complex task of evaluating clauses, which usually needs repeated theorem proving, by simple bitwise operations. An implementation of the proposed framework is used to combine Inverse Entailment of the learning system CProgol with a genetic search.