Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Learning complex, overlapping and niche imbalance Boolean problems using XCS-based classifier systems

  • Research Paper
  • Published:
Evolutionary Intelligence Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

XCS is an accuracy-based learning classifier system, which has been successfully applied to learn various classification and function approximation problems. Recently, it has been reported that XCS cannot learn overlapping and niche imbalance problems using the typical experimental setup. This paper describes two approaches to learn these complex problems: firstly, tune the parameters and adjust the methods of standard XCS specifically for such problems. Secondly, apply an advanced variation of XCS. Specifically, we developed previously an XCS with code-fragment actions, named XCSCFA, which has a more flexible genetic programming like encoding and explicit state-action mapping through computed actions. This approach is examined and compared with standard XCS on six complex Boolean datasets, which include overlapping and niche imbalance problems. The results indicate that to learn overlapping and niche imbalance problems using XCS, it is beneficial to either deactivate action set subsumption or use a relatively high subsumption threshold and a small error threshold. The XCSCFA approach successfully solved the tested complex, overlapping and niche imbalance problems without parameter tuning, because of the rich alphabet, inconsistent actions and especially the redundancy provided by the code-fragment actions. The major contribution of the work presented here is overcoming the identified problem in the wide-spread XCS technique.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. For a detailed review of different types and approaches in LCS refer to [36, 48].

  2. UCS (sUpervised Classifier System) [5] is a variant of XCS, which is specifically designed for supervised learning problems.

  3. This work is an extension of our previous work on XCSCFA published in [25, 27].

  4. Here, * can be 0, 1, or #.

  5. They also used a larger value for action set subsumption threshold, i.e. 100 instead of the commonly used value of 20.

  6. These methods need larger population size to solve even-parity problems.

