XCS Cannot Learn All Boolean FunctionsCharalambos Ioannides, Geoff Barrett, Kerstin Eder, XCS Cannot Learn All Boolean Functions. 13th Annual Genetic and Evolutionary Computation Conference (GECCO). ISBN 978-1-4503-0557-0, pp. 1283–1290. July 2011. No electronic version available.
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.