Skip to main content

Analysis of the niche genetic algorithm in learning classifier systems

Tim Kovacs, Robin Tindale, Analysis of the niche genetic algorithm in learning classifier systems. Genetic and Evolutionary Computation Conference, GECCO '13. ISBN 978-1-4503-1963-8, pp. 1069–1076. July 2013. PDF, 552 Kbytes.

Abstract

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 im- plicit, 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 math- ematical 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 draw- backs than previously thought.

Bibtex entry.

Contact details

Publication Admin