Background - Design and Analysis of Learning Classifier Systems - page 18

2.2.3 Interacting Subsystems

To summarise, LCS aim at maximising external reward by an interaction of the
following subsystems:

Performance Subsystem. This subsystem is responsible for reading the input
message, activating the classifiers based on their condition matching any
message in the message list, and performing actions that are promoted by
messages that are posted by the active classifiers.
Conflict Resolution Subsystem. If the classifiers promote several conflicting ac-
tions, this subsystem decides for one action, based upon the quality rating
of the classifiers that promote these actions.
Credit Allocation Subsystem. On receiving external reward, this subsystem de-
cides how this reward is credited to the classifiers that promoted the actions
causing the reward to be given.
Rule Induction Subsystem. This subsystem creates new classifiers based on cur-
rent high-quality classifiers in the population. As the population size is
usually limited, introducing new classifiers into the population requires the
deletion of other classifiers from the population, which is an additional task
of this subsystem.

Although the exact functionality for each of the systems was given in the origi-
nal paper [114], further developments introduce changes to the operation of some
subsystems, which is why only a general description is given here. Section 2.2.5
discusses some properties of these LCS, and point out the major problems that
led the way to a new class of LCS that feature major performance improvements.

2.2.4 The Genetic Algorithm in LCS

Holland initially introduced Learning Classifier Systems as an extension of Ge-
netic Algorithms to Machine Learning. GA's are a class of algorithms that are
based on the principles of evolutionary biology, driven by mutation, selection
and recombination. In principle, a population of candidate solutions is evolved
and, by allowing more reproductive opportunities to fitter solutions, the whole
population is pushed towards higher fitness. Although GA's were initially app-
lied as function optimisers (for example [95]), Holland's idea was to adapt them
to act as the search process in Machine Learning, giving rise to LCS.
In an LCS, the GA operates as the core of the rule induction subsystem,
aiming at replicating classifiers of higher fitness to increase the quality of the
whole population. New classifiers are created by selecting classifiers of high qua-
lity from the population, performing cross-over of their conditions and actions
and mutating their offspring. The offspring is then reintroduced into the popu-
lation, eventually causing deletion of lower quality classifiers due to bounded
population size. Together with the credit allocation subsystem, which is respon-
sible for rating the quality of the classifiers, this process was intended to generate
a set of classifiers that promote optimal behaviour in a given environment.