| Learning Classifier Systems (LCS) [Holland, 1976] are a machine learning technique which combines evolutionary computing, reinforcement learning, supervised learning or unsupervised learning, and heuristics to produce adaptive systems. They are rulebased systems, where the rules are usually in the traditional production system form of “IF state THEN action”. An evolutionary algorithm and heuristics are used to search the space of possible rules, whilst a credit assignment algorithm is used to assign utility to existing rules, thereby guiding the search for better rules. The LCS formalism was introduced by John Holland [1976] and based around his more wellknown invention – the Genetic Algorithm (GA)[Holland, 1975]. A few years later, in collaboration with Judith Reitman, he presented the first implementation of an LCS [Holland & Reitman, 1978]. Holland then revised the framework to define what would become the standard system [Holland, 1980; 1986a]. However, Holland’s full system was somewhat complex and practical experience found it difficult to realize the envisaged behaviour/performance [e.g., Wilson & Goldberg, 1989] and interest waned. Some years later, Wilson presented the “zeroth-level” classifier system, ZCS [Wilson, 1994] which “keeps much of Holland’s original framework but simplifies it to increase understandability and performance” [ibid.]. Wilson then introduced a form of LCS which altered the way in which rule fitness is calculated – XCS [Wilson, 1995]. The following decade has seen resurgence in the use of LCS as XCS in particular has been found able to solve a number of well-known problems optimally. Perhaps more importantly, XCS has also begun to be applied to a number of hard real-world problems such as data mining, simulation modeling, robotics, and adaptive control (see [Bull, 2004] for an overview) and where excellent performance has often been achieved. Further, given their rule-based nature, users are often able to learn about their problem domain through inspection of the produced solutions, this being particularly useful in areas such as data mining or safety-critical control for example. However their combination of two machine learning techniques and potentially many heuristics means that formal understanding of LCS is non-trivial. That is, current formal understanding of, for example, Genetic Algorithms and Reinforcement Learning is significant but understanding of how the two interact within Learning Classifier Systems is severely lacking. The purpose of this volume is to bring together current work aimed at understanding LCS in the hope that it will serve as a catalyst to a concerted effort to produce such understanding.
The rest of this contribution is arranged as follows: Firstly, the main forms of LCS are described in some detail. A number of historical studies are then reviewed before an overview of the rest of the volume is presented. See [Barry, 2000] for more on early LCS. |