Evolution of a Clustering Scheme for a Classifier System: Beyond the Bucket Brigade

Thesis Proposal

Patrick Tufts

December 1, 1994

Abstract

The Classifier System is a learning mechanism that explores the space of steps leading to a reward. It credits rules leading to a reward through a temporal difference method called a bucket brigade in which each step passes some of its reward to the step that preceded it.

The bucket brigade rewards all the steps in a chain, given enough time. However, the classifiers in a population are in competition with each other, so delays in rewarding key steps may result in those steps being crowded out by others.

The main hypothesis of this proposal is that the combination of a clustering operator with a classifier system will aid in the formation of long chains. This combination has potential applications for discovering useful variable-length representations for classifier systems, further enhancing their ability to learn, and can be applied to the field of Genetic Programming to discover useful building blocks.

1 Introduction

Learning systems that engage in sequential activity face the problem of crediting those steps that lead to a reward. When the reward is the result of many steps in a sequence, the problem becomes: what is the most efficient and reliable way to credit those steps?

In order to form solutions to problems where the payoff comes after a long sequence of actions, it is necessary to identify the steps that lead to the reward. Classifier systems do this using the bucket brigade mechanism [11]. The bucket brigade works as follows. Each time step, the currently active rules pass a fraction of their rewards to the rules that were active in the preceding time step. If a reward is received in a given time step, the one rule that fired in that time step receives the reward. Given a chain of rules that leads to a reward, each iteration through the chain passes some reward one step back. If the chain is n steps long, then it will take n iterations through the chain before the first classifier receives any reward.

The bucket brigade is closely related to temporal-difference (TD) methods [25], and shares advantages with them over conventional prediction-learning schemes. Like TD learning methods, the bucket brigade learns incrementally. This means that the bucket brigade can perform prediction-learning tasks using less memory and less peak computation than systems that store all cases and then learn over the entire set at once [25].

The bucket brigade implicitly favors short sequences of rules over long ones, making it unlikely that a classifier system will discover solutions that require more than a few steps [38].

I address this problem by developing a scheme for rule clustering [38, 22, 34, 37]. In this scheme, classifiers bid to be grouped with others, forming a collection that reproduces or dies together. Wilson hypothesizes that clustering will allow classifier systems to form longer chains, and thus be able to solve more complex tasks [38, 37].

The clustering operator is based on Koza’s Genetic Programming paradigm [15]. Genetic Programming is an extension to the Genetic Algorithm in which crossover occurs on tree structures rather than fixed-length bit strings.

In this proposed work, I intend to:

1. develop a formal scheme for clustering,

2. work out the theoretical ability of clustering to form long chains,

3. analyze the behavior of traditional classifier systems on difficult problems, and

4. show that experimental evidence bears out the theoretical predictions, 5. show that the combination of Classifier Systems and Genetic Program-

ming is more efficient than either method by itself in learning tasks where reward is infrequent.

2 Classifier Systems

A Classifier System is learning technique in which a collection of initially random rules is updated according to a fitness scheme. The standard classifier system proposed by Holland [11] contains:

• a finite population of classifiers

• a set of inputs

• a set of actions

• a fitness/reward function

• discovery functions: crossover and mutation

• a classifier reinforcement method: the bucket brigade

• a message system

A classifier is a condition/action pair with an associated fitness. If the current set of inputs satisfies the classifier’s conditions, that classifier fires and performs some action.

Learning in a classifier system occurs through reinforcement, recombination, and reproduction.

3 Problem

This section addresses the central problem for both Classifier Systems and Genetic Programming — the recognition of useful steps to the solution of a task. After showing how this problem affects learning systems from these two fields, I will show how a combination of Genetic Programming and a Classifier System can be powerful enough to efficiently recognize those steps that lead to reward.

3.1 Chain formation in Classifier Systems

One of the important aspects of the bucket brigade is that it doesn’t require extensive bookkeeping. The bucket brigade operates locally, reinforcing the connection between a rule and its immediate predecessor.

