Learning classifier system: Difference between revisions

Revision as of 08:22, 2 September 2019

Revision as of 12:54, 7 September 2019

Line 68:

</ref><ref>De Jong KA (1988) Learning with genetic algorithms: an overview. Mach Learn 3:121–138</ref> This new approach was more similar to a standard genetic algorithm but evolved independent sets of rules. Since that time LCS methods inspired by the online learning framework introduced by Holland at the University of Michigan have been referred to as '''Michigan-style LCS''', and those inspired by Smith and De Jong at the University of Pittsburgh have been referred to as '''Pittsburgh-style LCS'''.<ref name=":1" /><ref name=":3" /> In 1986, Holland developed what would be considered the standard Michigan-style LCS for the next decade.<ref name=":4">[http://dl.acm.org/citation.cfm?id=216016 Holland, John H. "Escaping brittleness: the possibilities of general purpose learning algorithms applied to parallel rule-based system." ''Machine learning''(1986): 593-623.]</ref>

Other important concepts that emerged in the early days of LCS research included (1) the formalization of a ''bucket brigade algorithm'' (BBA) for credit assignment/learning,<ref>{{Cite book|last=Holland|first=John H.|date=1985-01-01|title=Properties of the Bucket Brigade|url=http://dl.acm.org/citation.cfm?id=645511.657087|journal=Proceedings of the 1st International Conference on Genetic Algorithms|___location=Hillsdale, NJ, USA|publisher=L. Erlbaum Associates Inc.|pages=1–7|isbn=978-0805804263}}</ref> (2) selection of parent rules from a common 'environmental niche' (i.e. the ''match set'' [M]) rather than from the whole ''population'' [P],<ref>{{Cite thesis|last=Booker|first=L|title=Intelligent Behavior as a Adaptation to the Task Environment|date=1982-01-01|publisher=University of Michigan|url=http://www.citeulike.org/group/664/article/431772}}</ref> (3) ''covering'', first introduced as a ''create'' operator,<ref name=":5">Wilson, S. W. "[http://www.cs.sfu.ca/~vaughan/teaching/415/papers/wilson_animat.pdf Knowledge growth in an artificial animal]. Proceedings of the First International Conference on Genetic Algorithms and their Applications." (1985).</ref> (4) the formalization of an ''action set'' [A],<ref name=":5" /> (5) a simplified algorithm architecture,<ref name=":5" /> (6) ''strength-based fitness'',<ref name=":4" /> (7) consideration of single-step, or supervised learning problems<ref>{{Cite journal|last=Wilson|first=Stewart W.|title=Classifier systems and the animat problem|journal=Machine Learning|language=en|volume=2|issue=3|pages=199–228|doi=10.1007/BF00058679|issn=0885-6125|year=1987}}</ref> and the introduction of the ''correct set'' [C],<ref>{{Cite book|last=Bonelli|first=Pierre|last2=Parodi|first2=Alexandre|last3=Sen|first3=Sandip|last4=Wilson|first4=Stewart|date=1990-01-01|title=NEWBOOLE: A Fast GBML System|url=httphttps://dl.acmarchive.org/citation.cfm?id=101883.102047details/machinelearningp0000inte|journal=Proceedings of the Seventh International Conference (1990) on Machine Learning|___location=San Francisco, CA, USA|publisher=Morgan Kaufmann Publishers Inc.|pages=153–159|isbn=978-1558601413|url-access=registration}}</ref> (8) ''accuracy-based fitness''<ref>{{Cite journal|last=Frey|first=Peter W.|last2=Slate|first2=David J.|title=Letter recognition using Holland-style adaptive classifiers|journal=Machine Learning|language=en|volume=6|issue=2|pages=161–182|doi=10.1007/BF00114162|issn=0885-6125|year=1991}}</ref> (9) the combination of fuzzy logic with LCS<ref>Valenzuela-Rendón, Manuel. "[http://sci2s.ugr.es/sites/default/files/files/TematicWebSites/GeneticFuzzySystems/(1991)_Valenzuela-Rendon.pdf The Fuzzy Classifier System: A Classifier System for Continuously Varying Variables]." In ''ICGA'', pp. 346-353. 1991.</ref> (which later spawned a lineage of ''fuzzy LCS algorithms''), (10) encouraging ''long action chains'' and ''default hierarchies'' for improving performance on multi-step problems,<ref>{{Cite thesis|last=Riolo|first=Rick L.|title=Empirical Studies of Default Hierarchies and Sequences of Rules in Learning Classifier Systems|date=1988-01-01|publisher=University of Michigan|url=http://dl.acm.org/citation.cfm?id=914945|place=Ann Arbor, MI, USA}}</ref><ref>{{Cite journal|last=R.L.|first=Riolo|date=1987-01-01|title=Bucket brigade performance. I. Long sequences of classifiers|url=http://agris.fao.org/agris-search/search.do?recordID=US201301782174|journal=Genetic Algorithms and Their Applications : Proceedings of the Second International Conference on Genetic Algorithms : July 28–31, 1987 at the Massachusetts Institute of Technology, Cambridge, MA|language=English}}</ref><ref>{{Cite journal|last=R.L.|first=Riolo|date=1987-01-01|title=Bucket brigade performance. II. Default hierarchies|url=http://agris.fao.org/agris-search/search.do?recordID=US201301782175|journal=Genetic Algorithms and Their Applications : Proceedings of the Second International Conference on Genetic Algorithms : July 28–31, 1987 at the Massachusetts Institute of Technology, Cambridge, MA|language=English}}</ref> (11) examining [[latent learning]] (which later inspired a new branch of ''anticipatory classifier systems'' (ACS)<ref name=":7">W. Stolzmann, "Anticipatory classifier systems," in Proceedings

of the 3rd Annual Genetic Programming Conference, pp.