Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Soft Computing
Published in: Soft Computing 6/2015

01-06-2015 | Methodologies and Application

Learning classifier systems with memory condition to solve non-Markov problems

Authors: Zhaoxiang Zang, Dehua Li, Junying Wang

Published in: Soft Computing | Issue 6/2015

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In the family of learning classifier systems, the classifier system XCS has been successfully used for many applications. However, the standard XCS has no memory mechanism and can only learn optimal policy in Markov environments, but fails in non-Markov ones. In this work, we aim to develop a new classifier system based on XCS to tackle this problem. It adds a memory list with numbered slots to XCS to record input sensation history, and extends only a small number of classifiers with memory conditions. The classifier’s memory condition, as a foothold to disambiguate non-Markov states, is used to sense a specified element in the memory list, which makes our system can “jump over” irrelevant or confusing states to get decisive prior information that may be far back in time. Besides, a detection method is employed to recognize non-Markov states in environments, to avoid these states controlling over classifiers’ memory conditions. Furthermore, four sets of different complex maze environments have been tested by the proposed method. Experimental results show that our system can overcome the overhead problem often encountered in history-window approaches, and is an effective technique to solve non-Markov environments.
previous article Effect of simple ensemble methods on protein secondary structure prediction
next article A comparative study of evolving fuzzy grammar and machine learning techniques for text categorization

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
The more explanations will be given in Sect. 4.
 
2
The variable \(s_t \) is added to highlight system prediction is dependent on the current input \(s_t \) since the match set [\(M\)] is determined by \(s_t \). This will provide convenience for later use.
 
3
To refer to one of the attributes of a classifier \(cl\), we use the dot notation. For example, \(cl.mp\) is used to refer to \(mp\) of \(cl\).
 
