Charalambos Ioannides
Kerstin Eder
ABSTRACT
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.
- A. Piziali, Functional verification coverage measurement and analysis. Berlin: Springer, 2007. Google Scholar
Digital Library
- S. W. Wilson, "Classifier Fitness Based on Accuracy," Evolutionary Computation, vol. 3, no. 2, pp. 149--175, 1995. Google ScholarDigital Library
- T. Kovacs, "What Should a Classifier System Learn?," Evolutionary Computation, vol. 2, pp. 775 - 782, 2001.Google Scholar
- T. Kovacs, "Strength or Accuracy? Fitness Calculation in Learning Classifier Systems," in Learning Classifier Systems, From Foundations to Applications, London, UK, 2000, p. 143--160. Google ScholarDigital Library
- M. V. Butz, Rule-Based Evolutionary Online Learning Systems: A Principled Approach to LCS Analysis and Design, 1st ed. Springer, 2005.Google Scholar
- R. J. Urbanowicz and J. H. Moore, "Learning classifier systems: a complete introduction, review, and roadmap," J. Artif. Evol. App., vol. 2009, p. 1:1--1:25, 2009. Google ScholarCross Ref
- T. Kovacs, "A Comparison of Strength and Accuracy-Based Fitness in Learning Classifier Systems," PhD thesis, University of Birmingham, 2001.Google Scholar
- P. L. Lanzi and D. Loiacono, XCSLib: The XCS Classifier System Library. Illinois Genetic Algorithms Lab: University of Illinois, 2009.Google Scholar
- T. Kovacs, "XCS Classifier System Reliably Evolves Accurate, Complete, and Minimal Representations for Boolean Functions," in Soft Computing in Engineering Design and Manufacturing, Springer, 1997, pp. 59--68.Google Scholar
- W. V. Quine, "The Problem of Simplifying Truth Functions," The American Mathematical Monthly, vol. 59, no. 8, pp. 521--531, Oct. 1952.Google ScholarCross Ref
- T. Kovacs, "Performance and population state metrics for rule-based learning systems," in Proceedings of the Evolutionary Computation on 2002. CEC '02. Proceedings of the 2002 Congress - Volume 02, Washington, DC, USA, 2002, p. 1781--1786. Google ScholarDigital Library
- T. Kovacs and M. Kerber, "What Makes a Problem Hard for XCS?," in Revised Papers from the Third International Workshop on Advances in Learning Classifier Systems, London, UK, 2001, p. 80--102. Google ScholarDigital Library
- N. UFRGS Research Lab, "KARMA3."{Online}. Available: http://www.inf.ufrgs.br/logics/docman/karma/. {Accessed: 01-Jul-2011}.Google Scholar
- M. V. Butz, D. E. Goldberg, and K. Tharakunnel, "Analysis and improvement of fitness exploitation in XCS: bounding models, tournament selection, and bilateral accuracy," Evolutionary Computation, vol. 11, no. 3, pp. 239--277, 2003. Google ScholarDigital Library
- M. V. Butz, D. E. Goldberg, P. L. Lanzi, and K. Sastry, "Problem solution sustenance in XCS: Markov chain analysis of niche support distributions and the impact on computational complexity," Genetic Programming and Evolvable Machines, vol. 8, p. 5--37, Mar. 2007. Google ScholarDigital Library
- M. V. Butz, D. E. Goldberg, and P. L. Lanzi, "Computational Complexity of the XCS Classifier System," in Foundations of Learning Classifier Systems, vol. 183, L. Bull and T. Kovacs, Eds. Springer Berlin / Heidelberg, 2005, pp. 914--914.Google Scholar
Index Terms
- XCS cannot learn all boolean functions
Recommendations
Studying XCS/BOA learning in Boolean functions: structure encoding and random Boolean functions
GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computationRecently, studies with the XCS classifier system on Boolean functions have shown that in certain types of functions simple crossover operators can lead to disruption and, consequently, a more effective recombination mechanism is required. Simple ...
Analysis and improvement of fitness exploitation in XCS: bounding models, tournament selection, and bilateral accuracy
The evolutionary learning mechanism in XCS strongly depends on its accuracy-based fitness approach. The approach is meant to result in an evolutionary drive from classifiers of low accuracy to those of high accuracy. Since, given inaccuracy, lower ...
XCS-CR: determining accuracy of classifier by its collective reward in action set toward environment with action noise
GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference CompanionAccuracy based Learning Classifier System (XCS) prefers to generalize the classifiers that always acquire the same reward, because they make accurate reward predictions. However, real-world problems have noise, which means that classifiers may not ...
Comments