The bucket brigade keeps track of all classifiers active during the current and the previous time steps. Classifiers that are active in the current step pass a fraction of their strengths back to the classifiers that were active during the previous time step.

If a classifier’s action immediately results in a reward, that classifier’s strength is increased. At every time step, a fraction of the strength of the classifier that fires is passed to the classifiers that were active in the previous time step via the bucket brigade. This translates into a wave of diminishing reward that passes back along the chain of classifiers.

Other reinforcement schemes used in learning systems require a great deal of information about rule activation. The reinforcement mechanisms in LEX and ACT*, for example, keep track of all activated rules preceding a reward [34]. Keeping track of all activated rules may not be feasible when a learning system is operating in a complex, unpredictable domain (autonomous agents, for example).

Maintaining long chains in a classifier system is important for problems that require a large number of steps before receiving a payoff. Some examples of domains where a large number of steps must be performed before payoff are: food foraging [33], chess [21], and backgammon [28]. There are two weaknesses of long chains: they are hard to maintain (the reinforcement problem), and they are hard to generate in the first place. [38] Furthermore, the genetic component of the classifier system and the bucket brigade may interact in unpredictable ways, leading to the destabilization of correct solutions [3].

3.1.1 Reinforcement

One of the problems with maintaining a long chain is the time it takes to reinforce the early members in a chain. Specifically, if the fraction of an activated classifier’s strength paid to the classifier that preceded it is c (typically, c = .1 [34, p. 108]), and there are n classifiers in the chain, then the last classifier in the chain will have to be activated on the order of n/c times before the first classifier in the chain is fully reinforced.

Let n and c be as above. For the first classifier to reach 90% of the strength of the nth, the lower bound on the number of time steps t is given by the following equation [34] (see section 6.1 for its derivation):

t = \frac{3 + 1.2n}{c}  (1)

For n = 10, c = .1, t = 150 steps. Since the selection function kills off the least fit classifiers every time step, the earliest classifiers in a chain rarely stay around long enough to receive any reinforcement.

Note that equation 1 is only a lower bound because it assumes that there is only one active classifier in any time step, and it ignores randomness in rule selection.

Wilson and Goldberg propose two ways to work-around to the reinforcement problem [38].

• decompose action sequences into modules

• introduce a new operator so classifiers can cluster into groups

3.1.2 Generation

Not only are long chains hard to maintain once they arise, but they’re also difficult to generate in the first place. According to Wilson [38], very few classifier systems have ever formed chains.

The problem with generating long classifier chains lies in the methods for discovering and forming classifiers. Classifiers are formed by using the genetic algorithm to search through the space of possibilities.

When there are several different problems in a task, classifiers that solve one problem may not contain schemata to solve other ones. When this is the case, unrestricted crossover creates classifiers that solve neither problem [31].

3.1.3 Cooperation and Competition

Because, by definition, the early classifiers in a chain are further from the reward, they usually have a lower strength than the rules they activate. Later rules in a chain tend to be stronger than earlier ones.

Since all the rules are in competition with each other, this leads to the cooperator/competitor problem.

• early rules depend on the activation of later ones for a payoff.

• later rules depend on early ones to set the stage for their activation.

• all the rules in the population compete with each other based on their strength.

• since later rules tend to be stronger than earlier ones, they crowd out the early rules and thus weaken themselves.

The shorter the chain, the less likely it is that there is an imbalance of the strengths of its classifiers. Since short chains are less likely to encounter the cooperator/competitor problem, the traditional classifier system implicitly favors short chains over long ones.

In summary, long chains are often necessary to solve a problem, and yet are selected against by a classifier system in the ways outlined above. Given that some problems require many steps before a reward is reached, what can we do to encourage the formation the long chains while keeping the simplicity of the classifier system?

3.2 Building blocks and Genetic Programming

