Editing Learning classifier system (section)

=== Early years ===
[[John Henry Holland]] was best known for his work popularizing [[genetic algorithm]]s (GA), through his ground-breaking book "Adaptation in Natural and Artificial Systems"<ref>{{Cite book|title=Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence|last=Holland|first=John|publisher=Michigan Press|year=1975|isbn=9780262581110|url=https://books.google.com/books?id=5EgGaBkwvWcC}}</ref> in 1975 and his formalization of [[Holland's schema theorem]].  In 1976, Holland conceptualized an extension of the GA concept to what he called a "cognitive system",<ref>Holland JH (1976) Adaptation. In: Rosen R, Snell F (eds) Progress in theoretical biology, vol 4. Academic Press, New York, pp 263–293</ref> and provided the first detailed description of what would become known as the first learning classifier system in the paper "Cognitive Systems based on Adaptive Algorithms".<ref name=":2">Holland JH, Reitman JS (1978) Cognitive systems based on
adaptive algorithms Reprinted in: Evolutionary computation.
The fossil record. In: David BF (ed) IEEE Press, New York
1998. {{ISBN|0-7803-3481-7}}
</ref>  This first system, named '''Cognitive System One (CS-1)''' was conceived as a modeling tool, designed to model a real system (i.e. ''environment'') with unknown underlying dynamics using a population of human readable rules.  The goal was for a set of rules to perform [[online machine learning]] to adapt to the environment based on infrequent payoff/reward (i.e. reinforcement learning) and apply these rules to generate a behavior that matched the real system. This early, ambitious implementation was later regarded as overly complex, yielding inconsistent results.<ref name=":1" /><ref name=":3">{{Cite journal|last=Lanzi|first=Pier Luca|date=2008-02-08|title=Learning classifier systems: then and now|journal=Evolutionary Intelligence|language=en|volume=1|issue=1|pages=63–82|doi=10.1007/s12065-007-0003-3|s2cid=27153843|issn=1864-5909}}</ref>

Beginning in 1980, [[Kenneth A De Jong|Kenneth de Jong]] and his student Stephen Smith took a different approach to rule-based machine learning with '''(LS-1)''', where learning was viewed as an offline optimization process rather than an online adaptation process.<ref>Smith S (1980) A learning system based on genetic adaptive
algorithms. Ph.D. thesis, Department of Computer Science,
University of Pittsburgh
</ref><ref>Smith S (1983) [https://www.researchgate.net/profile/Stephen_Smith14/publication/220815785_Flexible_Learning_of_Problem_Solving_Heuristics_Through_Adaptive_Search/links/0deec52c18dbd0dd53000000.pdf Flexible learning of problem solving heuristics through adaptive search]. In: Eighth international joint conference
on articial intelligence. Morgan Kaufmann, Los Altos, pp
421–425
</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 an 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|doi-access=free}}</ref> and the introduction of the ''correct set'' [C],<ref>{{Cite book|last1=Bonelli|first1=Pierre|last2=Parodi|first2=Alexandre|last3=Sen|first3=Sandip|last4=Wilson|first4=Stewart|date=1990-01-01|title=NEWBOOLE: A Fast GBML System|url=https://archive.org/details/machinelearningp0000inte/page/153|journal=Proceedings of the Seventh International Conference (1990) on Machine Learning|location=San Francisco, CA, USA|publisher=Morgan Kaufmann Publishers Inc.|pages=[https://archive.org/details/machinelearningp0000inte/page/153 153–159]|isbn=978-1558601413|url-access=registration}}</ref> (8) ''accuracy-based fitness''<ref>{{Cite journal|last1=Frey|first1=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|doi-access=free}}</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=en}}</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=en}}</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.

658–664, 1998.
</ref>), and (12) the introduction of the first [[Q-learning]]-like credit assignment technique.<ref>{{Cite book|last=Riolo|first=Rick L.|date=1990-01-01|title=Lookahead Planning and Latent Learning in a Classifier System|url=http://dl.acm.org/citation.cfm?id=116517.116553|journal=Proceedings of the First International Conference on Simulation of Adaptive Behavior on from Animals to Animats|location=Cambridge, MA, USA|publisher=MIT Press|pages=316–326|isbn=978-0262631389}}</ref>  While not all of these concepts are applied in modern LCS algorithms, each were landmarks in the development of the LCS paradigm.