Genetic Algorithms and their Applications

Proceedings of the Second International Conference on Genetic Algorithms

John J. Grefenstette

• Publisher: Psychology Press
• Year: 2013
• Topic: Psychology
• eBook ISBN:
  9781134989805
• Subtopic: Cognitive Psychology & Cognition
• Index: Psychology

First Published in 1987. This is the collected proceedings of the second International Conference on Genetic Algorithms held at the Massachusetts Institute of Technology, Cambridge, MA on the 28th to the 31st July 1987. With papers on Genetic search theory, Adaptive search operators, representation issues, connectionism and parallelism, credit assignment ad learning, and applications.

BUCKET BRIGADE PERFORMANCE: I. LONG SEQUENCES OF CLASSIFIERS

Rick L. Riolo

The University of Michigan

Abstract

In Holland-type classifier systems the bucket brigade algorithm allocates strength (“credit”) to classifiers that lead to rewards from environment. This paper presents results that show the bucket brigade algorithm basically works as designed—strength is passed down sequences of coupled classifiers from those classifiers that receive rewards directly from the environment to those that are stage setters. Results indicate it can take a fairly large number of trials for a classifier system to respond to changes in its environment by reallocating strength down competing sequences of classifiers that implement simple reflex and non-reflex behaviors. However, “bridging classifiers” are shown to dramatically decrease the number of times a long sequence must be executed in order reallocate strength to all the classifiers in the sequence. Bridging classifiers also were shown to be one way to avoid problems caused by sharing classifiers across competing sequences.

1 INTRODUCTION

Like all highly parallel, fine-grained, rule-based learning systems, classifier systems ([Holland, 1986a], [Burks, 1986], [Holland and Burks, 1987], [Holland, 1986b]) must solve the apportionment of credit problem. In short, the apportionment of credit problem is the problem of deciding, when many rules are active at every time step, which of those rules active at step t are necessary and sufficient for achieving some desired outcome at step t + n. In terms of Samuel, who first recognized the problem in the context of his checker playing program [Samuel, 1959], the problem is how to know which of the many moves (or sequences of moves) made in the early parts of a game “set the stage” for a triple jump later in the game. The problem of apportioning credit is especially difficult in complex domains in which (a) information about what is a good result is provided only occassionally, perhaps after long sequences of actions, and (b) there are millions of possible states or state sequences, so that the system never sees the same exact sequence twice.

In classifier systems using the bucket brigade algorithm [Holland,1985], credit is allocated in the form of a value, strength, associated with each classifier. The strength assigned to a classifier is important for two reasons:

1. Strength determines in part what classifiers will be active at a given time step, and so controls the short term behavior of the system.
2. Strength is used by rule discovery algorithms to guide the creation and deletion of classifiers, thereby influencing the longer term learning behavior of the system.

Thus for classifier systems both to perform well and to learn, strength must be allocated properly and expeditiously by the bucket brigade algorithm.

Basically the bucket brigade algorithm acts in two ways:

1. It adjusts the strength of those classifiers that are active when a payoff is received from the environment. Each classifier’s strength is changed a little at a time until it is proportional to the average of the payoffs the system receives when that classifier is active.
2. It redistributes strength from each active classifier to classifiers that posted messages that activated it. Each classifier’s strength is modified a little at a time until it is proportional to the strength of the classifier(s) it activates.

Over time the bucket brigade algorithm reallocates strength from classifiers that directly lead to payoffs from the environment to those classifiers that indirectly lead to payoff, i.e., to classifiers that post messages that “set the stage” for those classifiers directly responsible for receiving payoffs.

The bucket brigade has several characteristics that make it ideal for use with highly parallel systems like classifier systems. First, the bucket brigade algorithm uses only local information: when adjusting the strength of a classifier, it only needs to know which classifiers directly activated it and which classifiers it directly activates. There is no need for complicated book-keeping or for high-level critics to analyze sequences of actions and assign credit accordingly. Second, the bucket brigade works in a highly parallel way, changing the strength of many (or all) rules at the same time. Third, the bucket brigade acts incrementally, changing the strength of classifiers gradually. By changing the strength of classifiers only a small amount at a time, the classifier system tends to learn gracefully, without the precipitous changes in performance that may result from making a large change in response to a single, possibly anomolous, case.

One key issue for systems using the bucket brigade algorithm is how fast strength flows down long sequences of classifiers. If a whole sequence of classifiers must be activated many times in order to adjust the strength of a classifier at the beginning of the chain in response to a change in payoff associated with the last step in the sequence, the system’s response to simple changes in its environment will be too slow. Wilson [Wilson, 1986] used a simple simulation to show that allocation down a sequence of classifiers can take a fairly large number of steps. (He suggested an alternative “hierarchical” bucket brigade algorithm that is designed to speed up the flow of credit down long sequences of classifiers.) Holland [Holland,1985] mentions this problem and suggests a way to implement “bridging” classifiers that speed up the flow of strength down a long sequence of classifiers.