In the Genetic Programming (GP) paradigm, programs are evolved in a manner analogous to the genetic algorithm. Where the genetic algorithm (GA) uses fixed length representations (usually bit strings), GP uses a hierarchical, extensible representation [15].

GA crossover corresponds to sub-tree swapping in GP. GA mutation corresponds to mutating a single node in a GP tree.

One problem with GP is — how can useful subtrees in a population be identified and protected from crossover? Crossover acts to swap two randomly selected subtrees from two members of the population. If the swap point occurs within a good subsolution, the resulting program is likely to be less fit than its parents [31].

Several methods have been proposed to identify useful subtrees and protect them from crossover.

• Automatically Defined Functions

Automatically Defined Functions (ADFs), proposed by Koza [16], introduce a constrained syntax into GP. The ADF template constrains members of the population to have a result-producing branch and a function definition branch. The difference between GP without and with ADFs is as follows:

– Without ADFs, each member of the population produces a result that is then evaluated.

– With ADFs, each member produces a result that is evaluated, and also defines one or more functions.

The problem with ADFs is that the experimenter must decide how much regularity to impose on the system in two ways:

1. the number of ADFs a program can create

2. the set of terminals and functions associated with each ADF

The choices the experimenter makes for each of the two constraints above determine how tightly the learning system is constrained to a particular form of solution. As an example, in an experiment where the system was to learn a 4-input multiplexer, Kinnear constrained each solution to have three ADFs, each with a different function and terminal set [13].

The approach proposed here allows the system to create modules as necessary to form reliable chains. The grouping of terminals and functions as specified in ADFs is expected to occur normally in the proposed system as part of the chaining process.

• Module Acquisition

Module Acquisition (MA) is a system for Genetic Programming in which random subtrees in a population of programs are selected, encapsulated, and placed in a global module library [1, 13]. The encapsulation process replaces a subtree in a program with a function name, and adds the named function and definition to the library.

During encapsulation, the tree may be trimmed to an arbitrary depth, creating a parameterized module. The nodes below the trim point become the arguments to the newly defined function.

Modules in the library do not evolve, and are kept as long as any member of the population refers to them. The initial encapsulation [15, 110-112] results in a single reference to the encapsulated module: the reference in the function from which the subtree was taken. If the module provides a benefit to new programs when brought in through the crossover operator, then the number of references to it in the population will increase.

Kinnear has shown Module Acquisition to be inferior to ADFs for one learning problem (even 4-parity, [13]). Because Module Acquisition occurs randomly, it may be less likely to discover useful subcomponents.

I believe that GP combined with chaining will be more efficient at discovering modules because it can identify the building blocks of those modules through chaining. Measuring the utility of pieces and creating larger ones from them seems to be a better approach than forming entire solutions and then randomly decomposing them into potential building blocks.

4 Prior art dealing with long chains

In this section I describe research into using various rule-clustering schemes in classifier systems. I also mention a reinforcement algorithm used by Drescher [6] for his schema mechanism, a system with some of the properties of a classifier system, and touch on some of the ways that two other reinforcement learning techniques — Q-learning [32] and temporal difference (TD) learning [24, 25] — deal with learning multi-step actions in domains with infrequent reward.

• Hierarchical Credit Allocation

Hierarchical Credit Allocation (HCA), proposed by Wilson [34], is a scheme where classifiers post and match messages that occur at different levels. By making the message system into a hierarchy, Wilson brings in a way for higher level classifiers to invoke lower level ones.

There is no notion of a genetic operator working on hierarchies of classifiers. The hierarchy is only exploited in activation and reinforcement. The classifiers fall into hierarchies depending on what messages they respond to. There is no operator that can in general take a sub-hierarchy and insert it into another hierarchy.

HCA is additionally constrained to the same fixed-length representation used by other classifier systems. The system proposed here allows the representation to change dynamically, adapting to the particular problem. In this respect, the proposed system is similar to the one proposed in [37].

