Learning Classifier System

General description and introduction

This program is a demonstration of a Learning Classifier System (LCS). The task of this system is guessing the color of tiles on a board. Adaptation to the pattern of colors on the board is achieved by a combination of two simple mechanisms.

The main part of the system is a collection of classifiers. In reaction to a query about a tile, some classifiers become active. The classifier which has been the most useful (has the highest strength) in the past gives an answer. If the answer is correct, the classifier is rewarded (its strength – usefulness grows). Furthermore, classifiers which answered earlier and helped currently active classifier give the correct answer, also get credit (paid by the currently active classifier). All classifiers must pay in each iteration for a "living" (this mechanism eliminates completely useless classifiers). The second mechanism is the Genetic Algorithm. It operates on the strengths of the classifiers, killing the weakest ones and trying to perfect the good patterns by crossing over and mutating them. It also introduces variation by mutation.

CFS – Classifier System

A basic Classifier System, according to John Holland, consists of:

• environment
• input
• output
• a system which has input, output and exists in the environment

The most primitive CFS has input, output and messages that flow between them, which are generated according to existing rules. Those rules are called classifiers. Messages are strings built from the {0,1} alphabet.

Classifiers are in the form of: IF cond-1 AND cond-2 AND ... AND cond-N THEN action.
Which can be written as: cond-1,cond-2,...,cond-N / action.

Conditions and action are strings based on the {0,1,#} alphabet. A message matches conditional part of the classifier if all 0's and 1's are in the same positions in both strings. The "#" sign is the "don't care" symbol – a wild-card.
Example: Message "00110011" fits the "0011#0## / ####1000" classifier.

If a classifier matches any messages on the messages list, it posts a new message onto this list as defined in its action-part. Here, "#" is a pass-through operator: it copies a bit from the matched message. Using example from the previous paragraph: the classifier would post "00111000".

Fig. 1. A basic Classifier System.

The main CFS cycle:

1. Activate the input interface and post incoming input messages to the message list.
2. Match condition parts of all classifiers against the message list.
3. Activate all fireable classifiers and add the messages they generate to the message list.
4. Activate the output interface. Remove output messages from the message list and perform the actions they describe. Go to 1.

LCS – Learning Classifier Systems

LCS is a CFS with adaptation mechanisms. There are two ways in which we can adapt (i.e., improve the performance of) a CFS:

• Adaptation by credit assignment: changing the way existing classifiers are used.
• Adaptation by rule discovery: introducing new classifiers.

Credit assignment

In the basic CFS all classifiers were equally allowed to post their messages into the message list. To improve performance we assign priorities to the classifiers. The good classifiers get high priority in posting their messages into the message list.

Quality of the classifier is defined using two parameters:

• Strength = past usefulness of the classifier.
• Specificity = (length – number_of_#) / length.

Strength and specificity are combined into a single measure, the bid a classifier makes in the aution.
bid = k * strength * specificity
(k = const. ~ 0.1, a parameter of the Bucket Brigade algorithm).

Adaptation by credit assignment – the Bucket Brigade algorithm:

1. If there is a reward (or punishment), add it to the strength of all active classifiers in the current cycle.
2. Each active classifier pays its bid to the classifiers that prepared the stage for it (i.e., posted messages that matched its condition).
3. Each classifier in every cycle pays the "life tax".

Rule discovery

Genetic Algorithm can be used to discover new classifiers. GA introduces diversity into the CFS and explores the space of solutions. In this particular case, the Michigan approach has been used – each classifier is one species. The strength of classifiers is used as fitness.

Description of the application

This application implements LCS with BB and GA.

Fig. 2. Main window of the application.

The classifier system has to guess correctly the color of each field on the board based on its coordinates. Each field can be either black or white. The answer of the system is presented as a small square in the center of the field in question. The small square can be black, white, or gray – when the system doesn't have an answer.

The user can query the system by right-clicking on some field. This process can be automated by clicking the "Start" button – the application will then query the CFS field by field. The system gets a reward for guessing right, and thus adapts following the mechanisms described above.

Changing values in the "Reward" and "Punishment" fields determines how much the strength of the classifier will increase after the correct answer, and how much it will decrease after the wrong answer. One can observe that the system learns much faster if the wrong answers decreases the strength of a classifier at least as much as it would gain for the right answer.

Users can change the task on-line and change colors of the fields by left-clicking on the desired square, or by selecting one of predefined patterns at the bottom of "Controls" tab.

Usage

After selecting language, you are presented with the main window as shown on the screenshot above. First, you should choose a color pattern for the board from the selection list in the right bottom corner. There is also a possibility to draw patterns by hand - by left-clicking on the desired panels (this flips color between black and white). Default parameters of the algorithms are quite good for most cases. You can click "Start". The main cycle of the algorithm begins. It queries the classifier system about all the panels on the board one-by-one. The querying process can be observed as flashing of the little squares. As the process progresses, the system adapts to the color pattern on the board, and its accuracy (which can be observed in the Control Panel) grows. After a while the system should stabilize, the accuracy will only oscillate slightly, and the top of the classifier list will not change. Let's try to modify a color of a few panels. You should see that the accuracy drops and some of the panels have little squares inside of a different color. It takes (depending on the settings) a couple of iterations for the system to adapt to the new pattern, and then the situation should stabilize again.

The moment of stability is good for fiddling with the settings of algorithms. By increasing the Strength Threshold in GA, we change the threshold value below which all classifiers will be "killed". This way we can influence the number of classifiers. Another way to change their number is to change life & bid tax (higher tax -> less classifiers).

An interesting option of the BB algorithm is changing number of classifiers that are allowed to post their answers in every cycle. The system will give answers regarding panel colors with some level of certainty. Quality of this answer is visible in the parenthesis next to the "Answer".

Advanced, technical description.

The board is the environment of the LCS. Field colors and coordinates are the inputs. Querying a field produces an input message in the form of:
10 xxx yyy

• Two first bits are the prefix of the input message.
• Bits 2–4 constitute a binary-encoded column number of the field.
• Bits 5–7 constitute a binary-encoded row number of the field.

The output interface filters messages that start with the "00" prefix, which is the output message prefix. Within output messages, the only important bit is the last one. If its value is 0 – the system answers "black", if it is 1 – the answer is "white". If the Bucket Brigade is allowed to produce more than one winner of the tournament, then the answer is the average of all output messages (this can be interpreted as an answer with a given probability).

The Genetic Algorithm:

• In every cycle, generates one new classifier with strength=1, which is the effect of a uniform crossover of the two best classifiers.
• There is the option of elitism – a number of best individuals is copied without modification into the new population.
• Kills all classifiers with strength below user-defined value.
• Mutates a part of the population.

Program and description: Jakub Misiorny

Improvements: Jędrzej Potoniec

Mentor: Maciej Komosiński