Using Coverage as a Model Building Constraint in Learning Classifier Systems

Abstract

Promoting and maintaining diversity is a critical requirement of search in learning classifier systems (LCSs). What is required of the genetic algorithm (GA) in an LCS context is not convergence to a single global maximum, as in the standard optimization framework, but instead the generation of individuals (i.e., rules) that collectively cover the overall problem space. COGIN (COverage-based Genetic INduction) is a system designed to exploit genetic recombination for the purpose of constructing rule-based classification models from examples. The distinguishing characteristic of COGIN is its use of coverage of training set examples as an explicit constraint on the search, which acts to promote appropriate diversity in the population of rules over time. By treating training examples as limited resources, COGIN creates an ecological model that simultaneously accommodates a dynamic range of niches while encouraging superior individuals within a niche, leading to concise and accurate decision models. Previous experimental studies with COGIN have demonstrated its performance advantages over several well-known symbolic induction approaches. In this paper, we examine the effects of two modifications to the original system configuration, each designed to inject additional diversity into the search: increasing the carrying capacity of training set examples (i.e., increasing coverage redundancy) and increasing the level of disruption in the recombination operator used to generate new rules. Experimental results are given that show both types of modifications to yield substantial improvements to previously published results.