• Hierarchically Structured Classifier System

In a Hierarchically Structured Classifier System (HCS), described in [22], classifiers are grouped into clusters through a relationship operator. Crossover can occur between individuals in a cluster and also between two clusters. Crossover between clusters is given a higher probability than crossover within a cluster.

Individuals are fixed-length representations, and the initial grouping of classifiers is done randomly. The fitness of a classifier is directly proportional to the sum of the fitnesses of classifiers within its cluster.

There is no mutation in HCS. If there are no schemata in the initial random population to cover the solution space, there is no way for them to arise.

Additionally, HCS assumes that clustering is beneficial to solving a problem. If applied to tasks in which clustering is of no benefit (the Boolean Multiplexer, for instance [7, p.293]), HCS would spend much time on unnecessary operations: calculating the fitness of clusters and performing crossover between clusters.

• bridging classifiers

A bridging classifiers is one that stays active from the start to the finish of a chain, and thus passes reward directly back to the beginning of the chain in a single time step.

                    +--B--C--D--+
                    |           |
                A---+           +---E
                    |           |
                    +-----F-----+

Figure 1: A bridging classifier

In figure 1, the chain is the sequence A → B → C → D → E is the chain, and F is the bridging classifier. Note that A → F → E on its own will not work. F happens to remain active at the same time as B → C → D, but does not actually set up the conditions for E to occur.

Holland theorized that bridging classifiers would: 1) arise on their own to 2) support long chains [10]. Riolo tested the second part of this hypothesis and found that, given the existence of bridging classifiers, learning does occur more rapidly [19]. I have not found any examples of bridging classifiers arising on their own in the literature.

5 Proposal — hierarchical clustering

I propose that a clustering mechanism based on Genetic Programming can have the same benefit for Classifier Systems as previous clustering schemes, while providing many new benefits for GP, namely:

• useful subtree identification

• efficient agglomeration of subtrees into fit modules

• caching of evaluated results of frequently used subtrees

• cooperation between trees

The idea is that Classifier Systems are good at identifying short chains of rules, while Genetic Programming suffers from not having a mechanism to give credit to useful subtrees.

At the same time, Genetic Programming is good at recognizing the fitness of trees of arbitrarily large size, while Classifier Systems using the bucket brigade algorithm have trouble recognizing the fitness of chains of rules of arbitrary size.

5.1 Implementation of GP/CS

• begin with a classifier system of depth one Lisp expressions.

• when two expressions chain, they form a depth two Lisp expression (a progn, for example).

• Lisp expressions of depth 2 and greater can recombine using the GP crossover operator.

An implementation of this system for classification of data might look like Figure 2. A number in the action column indicates a category the system has chosen for the input data. “Temp” means that the system takes the result of the S-expression and makes it available as an input in the next timestep.

One way to implement clustering would be to put two rules (C_{t−1} and C_{t}) into a cluster when the following are true:

• the rules have roughly the same strength

• C_{t} has reinforced C_{t−1} more than n percent of the time that C_{t} has been active (where n is a measure of the reliability of the reinforcement).

6 Theory of hierarchical clustering

In this section, I describe some of the theory behind existing hierarchical clustering systems, and the propose how I intend to extend this work with GP clustering.

Initial Population:
S-expression            Action
------------            ------
(iflte x3 x1)             2
      .                   .
      .                   .
      .                   .
(+ x1 x4)                temp
After Clustering:
S-expression            Action
------------            ------
(iflte x3 (+ x1 x4))      1
      .                   .
      .                   .
      .                   .

Figure 2: An example of grouping in the proposed system.

6.1 The Bucket Brigade

Equation 1 says that it takes O(n) time to form a chain of length n. A chain here means a sequence of classifiers in which a reward passes from one end to the other. The length of the chain is the number of classifiers within the chain, and the degree of coupling is given by the following equation.

