XCS Cannot Learn All Boolean Functions

Charalambos Ioannides, Geoff Barrett, Kerstin Eder

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

19 Citations (Scopus)


In this paper we applied the eXtended Classifier System (XCS) on a novel real world problem, namely digital Design Verification (DV). We witnessed the inadequacy of XCS on binary problems that contain high overlap between optimal rules especially when the focus is on population and not system level performance. The literature attempts to underplay the importance of the aforementioned weakness and in short, supports that a) XCS can potentially learn any Boolean function given enough resources are allocated (right parameters used) and b) the main metric deciding the learning difficulty of a Boolean function is the amount of classifiers required to represent it (i.e. |[O]|). With this work we experimentally refuted the aforementioned propositions and as a result of the work, we introduce new insights on the behavior of XCS when solving two-valued Boolean functions using a binary reward scheme (1000/0). We also introduce a new population metric (%[EPI]) that should necessarily be used to guide future research on improving XCS performance on the aforementioned problems.
Translated title of the contributionXCS Cannot Learn All Boolean Functions
Original languageEnglish
Title of host publication13th Annual Genetic and Evolutionary Computation Conference (GECCO)
PublisherAssociation for Computing Machinery (ACM)
ISBN (Print)978-1-4503-0557-0
Publication statusPublished - Jul 2011

Bibliographical note

Other page information: tbc-
Conference Proceedings/Title of Journal: Genetic and Evolutionary Computation Conference (GECCO)
Other identifier: 2001387


Dive into the research topics of 'XCS Cannot Learn All Boolean Functions'. Together they form a unique fingerprint.

Cite this