Abstract
Despite two decades of work learning classifier systems researchers have had relatively little to say on the subject of what makes a problem difficult for a classifier system. Wilson’s accuracy-based XCS, a promising and increasingly popular classifier system, is, we feel, the natural first choice of classifier system with which to address this issue. To make the task more tractable we limit our considerations to a restricted, but very important, class of problems. Most significantly, we consider only single step reinforcement learning problems and the use of the standard binary/ternary classifier systems language. In addition to distinguishing several dimensions of problem complexity for XCS, we consider their interactions, identify bounding cases of difficulty, and consider complexity metrics for XCS. Based on these results we suggest a simple template for ternary single step test suites to more comprehensively evaluate classifier systems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Goldberg, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, 1989.
Kovacs, T. Evolving Optimal Populations with XCS Classifier Systems. MSc Thesis, University of Birmingham. Also Technical Report CSR-96-17 and CSRP-96-17, School of Computer Science, University of Birmingham, Birmingham, U.K., 1996.
Kovacs, T. Steady State Deletion Techniques in a Classifier System. Unpublished PhD report, 1997.
Kovacs, T. XCS Classifier System Reliably Evolves Accurate, Complete, and Minimal Representations for Boolean Functions. In Roy, Chawdhry, and Pant, editors, Soft Computing in Engineering Design and Manufacturing, pages 59–68. Springer-Verlag, 1997.
Kovacs, T. Deletion schemes for classifier systems. In W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith, editors, GECCO-99: Proceedings of the Genetic and Evolutionary Computation Conference, pages 329–336. Morgan Kaufmann, 1999.
Kovacs, T. Strength or Accuracy? Fitness Calculation in Learning Classifier Systems. In P. L. Lanzi, W. Stolzmann, and S. W. Wilson, editors, Learning Classifier Systems: An Introduction to Contemporary Research, pages 143–160. Springer-Verlag, 2000.
Lanzi, P. L. A Study of the Generalization Capabilities of XCS. In Thomas Bäck, editor, Proceedings Seventh International Conference on Genetic Algorithms (ICGA-7), pages 418–425. Morgan Kaufmann, 1997.
Lanzi, P. L. Generalization in Wilson’s XCS. In A. E. Eiben, T. Bäck, M. Shoenauer, and H.-P. Schwefel, editors, Proceedings of the Fifth International Conference on Parallel Problem Solving From Nature, number 1498 in LNCS. Springer-Verlag, 1998.
Li, M. and Vitányi, P. An Introduction to Kolmogorov Complexity and Its Applications. 2nd edition. Springer-Verlag, 1997.
Wilson, S. W. Classifier fitness based on accuracy. Evolutionary Computation, 3(2):149–175, 1995.
Wilson, S. W. Generalization in the XCS classifier system. In J. Koza et al., editors, Genetic Programming 1998: Proceedings of the Third Annual Conference, pages 665–674. Morgan Kaufmann, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kovacs, T., Kerber, M. (2001). What Makes a Problem Hard for XCS?. In: Luca Lanzi, P., Stolzmann, W., Wilson, S.W. (eds) Advances in Learning Classifier Systems. IWLCS 2000. Lecture Notes in Computer Science(), vol 1996. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44640-0_7
Download citation
DOI: https://doi.org/10.1007/3-540-44640-0_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42437-6
Online ISBN: 978-3-540-44640-8
eBook Packages: Springer Book Archive