Holland classifier systems

ABSTRACT

A Holland classifier system is an adaptive, general purpose machine learning system which is designed to operate in noisy environments with infrequent and often incomplete feedback. Examples of such environments are financial markets, stock management systems, or chemical processes. In financial markets, a Holland classifier system would develop trading strategies, in a stock management system order heuristics, and in a chemical plant it would perform process control. In this paper we describe a Holland classifier system and present the implementation of its components, namely the production system, the bucket brigade algorithm, the genetic algorithm, and the cover detector, cover effector and triggered chaining operator. Finally, we illustrate the working of a Holland classifier system by learning to find a path with a high payoff in a simple finite state world.

REFERENCES

• Aliprantis et al., 1990: Charalambos D. Aliprantis, Donald J. Brown, and Owen Burkinshaw. Ex~slence and Optimality of Competztive Equilibria. Springer, Berlin, 1990.
• Arrow and Hahn, 1971: Kenneth J. Arrow and F. It. Hahn. General Competitive Analysis, volume 6 of Mathematical Economics Texts. Holden-Day, inc., San Francisco, 1971.
• Aubin, 1979: jean Pierre Aubin. Mathematical Methods of Game and Economic Theory, volume 7 of Studies in Mathematics and its Applications. North- Holland, Amsterdam, 1979.
• Farmer et al., 1986: J D Farmer , N H Packard, Evolution, games, and learning: models for adaptation in machines and nature. An introduction to the proceedings of the CNLS conference, Los Alamos, May 1985, Physica D, v.2 n.1-3, p.7-12, Oct.-Nov. 1986
• Geyer-Schulz, 1995: Andreas Geyer-Schulz. Fuzzy Rule-Based Expert Systems and Genetic Machine Learning, volume 3 of Studies in Fuzziness. Physica- Verlag, Heidelberg, 1995. 431p.
• Goldberg, 1989: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• Grefenstette, 1987: john J. Grefenstette, editor. Genetic Algorilhms and their Applications. Lawrence Erlbaum Associates, ttillsdale, New Jersey, 1987.
• Grefenstette, 1988: J.J. Grefenstette, Credit assignment in rule discovery systems based on genetic algorithms, Machine Language, v.3 n.2-3, p.225-245, Oct. 1988 [doi>10.1007/BF00113898]
• Holland and Reitman, 1978: John H. Holland and Judith S. Reitman. Cognitive systems based on adaptive algorithms. In Waterman and Hayes-Roth {1978}, pages 313-329.
• Holland et al., 1986: John H. Holland , Keith J. Holyoak , Richard E. Nisbett , Paul R. Thagard, Induction: processes of inference, learning, and discovery, MIT Press, Cambridge, MA, 1986
• Holland, 1986a: John H. Holland. Escaping brittleness: The possibilities of general-purpose learning algorithms applied to parallel rule-based systems, in Michalski et al. {1986}, pages 593-623.
• Holland, 1986b: J H Holland, A mathematical framework for studying learning in classifier systems, Physica D, v.2 n.1-3, p.307-317, Oct.-Nov. 1986
• Howard, 1971: Ronald A. Howard. Dynamic Probabilislic Systems. Volume I: Markov Models, volume 1 of Series in Decision and Control. john Wiley & Sons, New York, 1971.
• Koza, 1992: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• Michalski et al., 1986: Ryszard S. Michalski, Jaime G. Carbonell, and Tom M. Mitchell, editors. Machine Learning, volume II. Morgan Kaufmann, Los Altos, 1986.
• Minsky, 1971: Marvin L. Minsky. Berechnung: Endliche und unendliche Maschinen. Verlag Berliner Union GmbH, Stuttgart, 1971.
• Paich and Sterman, 1993: Mark Paich , John D. Sterman, Boom, bust, and failures to learn in experimental markets, Management Science, v.39 n.12, p.1439-1458, Dec. 1993 [doi>10.1287/mnsc.39.12.1439]
• Riolo, 1987a: Rick L. Riolo, Bucket brigade performance: I. Long sequences of classifiers, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.184-195, October 1987, Cambridge, Massachusetts, United States
• Riolo, 1987b: Rick L. Riolo, Bucket brigade performance: II. Default hierarchies, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.196-201, October 1987, Cambridge, Massachusetts, United States
• Riolo, 1989a: Rick L. Riolo, The emergence of coupled sequences of classifiers, Proceedings of the third international conference on Genetic algorithms, p.256-264, December 1989, George Mason University, United States
• Riolo, 1989b: Rick L. Riolo, The emergence of default hierarchies in learning classifier systems, Proceedings of the third international conference on Genetic algorithms, p.322-327, December 1989, George Mason University, United States
• Robertson and Riolo, 1988: G. G. Robertson , R. L. Riolo, A tale of two classifier systems, Machine Language, v.3 n.2-3, p.139-159, Oct. 1988 [doi>10.1007/BF00113895]
• Schaffer, 1989: Proceedings of the 3rd International Conference on Genetic Algorithms, June 1989
• Smith, 1776: Adam Smith. An Inquiry into the Nature and Causes of the Wealth of Nations. W. Strahan and T. Cadell, London, 1st edition, 1776. Quoted from the LibertyClassics 1981 edition of Liberty Press, Indianapolis which is a reprint of the Glasgow edition of the works and correspondence of Adam Smith, volume 2, edited by R.. H. Campbell and A. S. Skinner, Oxford, Clarendon Press, 1979.
• Sterman, 1989: John D. Sterman, Modeling managerial behavior: misperceptions of feedback in a dynamic decision making experiment, Management Science, v.35 n.3, p.321-339, March 1989 [doi>10.1287/mnsc.35.3.321]
• Waterman and Hayes-Roth, 1978: D. A. Waterman , Frederick Hayes-Roth, Pattern-Directed Inference Systems, Academic Press, Inc., Orlando, FL, 1978

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representations (procedural and rule-based)
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Experimentation, Languages, Theory

Keywords:
bucket brigade, classifier system, genetic algorithm, machine learning, triggered operations