Literature
Bagnall AJ, Zatuchna ZV (2005) On the classification of maze problems. In: Bull L, Kovacs T (eds) Foundations of learning classifier systems. Studies in fuzziness and soft computing, vol 183. Springer, Heidelberg, pp 307–316
Browne W, Scott D (2005) An abstraction algorithm for genetics-based reinforcement learning. In: Beyer H (ed) GECCO 2005: genetic and evolutionary computation conference, vol 2. ACM Press, Washington, DC, pp 1875–1882
Bull L, Hurst J (2003) A neural learning classifier system with self-adaptive constructivism. In: Proceedings of the 2003 congress on evolutionary computation, CEC ’03, vol 2. IEEE Press, pp 991–997
Butz MV (2003) Documentation of XCS+ts c-code 1.2. Illinois Genetic Algorithm Laboratory (IlliGAL), University of Illinois at Urbana-Champaign
Butz MV, Kovacs T, Lanzi PL, Wilson SW (2001) How XCS evolves accurate classifiers. In: Spector L, Goodman ED, Wu A (eds) GECCO-2001: Proceedings of the genetic and evolutionary computation conference. Morgan Kaufmann, Waltham, pp 927–934
Butz MV, Wilson SW (2002) An algorithmic description of XCS. Soft Comput 6(3–4):144–153CrossRefMATH
Cliff D, Ross S (1994) Adding temporary memory to ZCS. Adapt Behav 3(2):101–150CrossRef
Gilles E, Mathias P (2008) Adapted Pittsburgh classifier system: building accurate strategies in non Markovian environments. In: Proceedings of the 2008 GECCO conference companion on genetic and evolutionary computation. ACM, Atlanta, GA, USA, pp 2001–2008. doi:10.​1145/​1388969.​1389013
Gilles É, Mathias P (2010) Building accurate strategies in non Markovian environments without memory. In: Proceedings of learning classifier systems: 11th international workshop, IWLCS 2008, Atlanta, GA, USA, July 13, 2008, and 12th international workshop, IWLCS 2009, Montreal, QC, Canada, July 9, 2009, revised selected papers. Springer, Berlin, pp 107–126
Goldberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley Publishing Company Inc, ReadingMATH
Hamzeh A, Hashemi S, Sami A, Rahmani A (2009) A recursive classifier system for partially observable environments. Fundamenta Informaticae 97(1):15–40
Hamzeh A, Rahmani A (2008) A new architecture for learning classifier systems to solve POMDP problems. Fundamenta Informaticae 84(3):329–351MATHMathSciNet
Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor
Iqbal M, Browne WN, Zhang M (2012) Extracting and using building blocks of knowledge in learning classifier systems. In: Soule T, Moore JH (eds) Proceedings of the fourteenth international conference on genetic and evolutionary computation conference. GECCO ’12. ACM, Philadelphia, PA, USA, pp 863–870
Kaelbling LP, Littman M, Moore A (1996) Reinforcement learning: a survey. J Artif Intell Res 4(1):237–285
Kovacs T (2000) Towards a theory of strong overgeneral classifiers. In: Martin W, Spears WM (eds) Foundations of genetic algorithms (FOGA), vol 6. Morgan Kaufmann, San Francisco, pp 165–184
Landau S, Sigaud O (2008) A comparison between ATNoSFERES and learning classifier systems on non-Markov problems. Inf Sci 178(23):4482–4500CrossRef
Lanzi PL (1998a) Adding memory to XCS. In: Proceedings of the IEEE conference on evolutionary computation (ICEC98). IEEE Press, Anchorage, AK, USA, pp 609–614
Lanzi PL (1998b) An analysis of the memory mechanism of XCSM. In: Koza JR, Banzhaf W, Chellapilla K (eds) Genetic programming 1998: Proceedings of the third annual conference. Morgan Kaufmann, University of Wisconsin, Madison, Wisconsin, USA, pp 643–651
Lanzi PL (1999) An analysis of generalization in the XCS classifier system. Evol Comput 7(2):125–149CrossRef
Lanzi PL (2002) Learning classifier systems from a reinforcement learning perspective. Soft Comput 6(3–4):162–170CrossRefMATH
Lanzi PL, Wilson SW (2000) Toward optimal classifier system performance in non-Markov environments. Evol Comput 8(4):393–418CrossRef
Liepins GE, Hilliard MR, Palmer M, Rangarajan G (1991) Credit assignment and discovery in classifier systems. Int J Intell Syst 6(1):55–69CrossRef
Littman ML (1993) An optimization-based categorization of reinforcement learning environments. From animals to animats 2 : simulation of adaptive behavior. MIT Press, Honolulu, Hawai, USA, pp 262–270
Littman ML, Cassandra AR, Kaelbling LP (1995) Learning policies for partially observable environments: scaling up. Machine learning: Proceedings of the twelfth international conference on machine learning. Morgan Kaufmann Publishers Inc., Tahoe City, California, pp 362–370
Mccallum RA (1993) Overcoming incomplete perception with utile distinction memory. Proceedings of the tenth international conference on machine learning. Morgan Kaufmann, Amherst, pp 190–196
Mccallum RA (1996) Hidden state and reinforcement learning with instance-based state identification. Proc IEEE Trans Syst Man Cybern Part B 26(3):464–473 Special issue on learning autonomous robotsCrossRef
Métivier M, Lattaud C (2003) Anticipatory classifier system using behavioral sequences in non-Markov environments. In: Proceedings of learning classifier systems: 5th international workshop, IWLCS, (2002) vol 2661. Springer, New York, pp 143–162
Moioli RC, Vargas PA, Zuben FJV (2008) Analysing learning classifier systems in reactive and non-reactive robotic tasks. In: Bacardit J, Bernadó-Mansilla E, Butz MV, Kovacs T, Llorà X, Takadama K (eds) Learning classifier systems, vol 4998. Springer, New York, pp 286–305
Preen R, Bull L (2009) Discrete dynamical genetic programming in XCS. In: Proceedings of the 11th annual conference on genetic and evolutionary computation, GECCO ’09. ACM, New York, USA, pp 1299–1306
Sigaud O, Wilson S (2007) Learning classifier systems: a survey. Soft Comput 11(11):1065–1078CrossRefMATH
Smith RE (1994) Memory exploitation in learning classifier systems. Evol Comput 2(3):199–220CrossRef
Stolzmann W (1999) Latent learning in Khepera robots with anticipatory classifier systems. In: Wu A (ed) Proceedings of the 1999 genetic and evolutionary computation conference workshop. Morgan Kaufmann, San Francisco, California, pp 290–297
Stolzmann W (2000) An introduction to anticipatory classifier systems. In: Lanzi P, Stolzmann W, Wilson SE (eds) Learning classifier systems: from foundations to applications, Lecture notes in artificial intelligence, vol 1813. Springer, Berlin, pp 175–194
Tomlinson A, Bull L (1999) A zeroth level corporate classifier system. In: Banzhaf W, Daida J, Eiben AE et al (eds) Proceedings of the genetic and evolutionary computation conference (GECCO’99). Morgan Kaufmann, San Francisco, pp 306–313
Tomlinson A, Bull L (2002) An accuracy-based corporate classifier system. Soft Comput 6(3):200–215CrossRefMATH
Widrow B, Hoff ME (1988) Adaptive switching circuits. Neurocomputing: foundations of research. MIT Press, Cambridge, pp 123–134
Wilson SW (1991) The Animat path to AI. In: Meyer JA, Wilson SW (eds) From animals to animats 1: Proceedings of the first International conference on simulation of adaptive behavior (SAB90). MIT Press/Bradford Books, Cambridge, MA, pp 15–21
Wilson SW (1994) ZCS: a zeroth level classifier system. Evol Comput 2(1):1–18CrossRef
Wilson SW (1995) Classifier fitness based on accuracy. Evol Comput 3(2):149–175CrossRef
Wilson SW (1998) Generalization in the XCS classifier system. In: Koza JR, Banzhaf W, Chellapilla K et al (eds) Proceedings of the third annual genetic programming conference. Morgan Kaufmann, San Francisco, pp 665–674
Wilson SW, Goldberg DE (1989) A critical review of classifier systems. In: Schaffer JD (ed) Proceedings of the 3rd international conference on genetic algorithms. Morgan Kaufmann, San Francisco, pp 244–255
Zatuchna ZV (2005) AgentP: a learning classifier system with associative perception in maze environments, PhD, School of Computing Sciences, University of East Anglia (UEA), Norwich, England
Metadata
Title
Learning classifier systems with memory condition to solve non-Markov problems
Authors
Zhaoxiang Zang
Dehua Li
Junying Wang
Publication date
01-06-2015
Publisher
Springer Berlin Heidelberg
Published in
Soft Computing / Issue 6/2015
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-014-1357-y

Other articles of this Issue 6/2015

Soft Computing 6/2015 Go to the issue

Methodologies and Application

Uncertain random multilevel programming with application to production control problem

Methodologies and Application

Schedule length and reliability-oriented multi-objective scheduling for distributed computing

Focus

Applications and design of cooperative multi-agent ARN-based systems

Focus

Self-adjusting harmony search-based feature selection

Methodologies and Application

Effect of simple ensemble methods on protein secondary structure prediction

Methodologies and Application

Unsupervised nearest neighbor regression for dimensionality reduction

Premium Partner

    Image Credits