Classifier systems that compute action mappings

ABSTRACT

The learning in a niche based learning classifier system depends both on the complexity of the problem space and on the number of available actions. In this paper, we introduce a version of XCS with computed actions, briefly XCSCA, that can be applied to problems involving a large number of actions. We report experimental results showing that XCSCA can evolve accurate and compact representations of binary functions which would be challenging for typical learning classifier system models.

REFERENCES

• 1: Manu Ahluwalia and Larry Bull. A genetic programming-based classifier system. In Wolfgang Banzhaf et al., editor, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-99) pages 11--18. Morgan Kaufmann, 1999.
• 2: Ester Bernadó-Mansilla , Josep M. Garrell-Guiu, Accuracy-based learning classifier systems: models, analysis and applications to classification tasks, Evolutionary Computation, v.11 n.3, p.209-238, Fall 2003 [doi>10.1162/106365603322365289]
• 3: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 4: Leo Breiman, Random Forests, Machine Learning, v.45 n.1, p.5-32, October 1 2001 [doi>10.1023/A:1010933404324]
• 5: Martin Butz, David G. Goldberg, and Pier Luca Lanzi. Bounding learning time in XCS. In Genetic and Evolutionary Computation - GECCO-2004 LNCS, 2004. Springer-Verlag.
• 6: Martin Butz, David G. Goldberg, Pier Luca Lanzi, and Kumara Sastry. Bounding the population size to ensure niche support in XCS. Technical Report 2004033, Illinois Genetic Algorithms Laboratory. University of Illinois at Urbana-Champaign, IL 61801, February 2004.
• 7: Martin V. Butz. Anticipatory Learning Classifier Systems volume 4 of Genetic Algorithms and Evolutionary Computation Springer-Verlag, 2000.
• 8: 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]
• 9: Martin V. Butz , Kumara Sastry , David E. Goldberg, Strong, Stable, and Reliable Fitness Pressure in XCS due to Tournament Selection, Genetic Programming and Evolvable Machines, v.6 n.1, p.53-77, March 2005 [doi>10.1007/s10710-005-7619-9]
• 10: Martin V. Butz and Stewart W. Wilson. An algorithmic description of xcs. Journal of Soft Computing 6(3 . 4):144--153, 2002.
• 11: Simon Haykin, Neural Networks: A Comprehensive Foundation, Prentice Hall PTR, Upper Saddle River, NJ, 1998
• 12: J. H. Holland. Escaping brittleness:The possibilities of general purpose learning algorithms applied to parallel rule-based systems. In R. S. Michalski et al., editors, Machine Learning, An Artificial Intelligence Approach volume 2, chapter 20, pages 593--623. Morgan Kaufmann, Los Altos, CA, 1986.
• 13: Pier Luca Lanzi. An Analysis of Generalization in the XCS Classifier System. Evolutionary Computation Journal 7(2):125--149, 1999.
• 14: Pier Luca Lanzi, Daniele Loiacono, Stewart W. Wilson, and David E. Goldberg. XCS with computed prediction for the learning of boolean functions. In Proceedings of the IEEE Congress on Evolutionary Computation - CEC-2005 pages 588--595, 2005. IEEE.
• 15: Drew Mellor, A first order logic classifier system, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068318]
• 16: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 17: Toby O'Hara and Larry Bull. Accuracy-based neuro and neuro-fuzzy classifier systems. Technical Report UWELCSG02-001, University of West England., 2002.
• 18: Toby O 'Hara and Larry Bull. Building anticipations in an accuracy-based learning classifier system by use of an artificial neural network. In IEEE Press, editor, IEEE Congress on Evolutionary Computation pages 2046--2052, 2005.
• 19: F. Rosenblatt. Principles of Neurodynamics Spartan Books, New York, 1962.
• 20: Stewart W. Wilson. ZCS: A zeroth level classifier system. Evolutionary Computation 2(1):1--18, 1994. http://prediction-dynamics. com/.
• 21: Stewart W. Wilson. Classi . er Fitness Based on Accuracy. Evolutionary Computation 3(2):149--175, 1995. http://prediction-dynamics. com/.
• 22: Stewart W. Wilson. Generalization in the XCS classifier system. In Genetic Programming 1998: Proceedings of the Third Annual Conference pages 665--674. Morgan Kaufmann, 1998.
• 23: Stewart W. Wilson. Function approximation with a classifier system. In Lee Spector et al., editor, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001) pages 974--981, San Francisco, California, USA, 7-11 July 2001. Morgan Kaufmann.
• 24: 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
• 25: Stewart W. Wilson, Classifiers that approximate functions, Natural Computing: an international journal, v.1 n.2-3, p.211-234, June 2002 [doi>10.1023/A:1016535925043]
• 26: Stewart W. Wilson. Three architectures for continuous action. Technical Report 2006019, Illinois Genetic Algorithms Laboratory. University of Illinois at Urbana-Champaign, 2006.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

General Terms:
Algorithms, Performance

Keywords:
LCS, XCS, action mappings