The compact classifier system: motivation, analysis, and first results

ABSTRACT

This paper presents an initial analysis of how maximally general and accurate rules can be evolved in a Pittsburgh-style classifier system. In order to be able to perform such analysis we introduce a simple bare-bones Pittsburgh classifier systems---the compact classifier system (CCS)---based on estimation of distribution algorithms. Using a common rule encoding scheme of Pittsburgh classifier systems, CCS maintains a dynamic set of probability vectors that compactly describe a rule set. The compact genetic algorithm is used to evolve each of the initially perturbed probability vectors which represents the rules. Results show how CCS is able to evolve in a compact, simple, and elegant manner rule sets composed by maximally general and accurate rules.

REFERENCES

• 1: K. A. De Jong and W. M. Spears. Learning Concept Classification Rules using Genetic Algorithms. In Proceedings of the Twelfth International Conference on Artificial Intelligence IJCAI-91, volume 2, pages 651--656. Morgan Kaufmann, 1991.
• 2: G. Harik, F. Lobo, and D. E. Goldberg. The compact genetic algorithm. Proceedings of the IEEE International Conference on Evolutionary Computation, pages 523--528, 1998. (Also IlliGAL Report No. 97006).
• 3: Cezary Z. Janikow, A Knowledge-Intensive Genetic Algorithm for Supervised Learning, Machine Learning, v.13 n.2-3, p.189-228, Nov./Dec. 1993 [doi>10.1007/BF00993043]
• 4: P. Larrañaga and J. A. Lozano, editors. Estimation of Distribution Algorithms. Kluwer Academic Publishers, Boston, MA, 2002.
• 5: X. Llorà and J. Garrell. Knowledge-Independent Data Mining with Fine-Grained Parallel Evolutionary Algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'2001), pages 461--468. Morgan Kaufmann Publishers, 2001.
• 6: X. Llorà, K. Sastry, and D. E. Goldberg. Binary Rule Encoding Scheme: A Study Using The Compact Classifier System. In International Workshop on Learning Classifier Systems (IWLCS 2005), accepted, 2005.
• 7: S. W. Wilson. Classifier fitness based on accuracy. Evolutionary Computation, 3(2):149--175, 1995.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

General Terms:
Algorithms, Design, Theory

Keywords:
compact classifier system, learning classifier systems, maximally general classifiers, spawning and merging populations