Let C_{1} … C_{n} be the classifiers in a chain, and S(C_{i}) be the strength of a given classifier i. Furthermore, let M be the maximum observed strength of all classifiers in a population (not just those in the chain) at a given time step.

Then the theoretical degree of coupling for a given chain is:

\frac{S(C_{n}) − S(C_{1})}{M}  (2)

The above is an only an upper bound because the reinforcement The imbalance of a chain is the difference in strengths of the first and last classifiers in a chain.

Wilson derives the equation for the time to bring the first step in an n step chain to within 90% of the last step as follows (the derivation given below is Wilson’s [34], with minor changes).

Let a bucket brigade sequence of length n be represented by a list of n elements, each initialized to a strength of zero. We represent one repetition of the whole sequence by having each element i pass a fraction of its strength to the previous element in the chain:

S_{i}(t + 1) = S_{i}(t) − cS_{i}(t) + cS_{i+1}(t)  (3)

where the strength of the last element n, which receives a payoff R from the environment, is given by

S_{n}(t + 1) = S_{n}(t) − cS_{n}(t) + R  (4)

6.2 Bucket Brigade with Clustering

If clustering occurs between two classifiers after r reinforcements, then the time to reinforce a chain of length n becomes

t = r + (n − 1)  (5)

That is, it takes r steps for C_{n} and C_{n−1} to merge into a single node. The remaining nodes, C_{n−k} (k = 2 … 9) have been reinforced r − k times, respectively. Each time step after t = r, an additional classifier will become clustered with the ones that preceded it.

Going back to the example from equation 1, it will now take r + (n − 1) steps for the classifiers to form a single unit — a cluster, here, as opposed to a chain.

Since r + (10 − 1) ≤ 150 for r ≤ 141, whenever r < 141 a sequence of 10 classifiers will cluster faster than the bucket brigade can form a chain.

By introducing clustering, it is possible for a chain of classifiers to become highly coupled and balanced (as defined in section 6.1).

7 Experimental validation

7.1 Boolean Multiplexer

In the Boolean multiplexer problem, the system is presented with a string of bits and must generate the correct 1-bit output. For the 6-multiplexer problem, the string is 6 bits. The correct output is determined by treating the first 2 bits as an index into the remaining 4. For example, if the string is 001000, the the first two bits point to “location” 00 of the string 1000. For the 11-multiplexer problem, the first 3 bits are an index into the remaining 8.

The Boolean multiplexer is a good problem to test the clustering mechanism for two reasons. First, it is a standard problem for learning and optimization schemes. Second, the problem is scalable.

The Boolean multiplexer problem is a common benchmark for comparing different learning systems. Both Genetic Programming [15] and Classifier Systems [33, 4] have been applied to it. In addition, connectionist networks and decision trees have been applied to the problem according to [4].

The 11-multiplexer problem has a search space of approximately 10^{616} [15, p. 170].

7.2 Animat

The Animat problem, first proposed by Wilson [33], is one where an artificial agent moves about on a two-dimensional surface searching for food. The agent can sense its local environment, and chooses an action based on the classifiers that match its current sensors.

The field of Animat research is a part of the larger area of behavior based AI [17]. Behavior based AI the study of how to construct intelligent systems from the bottom up.

In the Animat problem, the environment can be structured so that the distance between any two food items is great enough that the agent must cope with learning where reward comes only after a large number of steps [35].

Animat learning is a good application for Genetic Programming using Classifier Systems for subtask discovery for the following reasons:

• Animats receive infrequent rewards; A good reinforcement scheme is a must.

• Animats and classifier systems are strongly associated. A demonstration of a hypothesized improvement to the classifier system within the Animat domain means the results of the theory can be compared with other results in the same field.

Furthermore, the Animat problem has been studied to some extent by the TD community [26], providing a point of comparison between the bucket brigade and other temporal difference algorithms. TD methods are optimal in the simplest Animat environments, learning the task more quickly than their bucket brigade cousins. Wilson hypothesizes that an an extended classifier mechanism similar to the one described in this proposal will prove superior to TD in more complex environments [37, 36].

