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

The motivation was to escape the brittleness of popular expert systems of that
time by evolving a set of cooperative and competing rules in a market-inspired
economy. In particular, Holland addressed the following three problems [115]:

Parallelism and coordination. Complex situations are to be decomposed into
simpler building blocks, called rules , that handle this situation coopera-
tively. The problem is to provide for the interaction and coordination of
a large number of rules that are active simultaneously.
Credit assignment. To decide which rules in a rule-based system are respon-
sible for its success, one needs to have a mechanism which accredits each
rule with its responsibility to that success. Such mechanism become parti-
cularly complex when rules act collectively, simultaneously and sequentially.
Furthermore, complex problems do not allow for exhaustive search over all
possible rule combinations, and so this mechanism has to operate locally
rather than globally.
Rule discovery. Only in toy problems can one evaluate all possible rules ex-
haustively. Real-world problems require the search for better rules based on
current knowledge to generate plausible hypotheses about situations that
are currently poorly understood.

Holland addressed these questions by proposing a rule-based system that can
be viewed as a message processing system acting on a current set of messages,
either internal or generated by a set of detectors to the environment and thus re-
presenting the environment's observable state. Credit assignment is handled by
a market-like situation with bidders, suppliers and brokers. Rule discovery facili-
tates an evolutionary computation-based process that discovers and recombines
building blocks of previously successful rules.
While the original framework is not replicate in full detail, the following sec-
tion gives an overview of the most common features among some of the LCS
implementations derived from this framework. A detailed overview and compa-
rison of different early LCS is given in Chap. 2 of Barry's Ph.D. thesis [10].

2.2.2 The General Framework

In LCS the agent's behaviour is determined by a set of classifiers (Holland's
rules), each consisting of at least one condition and an action. On sensing the
state of the environment though a detector, the sensor reading of the agent is
injected as a message into an internal message list, containing both internal and
external messages. Classifier conditions are then tested for matching any of the
messages on the message list. The matching classifiers are activated, promoting
their actions by putting their message on the message list. The message on the
list can be either interpreted to perform actions or to be kept on the list to act
as an input for the next cycle. If several actions are promoted at the same time,
a conflict resolution subsystem decides which action to perform. Once this is
completed, the cycle starts again by sensing the new state of the environment.
Figure 2.3 provides a schematic illustration of the message flow in LCS with a
single message list.