Classifier Systems and Genetic Algorithms

ARTIFICIAL INTELLIGENCE 235 Classifier Systems and Genetic Algorithms L.B. Booker, D.E. Goldberg and J.H. Holland Computer Science and Engineering, 3116 EECS Building, The University of Michigan, Ann Arbor, MI 48109, U.S.A. ABSTRACT Classifier systems are massively parallel, message-passing, rule-based systems that learn through credit assignment (the bucket brigade algorithm) and rule discovery (the genetic algorithm). They typically operate in environments that exhibit one or more of the following characteristics: (1) perpetually novel events accompanied by large amounts of noisy or irrelevant data; (2) continual, often real-time, requirements for action; (3) implicitly or inexactly defined goals; and (4) sparse payoff or reinforcement obtainable only through long action sequences. Classifier systems are designed to absorb new information continuously from such environments, devising

sets of compet- ing hypotheses (expressed as rules) without disturbing significantly capabilities already acquired. This paper reviews the definition, theory, and extant applications of classifier systems, comparing them with other machine learning techniques, and closing with a discussion of advantages, problems, and possible extensions of classifier systems. 1. Introduction Consider the simply defined world of checkers. We can analyze many of its complexities and with some real effort we can design a system that plays a pretty decent game. However, even in this simple world novelty abounds. A good player will quickly learn to confuse the system by giving play some novel twists. The real world about us is much more complex. A system confronting this environment faces perpetual novelty--the flow of visual information impinging upon a mammalian retina, for example, never twice generates the same firing pattern during the mammal's lifespan. How can a system act other than randomly in such environments? It is small wonder, in the face of such complexity, that even the most carefully contrived systems err significantly and repeatedly. There are only two cures. An outside agency can intervene to provide a new design, or the system can revise its own design on the basis of its experience. For the systems of most interest here----cognitive systems or robotic systems in realistic environments, ecological systems, the immune system, economic systems, and so on--the first option is rarely feasible. Such systems are immersed in continually changing Artificial Intelligence 40 (1989) 235-282 0004-3702/89/$3.50 © 1989, Elsevier Science Publishers B.V. (North-Holland) 236 L.B. BOOKER ET AL. environments wherein timely outside intervention is difficult or impossible. The only option then is learning or, using the more inclusive word, adaptation. In broadest terms, the object of a learning system, natural or artificial, is the expansion of its knowledge in the face of uncertainty. More directly, a learning system improves its performance by generalizing upon past experience. Clear- ly, in the face of perpetual novelty, experience can guide future action only if there are relevant regularities in the system's environment. Human experience indicates that the real world abounds in regularities, but this does not mean that it is easy to extract and exploit them. In the study of artificial intelligence the problem of extracting regularities is the problem of discovering useful representations or categories. For a machine learning system, the problem is one of constructing relevant categories from the system's primitives (pixels,...

Website: deepblue.lib.umich.edu | Filesize: -
No of Page(s): 48
Download Classifier Systems and Genetic Algorithms - Deep Blue at the ....pdf