Analysis of the Niche Genetic Algorithm in Learning Classifier Systems

Tim Kovacs*, Robin Tindale

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

2 Citations (Scopus)

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 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.

Original languageEnglish
Title of host publicationGECCO'13: PROCEEDINGS OF THE 2013 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE
EditorsC Blum
Place of PublicationNEW YORK
PublisherAssociation for Computing Machinery (ACM)
Pages1069-1076
Number of pages8
ISBN (Print)978-1-4503-1963-8
Publication statusPublished - 2013
Event15th Genetic and Evolutionary Computation Conference (GECCO) - Amsterdam, Netherlands
Duration: 6 Jul 201310 Jul 2013

Conference

Conference15th Genetic and Evolutionary Computation Conference (GECCO)
CountryNetherlands
Period6/07/1310/07/13

Keywords

  • Learning Classifier Systems
  • Niche Genetic Algorithm
  • ACCURACY

Cite this