×

Learning classifier systems: a survey. (English) Zbl 1122.68504

Summary: 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.

MSC:

68T05 Learning and adaptive systems in artificial intelligence

Software:

YACS; ACS2
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] 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
[2] Bacardit, J.; Garrell, JM; 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., Evolving multiple discretizations with adaptive intervals for a Pittsburgh rule-based learning classifier system, Genetic and evolutionary computation—GECCO-2003, 1818-1831 (2003), Berlin: Springer, Berlin · Zbl 1038.68627
[3] Banzhaf, W.; Daida, J.; Eiben, AE; Garzon, MH; Honavar, V.; Jakiela, M.; Smith, RE, Proceedings of the 1999 genetic and evolutionary computation conference workshop program (1999), San Francisco: Morgan Kaufmann, San Francisco
[4] Bellman, RE, Dynamic programming (1957), Princeton: Princeton University Press, Princeton · Zbl 0077.13605
[5] Bellman, RE, Adaptive control processes: a guided tour (1961), Princeton: Princeton University Press, Princeton · Zbl 0103.12901
[6] 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
[7] Bertsekas, DP, Dynamic programming and optimal control (1995), Belmont: Athena Scientific, Belmont · Zbl 0904.90170
[8] 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
[9] Booker, L.; Goldberg, DE; Holland, JH, Classifier systems and genetic algorithms, Artif Intell, 40, 1-3, 235-282 (1989) · doi:10.1016/0004-3702(89)90050-7
[10] Booker, LB; Lanzi, P-L; Stolzmann, W.; Wilson, SW, Do we really need to estimate rule utilities in classifier systems?, Learning classifier systems. From foundations to applications, vol. 1813 of Lecture Notes in Artificial Intelligence, 125-142 (2000), Berlin: Springer, Berlin
[11] 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
[12] Boutilier, C.; Dearden, R.; Goldszmidt, M., Stochastic dynamic programming with factored representations, Artif Intell, 121, 1, 49-107 (2000) · Zbl 0948.68167 · doi:10.1016/S0004-3702(00)00033-3
[13] Bull, L., On ZCS in multi-agent environments, Lect Notes Comput Sci, 1498, 471-479 (1998) · doi:10.1007/BFb0056889
[14] Bull, L.; Banzhaf, W.; Daida, J.; Eiben, AE; Garzon, MH; Honavar, V.; Jakiela, M.; Smith, RE, On using ZCS in a simulated continuous double-auction market, Proceedings of the 1999 genetic and evolutionary computation conference workshop program, 83-90 (1999), San Francisco: Morgan Kaufmann, San Francisco
[15] Bull, L.; Yao, X.; Burke, E.; Lozano, JA; Smith, J.; Merelo-Guervós, JJ; Bullinaria, JA; Rowe, J.; Tino, P.; Kabán, A.; Schwefel, H-P, A simple payoff-based learning classifier system, Proceedings of parallel problem solving from nature (PPSN VIII) (2004), Heidelberg: Springer, Heidelberg
[16] Bull, L., Applications of learning classifier systems (2004), Heidelberg: Springer, Heidelberg · Zbl 1054.68109
[17] Bull, L.; Bull, L.; Kovacs, T., Two simple learning classifier systems, Foundations of learning classifier systems (2005), Heidelberg: Springer, Heidelberg · Zbl 1084.68116
[18] Bull, L.; Hurst, J., ZCS redux, Evol Comput, 10, 2, 185-205 (2002) · doi:10.1162/106365602320169848
[19] Butz, M.; Kovacs, T.; Lanzi, PL; Wilson, SW, Toward a theory of generalization and learning in xcs, IEEE Trans Evol Comput, 8, 1, 28-46 (2004) · doi:10.1109/TEVC.2003.818194
[20] 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)
[21] Butz, MV; Lanzi, P-L; Stolzmann, W.; Wilson, SW, An algorithmic description of ACS2, Advances in learning classifier systems, vol 2321 of Lecture Notes in Artificial Intelligence, 211-229 (2002), Berlin: Springer, Berlin · Zbl 1047.68683
[22] Butz, MV; Goldberg, DE; Butz, MV; Sigaud, O.; Gérard, P., Generalized state values in an anticipatory Learning Classifier System, LNAI 2684: anticipatory behavior in adaptive learning systems, 281-301 (2003), Heidelberg: Springer, Heidelberg
[23] Butz MV, Goldberg DE, Lanzi PL (2003a) Gradient descent methods in learning classifier systems: improving XCS performance in multistep problem. Technical report 2003028, IlliGAL
[24] 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
[25] 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 · Zbl 1038.68651
[26] Butz, MV; Wilson, SW, An algorithmic description of XCS, J Soft Comput, 6, 3-4, 144-153 (2002) · Zbl 1027.68658
[27] 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
[28] Cao, YJ; Ireson, N.; Bull, L.; Miles, R.; Reusch, B., Design of a traffic junction controller using a classifier system and fuzzy logic, Proceedings of the sixth international conference on computational intelligence, theory and applications (6th fuzzy days), vol 1625 of LNCS, 342-353 (1999), Berlin: Springer, Berlin
[29] Cao, YJ; Ireson, N.; Bull, L.; Miles, R., An evolutionary intelligent agents approach to traffic signal control, Int J Knowl based Intell Eng Syst, 5, 4, 279-289 (2001)
[30] Cliff, D.; Ross, S., Adding memory to ZCS, Adapt Behav, 3, 2, 101-150 (1994) · doi:10.1177/105971239400300201
[31] 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
[32] 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
[33] 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
[34] 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
[35] 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
[36] Gérard, P.; Meyer, J-A; Sigaud, O., Combining latent learning with dynamic programming in MACS, Euro J Oper Res, 160, 614-637 (2005) · Zbl 1061.90081 · doi:10.1016/j.ejor.2003.10.004
[37] 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 · Zbl 1038.68704
[38] Gérard, P.; Stolzmann, W.; Sigaud, O., YACS: a new learning classifier system with anticipation, J Soft Comput Spl Issue Learn Classif Syst, 6, 3-4, 216-228 (2002) · Zbl 1027.68661
[39] Golberg, DE; Holland, JH, Guest editorial: genetic algorithms and machine learning, Mach Learn, 3, 95-99 (1988) · doi:10.1023/A:1022602019183
[40] Goldberg, DE, Genetic algorithms in search, optimization, machine learning (1989), Reading: Addison Wesley, Reading · Zbl 0721.68056
[41] Herbart JF (1825) Psychologie als Wissenschaft neu gegründet auf Erfahrung, Metaphysik und Mathematik. Zweiter, analytischer Teil. August Wilhem Unzer, Koenigsberg, Germany
[42] Hoffmann, J., Vorhersage und Erkenntnis [Anticipation and Cognition] (1993), Göttingen: Hogrefe, Göttingen
[43] Holland, JH, Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, artificial intelligence (1975), Ann Arbor: University of Michigan Press, Ann Arbor · Zbl 0317.68006
[44] 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
[45] Holland, JH; Holyoak, KJ; Nisbett, RE; Thagard, PR, Induction (1986), Cambridge: MIT, Cambridge
[46] Holland, JH; Reitman, JS, Cognitive systems based on adaptive algorithms, Pattern Direct Infer Syst, 7, 2, 125-149 (1978)
[47] 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
[48] Kovacs, T., Learning classifier systems resources, J Soft Comput, 6, 3-4, 240-243 (2002) · Zbl 1027.68662
[49] Kovacs, T., Strength or accuracy: credit assignment in learning classifier systems (2004), Berlin: Springer, Berlin · Zbl 1060.68103
[50] Landau S, Sigaud O (2006) A comparison between ATNoSFERES and LCSs on non-Markov problems. Inform Sci (to appear)
[51] 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
[52] 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
[53] Lanzi P-L (1998) Adding memory to XCS. In: Proceedings of the IEEE conference on evolutionary computation (ICEC98). IEEE Press
[54] Lanzi, P-L, Learning classifier systems from a reinforcement learning perspective, J Soft Comput, 6, 3-4, 162-170 (2002) · Zbl 1027.68664
[55] 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
[56] Lanzi, P-L; Perrucci, A.; Banzhaf, W.; Daida, J.; Eiben, AE; Garzon, MH; Honavar, V.; Jakiela, M.; Smith, RE, Extending the representation of classifier conditions part ii: from messy coding to s-expressions, Proceedings of the genetic and evolutionary computation conference (GECCO 99), Orlando, 345-352 (1999), San Francisco: Morgan Kaufmann, San Francisco
[57] Lanzi, P-L; Riolo, RL; Lanzi, P-L; Stolzmann, W.; Wilson, SW, A roadmap to the last decade of learning classifier systems research (from 1989 to 1999), Learning classifier systems: from foundations to applications, 33-62 (2000), Heidelberg: Springer, Heidelberg
[58] Lanzi, P-L; Stolzmann, W.; Wilson, SW, Learning classifier systems. From Foundations to Applications, vol 1813 of Lecture Notes in Artificial Intelligence (2000), Berlin: Springer, Berlin
[59] Lanzi, P-L; Stolzmann, W.; Wilson, SW, Advances in learning classifier systems, vol 1996 of Lecture Notes in Artificial Intelligence (2001), Berlin: Springer, Berlin · Zbl 0992.68525
[60] Lanzi, P-L; Stolzmann, W.; Wilson, SW, Advances in learning classifier systems, vol 2321 of Lecture Notes in Artificial Intelligence (2002), Berlin: Springer, Berlin · Zbl 0992.68525
[61] Lanzi P-L, Stolzmann W, Wilson SW (eds) (2002b) Proceedings of the international workshop on learning classifier systems (IWLCS2002), Granada
[62] 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
[63] 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
[64] Poli, R.; Langdon, WB, Schema theory for genetic programming with one-point crossover and point mutation, Evol Comput J, 6, 3, 231-252 (1998)
[65] Puterman, ML; Shin, MC, Modified policy iteration algorithms for discounted markov decision problems, Manage Sci, 24, 1127-1137 (1978) · Zbl 0391.90093 · doi:10.1287/mnsc.24.11.1127
[66] Riolo, RL; Meyer, J-A; Wilson, SW, Lookahead planning and latent learning in a Classifier System, From animals to animats: proceedings of the first international conference on simulation of adaptative behavior, 316-326 (1991), Cambridge: MIT, Cambridge
[67] 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
[68] Sanchez S (2004) Mécanismes évolutionnistes pour la simulation comportementale d’acteurs virtuels. PhD thesis, Université de Siences Sociales Toulouse 1, Toulouse
[69] Sanza C (2001) Evolution d’entités vituelles cooperatives par systèmes de classifieurs. PhD thesis, Université Paul Sabatier, Toulouse
[70] Seward, JP, An experimental analysis of latent learning, J Exp Psychol, 39, 177-186 (1949) · doi:10.1037/h0063169
[71] 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
[72] Smith SF (1980) A learning system based on genetic algorithms. PhD thesis, Department of Computer Science, University of Pittsburg, Pittsburg
[73] Spector, LD; Ge; Wu, A.; Langdon, WB; Voigt, HM; Gen, M., Proceedings of the genetic and evolutionary computation conference (GECCO01) (2001), San Francisco: Morgan Kaufmann, San Francisco
[74] Stolzmann, W.; Koza, J.; Banzhaf, W.; Chellapilla, K.; Deb, K.; Dorigo, M.; Fogel, DB; Garzon, MH; Goldberg, DE; Iba, H.; Riolo, R., Anticipatory classifier systems, Genetic programming, 658-664 (1998), San Francisco: Morgan Kaufmann, San Francisco
[75] Stolzmann W, Lanzi P-L, Wilson SW (eds) (2002) Proceedings of the international workshop on learning classifier systems (IWLCS2003), Chicago
[76] Stone, C.; Bull, L.; 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., Towards learning classifier systems for continuous-valued online environments, Genetic and evolutionary computation—GECCO-2003, 1924-1925 (2003), Berlin: Springer, Berlin · Zbl 1038.68878
[77] 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
[78] Sutton, RS; Touretzky, DS; Mozer, MC; Hasselmo, ME, Generalization in reinforcement learning: successul examples using sparse coarse coding, Advances in neural information processing systems: proceedings of the 1995 conference, 1038-1044 (1996), Cambridge: MIT, Cambridge
[79] Sutton, RS; Barto, AG, Reinforcement learning: an introduction (1998), Cambridge: MIT, Cambridge
[80] Tolman, EC, Purposive behavior in animals and men (1932), New York: Appletown, New York
[81] 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
[82] Tomlinson, A.; Bull, L.; Lanzi, P-L; Stolzmann, W.; Wilson, SW, CXCS, Learning classifier systems: from foundations to applications, 194-208 (2000), Heidelberg: Springer, Heidelberg
[83] Watkins CJCH (1989) Learning with delayed rewards. PhD thesis, Psychology Department, University of Cambridge, England
[84] 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
[85] 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 · Zbl 0695.68061
[86] Wilson, SW, ZCS, a zeroth level classifier system, Evol Comput, 2, 1, 1-18 (1994)
[87] Wilson, SW, Classifier fitness based on accuracy, Evol Comput, 3, 2, 149-175 (1995)
[88] Wilson, SW; Lanzi, P-L; Stolzmann, W.; Wilson, SW, Get real! XCS with continuous-valued inputs, LNAI 1813: From foundations to applications, 209-220 (2000), Berlin: Springer, Berlin
[89] Wilson, SW; Spector, L.; D, Ge; Wu, A.; Langdon, WB; Voigt, HM; Gen, M., Function approximation with a classifier system, Proceedings of the genetic and evolutionary computation conference (GECCO01), 974-981 (2001), San Francisco: Morgan Kaufmann, San Francisco
[90] Wilson SW (2004) Classifier systems for continuous payoff environments. In: LNCS 3103: learning classifier systems. Springer, Heidelberg, pp 824-835.
[91] 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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.