Classifier Systems

A classifier system (sometimes referred to as adaptive agents) is a specialized application of genetic algorithms. It is essentially a way to make genetic algorithms more adaptive to a dynamic environment. (If you are unfamiliar with genetic algorithms I suggest you read this page first.)

Examples of use could be an autonomous vehicle that must navigate without outside interference, or control of a complex network of gas pipes.

One possible method for making such systems work is to categorize their environment and deploy rules accordingly. This is a very human way of looking at the world: we always categorize our environment into categories and subcategories. When certain situations occur we try to apply the rules that seem most appropriate.

A classifier system has the ability to categorize its environment and create rules dynamically, thus making it able to adapt to differing circumstances on the fly.

Ingredients of a CS

On an abstract level a CS contains these things:

1. An environment. This is just the conceptual framework the system works within. It is of course defined by the problem.
2. Input data from the environment. This is the data that we use to formulate appropriate rules.
3. Rules that describe what to do in different circumstances (these circumstances are what the input data describe).
4. The usual GA methods of selection by fitness, recombination by cross-over, and mutation.

Probably the most illustrating example of environment and input data is nature itself: every animal in nature has to find a suitable behaviour or it won't survive very long.

Example 1: When to chase the mailman

Did you ever wonder why dogs chase the mailman? Certainly the dogs seem to find good reason for it. But some dogs chase and others don't. Let's make a system to find out whether or not to chase the mailman.

Mailmen come in many different shapes and sizes, and for our purposes we say that it is the appearance of the mailman that decides whether or not the dog should chase. In other words, the problem is: "Which action is best in relation to different types of mailmen?".

So what we have is (compare with above):

1. The environment is a simple universe that consists of dogs waiting for the mailman.
2. The input data is a steady stream of (different types of) mailmen coming to deliver mail.
3. We want to find rules that tell us what the dogs should do when confronted with different types of mailmen.
4. We use a genetic algorithm to iterate on the rules. By default we have just random rules. We continually select and refine the best of those rules into even better rules.

Classifying the mailmen

As always, we must find a way to represent the problem mathematically. The appearance of the mailman is what decides which rule to use, so let's find the attributes that define a mailman. Here they are:

• How big is he?
• How fast can he run?
• Is he scared of dogs? (dogs can smell fear)
• Is he carrying an Uzi machinegun?

Using these attributes we can come up with a number of different mailman types (2^4 = 16 types). Here's an example of one certain type (1 is true, 0 is false):

    BIG   FAST  SCARED   UZI
     1      1      0      0

This mailman is big, fast, not scared of dogs, and not carrying an Uzi.

Adding the rules

Each category of mailman must have a rule that describes how the dog should respond. This rule is not designed in advance - the trick is to let the system find the best rules by a guided trial-and-error process via the genetic operations. Typically we start from scratch (random rules).

A rule can be defined like this:

    IF [category] THEN [action]

The action is based on a number of predefined choices. In our example the following choices are possible (the choices here are mutually exclusive, but you could design a CS that gave you more than one choice):

• Chase mailman
• Run away
• Do nothing

Here's the clever part: we represent the rules as just another part of the "gene string". For example, here's a representation of the rule "IF big AND not fast AND scared AND no Uzi THEN chase":

    BIG   FAST  SCARED   UZI   /  CHASE   FLEE   STAY
     1      0      1      0    /    1      0      0

And here's a representation of the more general rule "IF has Uzi THEN flee" (# is a "don't care" symbol):

    BIG   FAST  SCARED   UZI   /  CHASE   FLEE   STAY
     #      #      #      1    /    0      1      0

The rules in the two examples are denoted as 1010/100 and ###1/010, respectively.

Making it "genetic"

You can probably see where this is leading to. We can treat the rules as 7-bit strings. If we have a number of these strings we can perform "genetic" operations on them. So that is exactly what we will do. We make a "genetic population" of these 7-bit strings.

You can think of the individual strings in the population as a particular dog's response to a particular mailman.

We have to supply the CS with a stream of input data that enables it to try out rules for all types of mailmen (in another CS you might not want to develop rules for every possible category, but we do here). We have basically two choices: design the input data in advance, or rely on the probability of the GA to come up with new mailman categories via cross-over. I don't know which is best - it depends on your preferences and the other parameters of the GA (population size, cross-over method, etc.).

The important thing is that the same mailman category is present more than once. Since the GA works by a guided trial-and-error process, it needs to try different rules on the same category.

We must have some idea in advance of what are good and bad solutions. Generally we don't want the dogs to hurt themselves or waste unnecessary energy. These general principles must be incorporated into the fitness function, so that it assigns a high fitness to some rules and low fitness to others. This is the way we test which rules are best for a given category.

If, for example, we get a rule that says the dog tries to chase the mailman, even though we know it cannot catch him, the fitness assigned to the rule should be low. This diminishes the rule's chances of being selected for mating with other rules, so future dog generations will be less inclined to pursue this strategy.

Using these measures of assigning fitness, our system would probably after some time propose rules like these as the best rules:

• IF big AND not fast THEN do nothing (we can catch him but he might beat us up)
• IF not big AND not fast THEN chase (we can catch him and not get beaten ourselves)
• IF fast AND scared THEN do nothing (he'll run away, and he's fast)
• IF fast AND not scared THEN chase (he's fast, but he won't run)
• IF has Uzi THEN flee (he's got a gun, better run away)

This "dog and mailman" problem is sufficiently simple that we can map all rules in advance. The problem actually scales down to several equations with several unknowns, and we might as well solve it using simple mathematics. However, if we had a more complex problem with unclear preferences we wouldn't know in advance what the rules should be. Then a CS would be truly usefull. It might even give us rules we would never have thought of by ourselves.

Example 2: A Mars buggy

Another example problem is a autonomous Mars buggy that must decide on its own what to do. For example whether to turn right or left to avoid obstacles, climb over them, or back away. And what to do in a dust storm. And when to collect samples. Etc., etc., etc.

Of course, should you choose to use a CS for a Mars buggy, you would not let it make up its own rules on Mars. In stead you would let it drive around in a simulated environment in your laboratory. The finding of best rules are a trial-and-error process, and you would only have one chance on Mars. When the buggy had developed appropriate rules for its behaviour, you would send it off.

You could choose to just implement those rules as a static set of rules. However, if you cannot plan for every eventuality, it would be a good idea to keep the ability to create new rules via a CS (or another adaptive learning system).

In any case, there are some rules that would probably always be the same (like "Don't drive off a vertical edge"). It would be a good idea to hardcode those rules, so that the CS cannot change them.

Applications for classifier systems

I've given a couple of examples above what a CS could be used for. Generally, a CS is well suited for areas such as machine learning and inductive expert systems. These areas comprise problems which must develop their own rules.

There are lots of different variants of CS's, and it is an area of computer science that is still developing rapidly. An interesting variant is a CS where the individuals in the genetic population interact with each other. For example a prey-predator system where the actions of the individuals (partially or completely) depend on what the other individuals are doing and where they are. This is a form of artificial life.