References

  1. Ahluwalia M, Bull L (1999) A genetic programming based classifier System. In proceedings of the genetic and evolutionary computation conference, pp 11–18

  2. Alfaro-Cid E, Merelo JJ, de Vega FF, Esparcia-Alcázar AI, Sharman K (2010) Bloat control operators and diversity in genetic programming: a comparative study. Evol Comput 18(2):305–332

    Article  Google Scholar 

  3. Behdad M, Barone L, French T, Bennamoun M (2012) On XCSR for electronic fraud detection. Evol Intell 5(2):139–150

    Article  Google Scholar 

  4. Behdad M, French T, Barone L, Bennamoun M (2012) On principal component analysis for high-dimensional XCSR. Evol Intell 5(2):129–138

    Article  Google Scholar 

  5. Bernadó-Mansilla E, Garrell-Guiu JM (2003) Accuracy-based learning classifier systems: models, analysis and applications to classification tasks. Evol Comput 11(3):209–238

    Article  Google Scholar 

  6. Brameier M, Banzhaf W (2007) Linear genetic programming. Springer, New York

  7. Bull L (2004) Applications of learning classifier systems. Springer, New York

  8. Bull L, Kovacs T (2005) Foundations of learning classifier systems: an introduction. Springer, New York

  9. Bull L, O’Hara T (2002) Accuracy-based neuro and neuro-fuzzy classifier systems. In proceedings of the genetic and evolutionary computation conference, pp 905–911

  10. Butz MV (2006) Rule-based evolutionary online learning systems: a principal approach to LCS analysis and design. Springer, New York

  11. Butz MV, Goldberg DE, Lanzi PL (2007) Effect of pure error-based fitness in XCS. In learning classifier systems, vol 4399. Springer, New York, pp 104–114

  12. Butz MV, Goldberg DE, Tharakunnel K (2003) Analysis and improvement of fitness exploitation in XCS: bounding models, tournament selection, and bilateral accuracy. Evol Comput 11(3):239–277

    Article  Google Scholar 

  13. Butz MV, Kovacs T, Lanzi PL, Wilson SW (2004) Toward a theory of generalization and learning in XCS. IEEE Trans Evol Comput 8(1):28–46

    Article  Google Scholar 

  14. Butz MV, Wilson SW (2002) An algorithmic description of XCS. Soft Comput 6(3-4):144–153

    Article  MATH  Google Scholar 

  15. Dam HH, Abbass HA, Lokan C, Yao X (2008) Neural-based learning classifier systems. IEEE Trans Knowl Data Eng 20(1):26–39

    Article  Google Scholar 

  16. Dandamudi SP (2003) Fundamentals of computer organization and design. Springer, New York

  17. Franco MA, Krasnogor N, Bacardit J (2012) Analysing BioHEL using challenging Boolean functions. Evol Intell 5(2):87–102

    Article  Google Scholar 

  18. Goldberg DE, Korb B, Deb K (1989) Messy genetic algorithms: motivation, analysis, and first results. Complex Syst 3(5):493–530

    MathSciNet  MATH  Google Scholar 

  19. Holland JH, Booker LB, Colombetti M, Dorigo M, Goldberg DE, Forrest S, Riolo RL, Smith RE, Lanzi PL, Stolzmann W, Wilson SW (2000) What is a learning classifier system? In learning classifier systems, from foundations to applications. Springer, New York, pp 3–32

  20. Hurst J, Bull L (2006) A neural learning classifier system with self-adaptive constructivism for mobile robot control. Artif Life 12(3):353–380

    Article  Google Scholar 

  21. Ioannides C, Barrett G, Eder K (2011) Improving XCS performance on overlapping binary problems. In proceedings of the IEEE congress on evolutionary computation, pp 1420–1427

  22. Ioannides C, Barrett G, Eder K (2011) XCS Cannot learn all Boolean functions. In proceedings of the genetic and evolutionary computation conference, pp 1283–1290

  23. Iqbal M, Browne WN, Zhang M (2012) Extracting and using building blocks of knowledge in learning classifier systems. In proceedings of the genetic and evolutionary computation conference, pp 863–870

  24. Iqbal M, Browne WN, Zhang M (2012) XCSR with computed continuous Action. In proceedings of the Australasian joint conference on artificial intelligence, pp 350–361

  25. Iqbal M, Browne WN, Zhang M (2013) Comparison of two methods for computing action values in XCS with code-fragment actions. In proceedings of the genetic and evolutionary computation conference (companion), pp 1235–1242

  26. Iqbal M, Browne WN, Zhang M (2013) Evolving optimum populations with XCS classifier systems. Soft Comput 17(3):503–518

    Article  Google Scholar 

  27. Iqbal M, Browne WN, Zhang M (2013) Learning overlapping natured and niche imbalance Boolean problems using XCS classifier systems. In proceedings of the IEEE congress on evolutionary computation, pp 825

  28. Iqbal M, Browne WN, Zhang M (2013) Using building blocks of extracted knowledge to solve complex, large-scale Boolean problems. IEEE transactions on evolutionary computation. (to appear)

  29. Iqbal M, Zhang M, Browne WN (2011) Automatically defined functions for learning classifier systems. In proceedings of the genetic and evolutionary computation conference (companion), pp 375–382

  30. De Jong KA (2006) Evolutionary computation: a unified approach. The MIT Press, Cambridge

  31. Kinzett D, Johnston M, Zhang M (2009) Numerical simplification for bloat control and analysis of building blocks in genetic programming. Evol Intell 2(4):151–168

    Article  Google Scholar 

  32. Kovacs T (1996) Evolving optimal populations with XCS classifier systems. Technical report CSR-96-17 and CSRP-9617, University of Birmingham, UK

  33. Kovacs T (2002) What should a classifier system learn and how should we measure it? Soft Comput 6(3–4):171–182

    Article  MATH  Google Scholar 

  34. Lanzi PL (1999) Extending the representation of classifier conditions part I: from binary to messy coding. In proceedings of the genetic and evolutionary computation conference, pp 337–344

  35. Lanzi PL (2003) XCS with stack-based genetic programming. In proceedings of the IEEE congress on evolutionary computation, pp 1186–1191

  36. Lanzi PL (2008) Learning classifier systems: then and now. Evol Intell 1(1):63–82

    Article  Google Scholar 

  37. Lanzi PL, Loiacono D (2007) Classifier systems that compute action mappings. In proceedings of the genetic and evolutionary computation conference, pp 1822–1829

  38. Lanzi PL, Loiacono D, Wilson SW, Goldberg DE (2005) XCS with computed prediction for the learning of Boolean functions. Technical Report 2005007, Illinois Genetic Algorithms Laboratory

  39. Lanzi PL, Loiacono D, Wilson SW, Goldberg DE (2007) Generalization in the XCSF classifier system: analysis, improvement, and extension. Evol Comput 15(2):133–168

    Article  Google Scholar 

  40. Lanzi PL, Perrucci A (1999) Extending the representation of classifier conditions part II: from messy coding to S-expressions. In proceedings of the genetic and evolutionary computation conference, pp 345–352

  41. Loiacono D, Marelli A, Lanzi PL (2007) Support vector machines for computing action mappings in learning classifier systems. In proceedings of the IEEE congress on evolutionary computation, pp 2141–2148

  42. Luke S, Panait L (2006) A comparison of bloat control methods for genetic programming. Evol Comput 14(3):309–344

    Article  Google Scholar 

  43. Miller JF, Smith SL (2006) Redundancy and computational efficiency in cartesian genetic programming. IEEE Trans Evol Comput 10(2):167–174

    Article  Google Scholar 

  44. Miller JF, Thomson P (2000) Cartesian genetic programming. In proceedings of the European conference on genetic programming, pp 121–132

  45. Poli R, Langdon WB, McPhee NF (2008) A field guide to genetic programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk. (With contributions by Koza JR)

  46. Shafi K, Kovacs T, Abbass HA, Zhu W (2009) Intrusion detection with evolutionary learning classifier systems. Nat Comput 8(1):3–27

    Article  MathSciNet  MATH  Google Scholar 

  47. Stalph PO, Rubinsztajn J, Sigaud O, Butz MV (2012) Function approximation with LWPR and XCSF: a comparative study. Evol Intell 5(2):103–116

    Article  Google Scholar 

  48. Urbanowicz RJ, Moore JH (2009) Learning classifier systems: a complete introduction, review, and roadmap. J Artif Evol Appl 2009(1):1–25

    Article  Google Scholar 

  49. Vijayakumar S, Schaal S (2000) Locally weighted projection regression: an o(n) algorithm for incremental real time learning in high dimensional space. In proceedings of the international conference on machine learning, pp 1079–1086

  50. Wilson SW (1994) ZCS: A zeroth level classifier system. Evol Comput 2(1):1–18

    Article  Google Scholar 

  51. Wilson SW (1995) Classifier fitness based on accuracy. Evol Comput (2):149–175

    Article  Google Scholar 

  52. Wilson SW (1998) Generalization in the XCS classifier system. In proceedings of the genetic programming conference, pp 65–674

  53. Wilson SW (2000) Get real! XCS with continuous-valued inputs. In learning classifier systems. Springer, New York, pp 209–219

  54. Wilson SW (2000) Mining oblique data with XCS. In proceedings of the genetic and evolutionary computation conference (companion), pp 158–174

  55. Wilson SW (2002) Classifiers that approximate functions. Nat Comput 1:211–233

    Google Scholar 

  56. Wilson SW (2008) Classifier conditions using gene expression programming. In learning classifier systems, Springer, New York, pp 206–217

  57. Wong P, Zhang M (2006) Algebraic simplification of GP programs during evolution. In proceedings of the genetic and evolutionary computation conference, pp 927–934

Download references

Author information

Authors and Affiliations

  1. Evolutionary Computation Research Group, School of Engineering and Computer Science, Victoria University of Wellington, PO Box 600, Wellington, 6140, New Zealand

    Muhammad Iqbal, Will N. Browne & Mengjie Zhang

Authors
  1. Muhammad Iqbal
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Will N. Browne
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mengjie Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Muhammad Iqbal.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Iqbal, M., Browne, W.N. & Zhang, M. Learning complex, overlapping and niche imbalance Boolean problems using XCS-based classifier systems. Evol. Intel. 6, 73–91 (2013). https://doi.org/10.1007/s12065-013-0091-1

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12065-013-0091-1

Keywords

Search

Navigation