This paper describes some simple experiments designed to show how well the bucket brigade is able to allocate strength down long sequences of classifiers. Section 2 describes the CFS-C/FSW1 classifier system, which is used to carry out all experiments described in this paper. In Section 3, the allocation of strength down a single chain of classifiers will be examined. In Sections 4 and 5, the ability of the bucket brigade to allocate strength so that the system learns to make the proper choice at the beginning of a long sequence of steps is examined. The effects of “bridging” classifiers are also examined. In Section 6 the effect of sharing classifiers in different sequences is examined, without and with bridging classifiers.

2 THE CFS-C/FSW1 SYSTEM

All experiments described in this paper were done using the CFS-C classifier system [Riolo, 1986], set in the FSW1 (“Finite State World 1”) task environment [Riolo, 1987). This section describes the parts of the CFS-C/FSW1 system that are relevant to the experiments described in this paper. For a complete description of those systems, see the documentation cited.

Basically, the FSW1 domain is a world that is modeled as a finite Markov process, in which a payoff is associated with some states. The classifier system’s input interface provides a message that indicates the current state of the Markov process. The classifier’s output interface provides the system with a way to alter the transition probabilities of the process, so that the system can control (in part) the path taken through the finite state world. When the classifier system visits states with non-zero payoff, that payoff is given to the system as a “reward”. Thus the task for the CFS-C classifier system in the FSW1 domain is to learn to emit the appropriate signals at each step so that the Marlov process will visit states with higher payoff values as often as possible.

More formally, the FSW1 task domain is fully defined by specifying:

• A set of n states W_i, i = 0, …, n – 1, each with an associated payoff µ(W_i) ε ℜ; one state also is designated the start state.
• A set of probability transition matrices, P(r), where each entry Pij(r) in P(r) gives the probability of going to state W_j, given that the system is in state W_i and that the classifier system has emitted r as its output value (r = 0…15).

Figure 1: A simple FSW1 finite state world.

For example, consider the simple three state world shown in Figure 1. (In this and other diagrams, states are shown as circles, and arrows designate non-zero probability transitions.) W₀ is the start state. The payoff for state W₁ is 100; the payoff for the other states is 0. When the system is in state W₀, if r = 1 the probability of going from state W₀ to W₁ is 1.0; if r = 2 the probability of going from state W₀ to W₂, is 1.0. For other values of r, the probability of going from state W₀ to state W₁ or W₂ is 0. The probability of going from either W₁ or W₂ to W₀ is 1.0, no matter what the value of r. Thus if the classifier system is to maximize its payoff in this world, it must learn to set r = 1 whenever it is in state W₀.

The CFS-C classifier system is a standard, “Holland” type learning classifier system that consists of four basic parts:

• A message list, which acts as a “blackboard” for communications and short term memory. In the CFS-C classifier system, the message list has a small, maximum size.
• A classifier list, which consists of condition-action rules called classifiers. Each classifier in the CFS-C system is a two-condition classifier of the form:
  C₁,C₂ / Action
  A classifier’s condition part is satisfied when each of the conditions C₁ and C₂ is matched by one or more messages on the message...

Table of contents

• Front Cover
• Title Page
• Title Page
• Copyright
• Acknowledgement
• Conference Program
• Finite Markov chain analysis of genetic algorithms
• An analysis of reproduction and crossover in a binary-coded genetic algorithm
• Reducing bias and inefficiency in the selection algorithm
• Altruism in the bucket brigade
• Schema recombination in pattern recognition problems
• An adaptive crossover distribution mechanism for genetic algorithms
• Genetic algorithms with sharing for multimodal function optimization
• The ARGOT strategy: adaptive representation genetic optimizer technique
• Nonstationary function optimization using genetic algorithms with dominance and diploidy
• Genetic operators for high-level knowledge representations
• Tree structured rules in genetic algorithms
• Genetic algorithms and classifier systems: foundations and future directions
• Greedy genetics
• Incorporating heuristic information into genetic search
• Using reproductive evaluation to improve genetic search and heuristic discovery
• Toward a unified thermodynamic genetic operator
• Toward the evolution of symbols
• SUPERGRAN: a connectionist approach to learning, integrating genetic algorithms and graph induction
• Parallel implementation of genetic algorithms in a classifier system
• Punctuated equilibria: a parallel genetic algorithm
• A parallel genetic algorithm
• Genetic learning procedures in distributed environments
• Parallelisation of probabilistic sequential search algorithms
• Parallel genetic algorithms for a hypercube
• Bucket brigade performance: I. Long sequences of classifiers
• Bucket brigade performance: II. Default hierarchies
• Multilevel credit assignment in a genetic learning system
• On using genetic algorithms to search program spaces
• A genetic system for learning models of consumer choice
• A study of permutation crossover operators on the traveling salesman problem
• A classifier based system for discovering scheduling heuristics
• Using the genetic algorithm to generate LISP source code to solve the prisoner’s dilemma
• Optimal determination of user-oriented clusters: an application for the reproductive plan
• The genetic algorithm and biological development
• Genetic algorithms and communication link speed design: theoretical considerations
• Genetic algorithms and communication link speed design: constraints and operators