7.3 Algorithm Discovery — Sorting

The problem of sorting inputs is an ideal application for a Genetic Programming system that uses a Classifier System to identify useful subtrees. Experiments by Hillis [9], Kinnear [14] and the author [31] indicate that variable length representations are a better choice than fixed-length methods for the problem. Furthermore, a hierarchical representation is appropriate given that the steps to the solution are coupled — later steps depend on the results of earlier ones for success.

Given these features of the problem: variable length, hierarchical representation, and dependence of later steps on earlier ones, I believe that this problem is a fruitful one for investigation using a merger of Genetic Programming and a Classifier System.

The problem is good for other reasons as well. While the theory of sorting is well known and well studied, the invention of efficient sorting networks lies in the area between endeavors for which humans are the best and those for which machines excel. Recent experiments by Drescher [5] and Thearling [29] have confirmed the experiments of Juille and Tufts [31] that machines can generate sorting networks that are as efficient as the best human-built ones.

Hillis combined two populations, one of sorting networks and one of test cases, in a predator/prey model of competition [9]. Hillis introduced predators into his model in order to prevent premature convergence. These predators are collections of test cases, and evolve in parallel with the sorters. Hillis found the predator scheme was more effective than using a fixed subset of the test cases. With fixed test cases, his system evolved a 65 comparator network. With a separate population of evolving test cases, his system created a 61 comparator network. In his experiments, Hillis initialized his population with the first 32 steps of Green’s sorter, leaving the GA to flesh out the second half of the network.

Belew and Kammeyer published a one page description of their work [2] generating sorting networks using grammars.

Ryan [20] applied a Genetic Programming approach to the problem of 9-input sorting networks. Kim Kinnear also used GP, but in the area of adaptive sorting algorithms, to find an algorithm to sort n elements in O(n^{2}) time [14]. It’s important to note that these two problems — 9-input sorting networks and O(n^{2}) adaptive sorting algorithms — are not very difficult, but are included here to show the range of potential applications of GP. The author has used an approach related to GP to generate efficient 16-input sorters. The space of 16 input networks is roughly 40 orders of magnitude larger than the space of 9 input networks [31].

7.3.1 The Size of the Space

The upper bound for the size of the search space for sorting networks is as follows [31].

For an n-input network, there are:

\frac{n(n − 1)}{2}  (6)

possible comparisons a given comparator can perform on the inputs.

The space of all networks (sorting and non-sorting) with c comparators and n inputs is:

(\frac{n(n − 1)}{2})^{c}  (7)

For n = 16, there are 120^{c} possible comparators. Even if we restrict our search to networks of just 60 comparators, the space is still too large to search exhaustively.

8 Classifier GP

Genetic Programming has been applied to such problems as pattern classification [23], plan generation [8], image recognition [27] and classification [12], induction on large databases [31], discovery of adaptive sorting algorithms [14], and stack filter optimization [18].

The addition of a classifier structure to the Genetic Programming paradigm can potentially lead to the following improvements in GP.

• caching of evaluated subtrees

• method of “taking apart” large trees into individual rules

9 Schedule

This is my proposed timeline for work on the theory and experiments for Genetic Programming with Classifiers. A large part of the coding and some of the experiments have already been done.

I have written a package [30] based on Koza’s GP kernel [15] to run largescale experiments on a CM-5 and have used GP to perform classification and prediction on a 2 gigabyte database as part of a research project at Thinking Machines.

I have also written up experiments using a variable-length genetic representation to evolve sorting networks [31]. The representation used in these experiments for genetic operations are isomorphic to those used in Genetic Programming.

The largest coding job left is to combine GP with a classifier system. This is possible with minimal changes to the GP code already developed.

The theory of GP with CS needs to be developed. I expect this will require more time than any remaining coding.

