What Makes a Problem Hard for XCS?

Tim Kovacs, Lanzi P. L., Kerber Manfred, Stolzmann W., Wilson S. W.

Research output: Chapter in Book/Report/Conference proceedingChapter in a book


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.
Translated title of the contributionWhat Makes a Problem Hard for XCS?
Original languageEnglish
Title of host publicationAdvances in Learning Classifier Systems
Publication statusPublished - 2001

Bibliographical note

Other page information: 80-99
Other identifier: 1000606


Dive into the research topics of 'What Makes a Problem Hard for XCS?'. Together they form a unique fingerprint.

Cite this