Abstract
Learning classifier systems (LCSs) are rule- based systems that automatically build their ruleset. At the origin of Holland’s work, LCSs were seen as a model of the emergence of cognitive abilities thanks to adaptive mechanisms, particularly evolutionary processes. After a renewal of the field more focused on learning, LCSs are now considered as sequential decision problem-solving systems endowed with a generalization property. Indeed, from a Reinforcement Learning point of view, LCSs can be seen as learning systems building a compact representation of their problem thanks to generalization. More recently, LCSs have proved efficient at solving automatic classification tasks. The aim of the present contribution is to describe the state-of- the-art of LCSs, emphasizing recent developments, and focusing more on the sequential decision domain than on automatic classification.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Ahluwalia M, Bull L (1999) A genetic programming-based classifier system. In: Banzhaf W, Daida J, Eiben AE, Garzon MH, Honavar V, Jakiela M, Smith RE (eds) (1999) Proceedings of the 1999 genetic and evolutionary computation conference workshop program. Morgan Kaufmann, San Francisco, pp 11–18
Bacardit J, Garrell JM (2003) Evolving multiple discretizations with adaptive intervals for a Pittsburgh rule-based learning classifier system. In: Cantú-Paz E, Foster JA, Deb K, Davis D, Roy R, O’Reilly U-M, Beyer H-G, Standish R, Kendall G, Wilson S, Harman M, Wegener J, Dasgupta D, Potter MA, Schultz AC, Dowsland K, Jonoska N, Miller J (eds). Genetic and evolutionary computation—GECCO-2003. Springer, Berlin, pp. 1818–1831
Banzhaf W, Daida J, Eiben AE, Garzon MH, Honavar V, Jakiela M, Smith RE (eds) (1999) Proceedings of the 1999 genetic and evolutionary computation conference workshop program. Morgan Kaufmann, San Francisco
Bellman RE (1957) Dynamic programming. Princeton University Press, Princeton
Bellman RE (1961) Adaptive control processes: a guided tour. Princeton University Press, Princeton
Bernadó E, Llorà X, Garrel JM (2001) XCS and GALE: a comparative study of two learning classifer systems with six other learning algorithms on classification tasks. In: Lanzi P-L, Stolzmann W, Wilson SW (eds) Proceedings of the fourth international workshop on Learning Classifer Systems
Bertsekas DP (1995) Dynamic programming and optimal control. Athena Scientific, Belmont
Beyer H-G, O’Reilly U-M, Arnold D, Banzhaf W, Blum C, Bonabeau E, Cantú Paz E, Dasgupta D, Deb K, Foster J, de Jong E, Lipson H, Llora X, Mancoridis S, Pelikan M, Raidl G, Soule T, Tyrrell A, Watson J-P, Zitzler E (eds) (2005) Proceedings of the genetic and evolutionary computation conference, GECCO-2005. ACM, Washington
Booker L, Goldberg DE, Holland JH (1989) Classifier systems and genetic algorithms. Artif Intell 40(1–3):235–282
Booker LB (2000) Do we really need to estimate rule utilities in classifier systems?. In: Lanzi P-L, Stolzmann W, Wilson SW (eds). Learning classifier systems. From foundations to applications, vol. 1813 of Lecture Notes in Artificial Intelligence. Springer, Berlin, pp. 125–142
Boutilier C, Dearden R, Goldszmidt M (1995) Exploiting structure in policy construction. In: Proceedings of the fourteenth international joint conference on artificial intelligence (IJCAI-95), Montreal, pp 1104–1111
Boutilier C, Dearden R, Goldszmidt M (2000) Stochastic dynamic programming with factored representations. Artif Intell 121(1): 49–107
Bull L (1998) On ZCS in multi-agent environments. Lect Notes Comput Sci 1498:471–479
Bull L (1999) On using ZCS in a simulated continuous double-auction market. In: Banzhaf W, Daida J, Eiben AE, Garzon MH, Honavar V, Jakiela M, Smith RE (eds) Proceedings of the 1999 genetic and evolutionary computation conference workshop program. Morgan Kaufmann, San Francisco, pp. 83–90
Bull L (2004a) A simple payoff-based learning classifier system. In: Yao X, Burke E, Lozano JA, Smith J, Merelo-Guervós JJ, Bullinaria JA, Rowe J, Tino P, Kabán A, Schwefel H-P (eds). Proceedings of parallel problem solving from nature (PPSN VIII). Springer, Heidelberg
Bull L (ed) (2004b) Applications of learning classifier systems. Springer, Heidelberg
Bull L (2005) Two simple learning classifier systems. In: Bull L, Kovacs T (eds) Foundations of learning classifier systems. Springer, Heidelberg
Bull L, Hurst J (2002) ZCS redux. Evol Comput 10(2):185–205
Butz M, Kovacs T, Lanzi PL, Wilson SW (2004) Toward a theory of generalization and learning in xcs. IEEE Trans Evol Comput 8(1):28–46
Butz M, Pelikan M, Llorà X, Goldberg DE (2006) Automated global structure extraction for eeffective local building block processing in XCS. J Evol Comput (to appear)
Butz MV (2002) An algorithmic description of ACS2. In: Lanzi P-L, Stolzmann W, Wilson SW (eds) Advances in learning classifier systems, vol 2321 of Lecture Notes in Artificial Intelligence. Springer, Berlin, pp 211–229
Butz MV, Goldberg DE (2003) Generalized state values in an anticipatory Learning Classifier System. In Butz MV, Sigaud O, Gérard P (eds) LNAI 2684: anticipatory behavior in adaptive learning systems. Springer, Heidelberg, pp 281–301
Butz MV, Goldberg DE, Lanzi PL (2003a) Gradient descent methods in learning classifier systems: improving XCS performance in multistep problem. Technical report 2003028, IlliGAL
Butz MV, Goldberg DE, Stolzmann W (2000) Introducing a genetic generalization pressure to the Anticipatory Classifier Systems part I: Theoretical approach. In: Whitley LD, Goldberg DE, Cantú-Paz E, Spector L, Parmee IC, Beyer H-G (eds) (2000) Proceedings of the genetic and evolutionary computation conference (GECCO00). Morgan Kaufmann, San Francisco, pp 34–41. Also Technical Report 2000005 of the Illinois Genetic Algorithms Laboratory
Butz MV, Sastry K, Goldberg DE (2003b) Tournament selection: stable fitness pressure in XCS. In: Cantú-Paz E, Foster JA, Deb K, Davis D, Roy R, O’Reilly U-M, Beyer H-G, Standish R, Kendall G, Wilson S, Harman M, Wegener J, Dasgupta D, Potter MA, Schultz AC, Dowsland K, Jonoska N, Miller J (eds) Genetic and evolutionary computation—GECCO-2003, vol 2724 of LNCS. Springer, Berlin, pp 1857–1869
Butz MV, Wilson SW (2002) An algorithmic description of XCS. J Soft Comput 6(3–4):144–153
Cantu-Paz E, Foster JA, Deb K, O’Reilly U-M, Beyer H-G, Standish R, Kendall G, Wilson S, Harman M, Weneger J, Dasgupta D, Potter MA, Schultz AC, Dowsland KA, Jonoska N, Miller J (eds) (2003) Proceedings of the 2003 genetic and evolutionary computation conference workshop program, Chicago. Springer, Berlin
Cao YJ, Ireson N, Bull L, Miles R (1999) Design of a traffic junction controller using a classifier system and fuzzy logic. In Reusch B (ed) Proceedings of the sixth international conference on computational intelligence, theory and applications (6th fuzzy days), vol 1625 of LNCS. Springer, Berlin, pp 342–353
Cao YJ, Ireson N, Bull L, Miles R (2001) An evolutionary intelligent agents approach to traffic signal control. Int J Knowl based Intell Eng Syst 5(4):279–289
Cliff D, Ross S (1994) Adding memory to ZCS. Adapt Behav 3(2):101–150
Deb K, Poli R, Banzhaf W, Beyer H-G, Burke E, Darwen P, Dasgupta D, Floreano D, Foster JA, Harman M, Holland O, Lanzi P-L, Spector L, Tettamanzi A, Thierens D, Tyrrell A (eds) (2004) Proceedings of the 2004 genetic and evolutionary computation conference workshop program, Seattle. Springer, Berlin
Degris T, Sigaud O, Wuillemin P-H (2006a) Chi-square tests driven method for learning the structure of factored mdps. In: Proceedings of the 22nd uncertainty in artificial intelligence conference (UAI’2006). MIT, Massachussetts, pp 122–129
Degris T, Sigaud O, Wuillemin P-H (2006b) Learning the structure of factored markov decision processes in reinforcement learning problems. In: Proceedings of the 23rd international conference on machine learning (ICML’2006). CMU, Pensylvania, pp 257–264
Dorigo M, Bersini H (1994) A comparison of Q-learning and classifier systems. In: Cliff D, Husbands P, Meyer J-A, Wilson SW (eds) From animals to animats 3 MIT, Cambridge, pp 248– 255
Drugowitsch J, Barry A (2006) Towards convergence of learning classifier systems value iteration. Technical report CSBU-2006-03, Department of Computer Science, University of Bath
Gérard P, Meyer J-A, Sigaud O (2005) Combining latent learning with dynamic programming in MACS. Euro J Oper Res 160: 614–637
Gérard P, Sigaud O (2003) Designing efficient exploration with MACS: Modules and function approximation. In: Proceedings of the genetic and evolutionary computation conference 2003 (GECCO’03), Chicago. Springer, Berlin, pp 1882–1893
Gérard P, Stolzmann W, Sigaud O (2002) YACS: a new learning classifier system with anticipation. J Soft Comput Spl Issue Learn Classif Syst 6(3-4):216–228
Golberg DE, Holland JH (1988) Guest editorial: genetic algorithms and machine learning. Mach Learn 3:95–99
Goldberg DE (1989) Genetic algorithms in search, optimization, machine learning. Addison Wesley, Reading
Herbart JF (1825) Psychologie als Wissenschaft neu gegründet auf Erfahrung, Metaphysik und Mathematik. Zweiter, analytischer Teil. August Wilhem Unzer, Koenigsberg, Germany
Hoffmann J (1993) Vorhersage und Erkenntnis [Anticipation and Cognition]. Hogrefe, Göttingen
Holland JH (1975) Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, artificial intelligence. University of Michigan Press, Ann Arbor
Holland JH (1986) Escaping brittleness: the possibilities of general-purpose learning algorithms applied to parallel rule-based systems. In: Machine learning, an artificial intelligence approach (vol II). Morgan Kaufmann, San Francisco
Holland JH, Holyoak KJ, Nisbett RE, Thagard PR (1986) Induction. MIT, Cambridge
Holland JH, Reitman JS (1978) Cognitive systems based on adaptive algorithms. Pattern Direct Infer Syst 7(2):125–149
Holmes JH (2002) A new representation for assessing classifier performance in mining large databases. In: Stolzmann W, Lanzi P-L, Wilson SW (eds) IWLCS-02. Proceedings of the international workshop on learning classifier systems, LNAI, Granada. Springer, Berlin
Kovacs T (2002) Learning classifier systems resources. J Soft Comput 6(3-4):240–243
Kovacs T (2004) Strength or accuracy: credit assignment in learning classifier systems. Springer, Berlin
Landau S, Sigaud O (2006) A comparison between ATNoSFERES and LCSs on non-Markov problems. Inform Sci (to appear)
Landau S, Sigaud O, Schoenauer M (2005) ATNoSFERES revisited. In: Beyer H-G, O’Reilly U-M, Arnold D, Banzhaf W, Blum C, Bonabeau E, Cantú Paz E, Dasgupta D, Deb K, Foster J, de Jong E, Lipson H, Llora X, Mancoridis S, Pelikan M, Raidl G, Soule T, Tyrrell A, Watson J-P, Zitzler E (eds) Proceedings of the genetic and evolutionary computation conference, GECCO-2005, Washington. ACM, pp 1867–1874
Langdon WB, Cantu-Paz E, Mathias K, Roy R, Davis D, Poli R, Balakrishnan K, Honavar V, Rudolph G, Wegener J, Bull L, Potter MA, Schultz AC, Miller JF, Burke E, Jonoska N (eds) (2002) Proceedings of the genetic and evolutionary computation conference, GECCO 2002, New York. Morgan Kaufmann, San Francisco
Lanzi P-L (1998) Adding memory to XCS. In: Proceedings of the IEEE conference on evolutionary computation (ICEC98). IEEE Press
Lanzi P-L (2002) Learning classifier systems from a reinforcement learning perspective. J Soft Comput 6(3–4):162–170
Lanzi P-L, Loiacono D, Wilson S, Goldberg DE (2006) Classifier prediction based on tile coding. In: Proceedings of the 2006 genetic and evolutionary computation conference workshop program (GECCO 2006). Seattle, Washington, pp 1497–1504
Lanzi P-L, Perrucci A (1999) Extending the representation of classifier conditions part ii: from messy coding to s-expressions. In: Banzhaf W, Daida J, Eiben AE, Garzon MH, Honavar V, Jakiela M, Smith RE (eds) Proceedings of the genetic and evolutionary computation conference (GECCO 99), Orlando. Morgan Kaufmann, San Francisco, pp 345–352
Lanzi P-L, Riolo RL (2000) A roadmap to the last decade of learning classifier systems research (from 1989 to 1999). In: Lanzi P-L, Stolzmann W, Wilson SW (eds) Learning classifier systems: from foundations to applications. Springer, Heidelberg, pp 33–62
Lanzi P-L, Stolzmann W, Wilson SW, (eds) (2000) Learning classifier systems. From Foundations to Applications, vol 1813 of Lecture Notes in Artificial Intelligence. Springer, Berlin
Lanzi P-L, Stolzmann W, Wilson SW (eds). (2001) Advances in learning classifier systems, vol 1996 of Lecture Notes in Artificial Intelligence. Springer, Berlin
Lanzi P-L, Stolzmann W, Wilson SW (eds) (2002a) Advances in learning classifier systems, vol 2321 of Lecture Notes in Artificial Intelligence. Springer, Berlin
Lanzi P-L, Stolzmann W, Wilson SW (eds) (2002b) Proceedings of the international workshop on learning classifier systems (IWLCS2002), Granada
Llorà X, Garrell JM (2002) Co-evolving different knowledge representations with fine-grained parallel learning classifier systems. In: Langdon WB, Cantu-Paz E, Mathias K, Roy R, Davis D, Poli R, Balakrishnan K, Honavar V, Rudolph G, Wegener J, Bull L, Potter MA, Schultz AC, Miller JF, Burke E, Jonoska N (eds) Proceeding of the genetic and evolutionary computation conference (GECCO2002). Morgan Kaufmann, San Francisco
MiramontesHercog L, Fogarty TC (2002) Co-evolutionary classifier systems for multi-agent simulation. In: Fogel DB, El-Sharkawi MA, Yao X, Greenwood G, Iba H, Marrow P, Shackleton M (eds) Proceedings of the 2002 congress on evolutionary computation CEC2002. IEEE Press, pp 1798–1803
Poli R, Langdon WB (1998) Schema theory for genetic programming with one-point crossover and point mutation. Evol Comput J 6(3):231–252
Puterman ML, Shin MC (1978) Modified policy iteration algorithms for discounted markov decision problems. Manage Sci 24:1127–1137
Riolo RL (1991) Lookahead planning and latent learning in a Classifier System. In: Meyer J-A, Wilson SW (eds) From animals to animats: proceedings of the first international conference on simulation of adaptative behavior. MIT, Cambridge, pp 316–326
Robert G (2005) MHiCS, une architecture de Sélection de l’Action Motivationnelle et Hiérarchique á Systèmes de Classeurs pour Personnages Non Joueurs Adaptatifs. PhD thesis, Laboratoire d’Informatique de Paris 6
Sanchez S (2004) Mécanismes évolutionnistes pour la simulation comportementale d’acteurs virtuels. PhD thesis, Université de Siences Sociales Toulouse 1, Toulouse
Sanza C (2001) Evolution d’entités vituelles cooperatives par systèmes de classifieurs. PhD thesis, Université Paul Sabatier, Toulouse
Seward JP (1949) An experimental analysis of latent learning. J Exp Psychol 39:177–186
Sigaud O, Gourdin T, Wuillemin P-H (2004) Improving MACS thanks to a comparison with 2TBNs. In: Proceedings of the genetic and evolutionary computation conference, GECCO’04. Springer, Berlin, pp 810–823
Smith SF (1980) A learning system based on genetic algorithms. PhD thesis, Department of Computer Science, University of Pittsburg, Pittsburg
Spector LD, GE, Wu A, Langdon WB, Voigt HM, Gen M (eds) (2001) Proceedings of the genetic and evolutionary computation conference (GECCO01). Morgan Kaufmann, San Francisco
Stolzmann W (1998) Anticipatory classifier systems. In Koza J, Banzhaf W, Chellapilla K, Deb K, Dorigo M, Fogel DB, Garzon MH, Goldberg DE, Iba H, Riolo R (eds) Genetic programming. Morgan Kaufmann, San Francisco, pp 658–664
Stolzmann W, Lanzi P-L, Wilson SW (eds) (2002) Proceedings of the international workshop on learning classifier systems (IWLCS2003), Chicago
Stone C, Bull L (2003) Towards learning classifier systems for continuous-valued online environments. In: Cantú-Paz E, Foster JA, Deb K, Davis D, Roy R, O’Reilly U-M, Beyer H-G, Standish R, Kendall G, Wilson S, Harman M, Wegener J, Dasgupta D, Potter MA, Schultz AC, Dowsland K, Jonoska N, Miller J (eds) Genetic and evolutionary computation—GECCO-2003. Springer, Berlin, pp 1924–1925
Sutton RS (1990) Planning by incremental dynamic programming. In: Proceedings of the eighth international conference on machine learning, San Mateo. Morgan Kaufmann, San Francisco pp 353–357
Sutton RS (1996) Generalization in reinforcement learning: successul examples using sparse coarse coding. In: Touretzky DS, Mozer MC, Hasselmo ME (eds) Advances in neural information processing systems: proceedings of the 1995 conference. MIT, Cambridge, pp. 1038–1044
Sutton RS, Barto AG (1998) Reinforcement learning: an introduction. MIT, Cambridge
Tolman EC (1932) Purposive behavior in animals and men. Appletown, New York
Tomlinson A, Bull L (1998) A corporate classifier system. In: Eiben AE, Bäck T, Shoenauer M, Schwefel H-P (eds) Proceedings of the fifth international conference on parallel problem solving from nature—PPSN V, no. 1498 in LNCS, Springer, Berlin pp 550–559
Tomlinson A, Bull L (2000) CXCS. In: Lanzi P-L, Stolzmann W, Wilson SW (eds) Learning classifier systems: from foundations to applications. Springer, Heidelberg, pp 194–208
Watkins CJCH (1989) Learning with delayed rewards. PhD thesis, Psychology Department, University of Cambridge, England
Whitley LD, Goldberg DE, Cantú-Paz E, Spector L, Parmee IC, Beyer H-G (eds) (2000) Proceedings of the genetic and evolutionary computation conference (GECCO00). Morgan Kaufmann, San Francisco
Wilson SW (1985) Knowledge growth in an artificial animat. In: Grefenstette JJ (Ed.) Proceedings of the 1st international conference on genetic algorithms and their applications (ICGA85), pp 16–23. LE. Associates
Wilson SW (1994) ZCS, a zeroth level classifier system. Evol Comput 2(1):1–18
Wilson SW (1995) Classifier fitness based on accuracy. Evol Comput 3(2):149–175
Wilson SW (2000) Get real! XCS with continuous-valued inputs. In: Lanzi P-L, Stolzmann W, Wilson SW (eds) LNAI 1813: From foundations to applications. Springer, Berlin, pp 209–220
Wilson SW (2001) Function approximation with a classifier system. In: Spector L, D GE, Wu A, Langdon WB, Voigt HM, Gen M (eds) Proceedings of the genetic and evolutionary computation conference (GECCO01). Morgan Kaufmann, San Francisco, pp 974–981
Wilson SW (2004) Classifier systems for continuous payoff environments. In: LNCS 3103: learning classifier systems. Springer, Heidelberg, pp 824–835.
Wilson SW, Goldberg DE (1989) A critical review of classifier systems. In: Proceedings of the third international conference on genetic algorithms, Los Altos, California. Morgan Kaufmann, San Francisco, pp 244–255
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Sigaud, O., Wilson, S.W. Learning classifier systems: a survey. Soft Comput 11, 1065–1078 (2007). https://doi.org/10.1007/s00500-007-0164-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-007-0164-0