Following the implementation of code and the development of the theory, the experiments I will perform are:

• comparison of system to ADF and MA

• comparison of system to HCS

9.1 Time Line

month goal  status
Sep data-parallel GP done
GP and Classification Trees  prelim. expts [30]
sorting networks  prelim. expts [31]
GP with classifier system  coding
Oct  Theory: GP & CS compute complexity
Nov  Theory: GP & CS chain formation
Jan  GP: comparison to ADF and MA
Feb  CS: comparison to HCS
Mar draft of thesis
May revised draft

References

[1] Peter J. Angeline. Genetic programming and emergent intelligence. In Kenneth E. Kinnear, Jr., editor, Advances in Genetic Programming, chapter 4, pages 75–97. MIT Press, 1994.

[2] Richard K. Belew and Thomas Kammayer. Evolving æsthetic sorting networks using developmental grammars. In Stephanie Forrest, editor, Proceedings of the Fifth International Conference on Genetic Algorithms, San Mateo, California, 1993. Morgan Kauffmann.

[3] M. Compiani, D. Montanari, and R. Serra. Learning and bucket brigade dynamics in classifier systems. In Stephanie Forrest, editor, Emergent Computation (Special Issue of Physica D), pages 202–212. MIT/North-Holland, 1991.

[4] Lawrence Davis, Stewart Wilson, and David Orvosh. Temporary memory for examples can speed learning in a simple adaptive system. In Jean-Arcady Meyer, Herbert L Roitblat, and Stewart W. Wilson, editors, From Animals to Animats 2, pages 313–320. MIT Press, 1993.

[5] Gary Drescher. Personal communication, 1994. Hillclimbing experiments with sorting networks.

[6] Gary L. Drescher. Made-up minds: A Constructivist Approach to Artificial Intelligence. MIT Press, 1991.

[7] David E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley, 1989.

[8] Simon G. Handley. The automatic generation of plans for a mobile robot via genetic programming with automatically defined functions. In Kenneth E. Kinnear, Jr., editor, Advances in Genetic Programming, chapter 18, pages 391–408. MIT Press, 1994.

[9] W. Daniel Hillis. Co-evolving parasites improve simulated evolution as an optimization procedure. In Chris Langton et al., editors, Artificial Life II. Addison Wesley, 1992.

[10] John Holland. Properties of the bucket brigade algorithm. In Proceedings of the First International Conference on Genetic Algorithms and Their Applications, pages 1–7. Lawrence Erlbaum Associates, 1985.

[11] John H. Holland, Keith J. Holyoak, Richard E. Nisbett, and Paul R. Thagard. Induction: Processes of inference, learning, and discovery. MIT Press, 1987.

[12] Michael Patrick Johnson, Pattie Maes, and Trevor Darrell. Evolving visual routines. In Rodney Brooks and Pattie Maes, editors, Artificial Life IV, pages 198–209. MIT Press, 1994. Draft proceedings.

[13] Kenneth E. Kinnear, Jr. Alternatives in automatic function definition: A comparison of performance. In Kenneth E. Kinnear, Jr., editor, Advances in Genetic Programming, chapter 6, pages 120–141. MIT Press, 1994.

[14] Kim Kinnear. Generality and difficulty in GP: Evolving a sort. In Stephanie Forrest, editor, Proceedings of the Fifth International Conference on Genetic Algorithms, San Mateo, California, 1993. Morgan Kauffmann.

[15] John R. Koza. Genetic Programming: on the programming of computers by means of natural selection. MIT Press, 1992.

[16] John R. Koza. Scalable learning in genetic programming using automatic function definition. In Kenneth E. Kinnear, Jr., editor, Advances in Genetic Programming, chapter 5, pages 99–117. MIT Press, 1994.

[17] Pattie Maes. Behavior-based artificial intelligence. In Jean-Arcady Meyer, Herbert L. Roitblat, and Stuart W. Wilson, editors, From Animals to Animats II. MIT Press, 1992.

