Analysis of the Niche Genetic Algorithm in Learning Classifier Systems

Learning Classifier Systems (LCS) evolve IF-THEN rules for classification and control tasks. The earliest Michigan-style LCS used a panmictic Genetic Algorithm (GA) (in which all rules compete for selection) but newer ones tend to use a niche GA (in which only a certain subset of rules compete for selection at any one time). The niche GA was thought to be advantageous in all learning tasks, but recent research suggests it has difficulties when the rules composing the solution overlap. Furthermore, the niche GA's effects are implicit, making it difficult study, and fixed, which prevents tuning its performance. Given these issues, we set out on a long-term project to reevaluate the niche GA. This work is our starting point and in it we address the implicit and unquantified effects of the niche GA by building a mathematical model of the probability of rule selection. This model reveals a number of insights into the components of rule fitness, particularly the bonus for rule generality and penalty for overlaps, both previously unquantified. These theoretical results are our primary contribution. However, to demonstrate one way to apply this theory, we then introduce a new variant of the UCS algorithm, which uses a hybrid panmictic/niche GA. Preliminary results suggest, unexpectedly, that the niche GA may have even more drawbacks than previously thought.