An analysis of matching in learning classifier systems

ABSTRACT

We investigate rule matching in learning classifier systems for problems involving binary and real inputs. We consider three rule encodings: the widely used character-based encoding, a specificity-based encoding, and a binary encoding used in Alecsys. We compare the performance of the three algorithms both on matching alone and on typical test problems. The results on matching alone show that the population generality influences the performance of the matching algorithms based on string representations in different ways. Character-based encoding becomes slower and slower as generality increases, specificity-based encoding becomes faster and faster as generality increases. The results on typical test problems show that the specificity-based representation can halve the time required for matching but also that binary encoding is about ten times faster on the most difficult problems. Moreover, we extend specificity-based encoding to real-inputs and propose an algorithm that can halve the time require for matching real inputs using an interval-based representation.

REFERENCES

• 1: E. Bernadó-Mansilla and T. K. Ho. Domain of competence of XCS classifier system in complexity measurement space. IEEE Trans. Evolutionary Computation, 9(1):82--104, 2005.
• 2: M. V. Butz. XCS (+ tournament selection) classifier system implementation in c, version 1.2. Technical Report 2003023, Illinois Genetic Algorithms Laboratory -- University of Illinois at Urbana-Champaign, 2003.
• 3: Martin V. Butz, Kernel-based, ellipsoidal conditions in the real-valued XCS classifier system, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068320]
• 4: M. V. Butz. Rule-Based Evolutionary Online Learning Systems: A Principled Approach to LCS Analysis and Design. Studies in Fuzziness and Soft Computing. Springer Verlag, Berlin-Heidelberg, Germany, 2006.
• 5: M. V. Butz, T. Kovacs, P. L. Lanzi, and S. W. Wilson. Toward a theory of generalization and learning in XCS. IEEE Transaction on Evolutionary Computation, 8(1):28--46, Feb. 2004.
• 6: Martin V. Butz , Pier Luca Lanzi , Stewart W. Wilson, Hyper-ellipsoidal conditions in XCS: rotation, linear approximation, and solution structure, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144237]
• 7: M. V. Butz and S. W. Wilson. An algorithmic description of XCS. Journal of Soft Computing, 6(3-4):144--153, 2002.
• 8: Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 2006
• 9: Marco Dorigo , Marco Colombetti, Robot Shaping: An Experiment in Behavior Engineering, MIT Press, Cambridge, MA, 1997
• 10: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 11: J. H. Holland and J. S. Reitman. Cognitive systems based on adaptive algorithms. 1978. Reprinted in: Evolutionary Computation. The Fossil Record. David B. Fogel (Ed.) IEEE Press, 1998. ISBN: 0-7803-3481-7.
• 12: K. A. D. Jong and W. M. Spears. Learning Concept Classification Rules using Genetic Algorithms. In Proceedings of the Twelfth International Conference on Artificial IntelligenceIJCAI-91, volume 2, 1991.
• 13: Nicolai M. Josuttis, The C++ standard library: a tutorial and reference, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 14: Tim Kovacs , Manfred Kerber, What Makes a Problem Hard for XCS?, Revised Papers from the Third International Workshop on Advances in Learning Classifier Systems, p.80-102, September 15-16, 2000
• 15: P. L. Lanzi. The XCS library. 2002.
• 16: Pier Luca Lanzi , Stewart W. Wilson, Using convex hulls to represent classifier conditions, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144240]
• 17: X. Llorá and K. Sastry. Software for fast rule matching using vector instructions. http://www.illigal.uiuc.edu/web/xllora/2006/01/19/, Last checked on March 21th 2008.
• 18: Xavier Llorà , Kumara Sastry, Fast rule matching for learning classifier systems via vector instructions, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144244]
• 19: Christopher Stone , Larry Bull, For real! XCS with continuous-valued inputs, Evolutionary Computation, v.11 n.3, p.299-336, Fall 2003 [doi>10.1162/106365603322365315]
• 20: Stewart W. Wilson, Classifier fitness based on accuracy, Evolutionary Computation, v.3 n.2, p.149-175, Summer 1995 [doi>10.1162/evco.1995.3.2.149]
• 21: S. W. Wilson. Generalization in the XCS classifier system. In Genetic Programming 1998: Proceedings of the Third Annual Conference, pages 665--674. Morgan Kaufmann, 1998.
• 22: Stewart W. Wilson, Get Real! XCS with Continuous-Valued Inputs, Learning Classifier Systems, From Foundations to Applications, p.209-222, January 2000
• 23: Stewart W. Wilson, Mining Oblique Data with XCS, Revised Papers from the Third International Workshop on Advances in Learning Classifier Systems, p.158-176, September 15-16, 2000

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Self-modifying machines (e.g., neural networks)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

General Terms:
Algorithms, Performance

Keywords:
LCS, RL, XCS, matching