[18] E. H. N. Oakley. Two scientific applications of genetic programming: Stack filters and non-linear equation fitting to chaotic data. In Kenneth E. Kinnear, Jr., editor, Advances in Genetic Programming. MIT Press, 1994.

[19] Rick L. Riolo. Bucket brigade performance: I. Long sequences of classifiers. In Genetic Algorithms and Their Applications: Proceedings of the Second International Conference on Genetic Algorithms, pages 184–195. Lawrence Erlbaum Associates, 1987.

[20] Conor Ryan. Pygmies and civil servants. In Kenneth E. Kinnear, Jr., editor, Advances in Genetic Programming. MIT Press, 1994.

[21] A. L. Samuel. Some studies in machine learning using the game of checkers. In Edward A. Feigenbaum and Julian Feldman, editors, Computers and Thought, pages 71–105. McGraw-Hill, 1981. Reprint of the 1963 edition.

[22] Lingyan Shu and Johnathan Schaeffer. HCS: Adding hierarchies to classifier systems. In Richard K. Belew and Lashon B. Booker, editors, Proceedings of the Fourth International Conference on Genetic Algorithms, pages 339–345, San Mateo, CA, 1991. Morgan Kauffmann.

[23] Eric V. Siegel. Competitively evolving decision trees against fixed training cases for natural language processing. In Kenneth E. Kinnear, Jr., editor, Advances in Genetic Programming, chapter 19, pages 409–424. MIT Press, 1994.

[24] Richard. S. Sutton. Temporal Credit Assignment in Reinforcement Learning. PhD thesis, UMass Amherst, 1984.

[25] Richard. S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning, 3:9–44, 1988.

[26] Richard S. Sutton. Reinforcement learning architectures for animats. In Jean-Arcady Meyer and Stewart W. Wilson, editors, From Animals to Animats, pages 288–296. MIT Press, 1991.

[27] W. A. Tackett. Genetic programming for feature discovery and image discrimination. In Stephanie Forrest, editor, Proceedings of the Fifth International Conference on Genetic Algorithms. Morgan Kauffmann, 1993.

[28] Gerald Tesauro. Practical issues in temporal difference learning. Machine Learning, 8:257–277, 1992.

[29] Kurt Thearling. Personal communication, 1994. GA experiments with sorting networks.

[30] Patrick Tufts. Parallel case evaluation for genetic programming. In Daniel L. Stein and L. Nadel, editors, 1993 Lectures in Complex Systems, volume X of Santa Fe Institute Studies in the Science of Complexity. Addison-Wesley, 1993.

[31] Patrick Tufts and Hugues Juille. Evolving non-deterministic algorithms for efficient sorting networks. presented at ALife IV poster session, April 1994.

[32] Chris Watkins. Learning from Delayed Rewards. PhD thesis, Cambridge University, 1989.

[33] Stewart W. Wilson. Classifier systems and the animat problem. Machine Learning, 2(3):199–228, 1987.

[34] Stewart W. Wilson. Hierarchical credit allocation in a classifier system. In Lawrence Davis, editor, Genetic Algorithms and Simulated Annealing, Research Notes in Artificial Intelligence, chapter 8, pages 104–115. Morgan Kauffmann, Los Altos, CA, 1987.

[35] Stewart W. Wilson. The animat path to AI. In Jean-Arcady Meyer and Stewart W. Wilson, editors, From Animals to Animats, pages 15–21. MIT Press, 1991.

[36] Stewart W. Wilson. Personal communication, September 1994. E-mail.

[37] Stewart W. Wilson. ZCS: A zeroth level classifier system. Evolutionary Computation, 2(1):1–18, 1994.

[38] Stewart W. Wilson and David E. Goldberg. A critical review of classifier systems. In J. David Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms, San Mateo, CA, 1989. Morgan Kauffmann.