Example of Classifier System
Behaviour of a frog
-
Whenever a small flying object appears, that has no stripes, Kermit should
eat it, because its very likely a spicy fly, or other flying insect.
-
If it has stripes, the insect is better left alone, because Kermit had
better not bother with wasps, hornets, or bees.
-
If Kermit encounters a large, looming object, it immediately uses its effectors
to jump away, as far as possible.
Write into if then else rules:
IF small, flying object to the left THEN send @
IF small, flying object to the right THEN send %
IF small, flying object centered THEN send $
IF large, looming object THEN send !
IF no large, looming object THEN send *
IF * and @ THEN move head 15 degrees left
IF * and % THEN move head 15 degrees right
IF * and $ THEN move in direction head pointing
IF ! THEN move rapidly away from direction head pointing
Coding
IF THEN
0000, 00 00 00 00
0000, 00 01 00 01
0000, 00 10 00 10
1111, 01 ## 11 11
~1111, 01 ## 10 00
1000, 00 00 01 00
1000, 00 01 01 01
1000, 00 10 01 10
1111, ## ## 01 11
(~ is a NOT) Obviously, string `0000' denotes small, and `00' in the
fist part of the second column, denotes flying. The last two bits of column
#2 encode the direction of the object approaching, where `00' means left,
`01' means right, etc.
In rule #4 a the "don't care symbol" `#' is used, that matches `1' and
`0', i.e., the position of the large, looming object, is completely arbitrary.
A simple fact, that can save Kermit's (artificial) life.
Algorithm Non-Learning CFS is
// start with an initial time
t := 0;
// an initially empty message list
initMessageList ML (t);
// and a randomly generated population of classifiers
initClassifierPopulation P (t);
// test for cycle termination criterion (time, fitness, etc.)
while not done do
// increase the time counter
t := t + 1;
// 1. detectors check whether input mess are
present
ML := readDetectors
(t);
// 2. compare ML to the classifiers and save
matches
ML' := matchClassifiers
ML,P (t);
// 3. process new messages through output
interface
ML := sendEffectors
ML' (t);
od
end CFS.
To convert the previous, non-learning CFS into a learning CLASSIFIER
SYSTEM, LCS, as has been proposed in Holland (1986), it takes two steps:
(1) the major cycle has to be changed such that the activation of each
classifier depends on some additional parameter, that can be modified as
a result of experience, i.e. reinforcement from the ENVIRONMENT;
(2) and/or change the contents of the classifier list, i.e., generate
new classifiers/rules, by removing, adding, or combining condition/action-parts
of existing classifiers.
Algorithm Learning LCS is
// start with an initial time
t := 0;
// an initially empty message list
initMessageList ML (t);
// and a randomly generated population of classifiers
initClassifierPopulation P (t);
// test for cycle termination criterion (time, fitness, etc.)
while not done do
// increase the time counter
t := t + 1;
// 1. detectors check whether input mess are present
ML := readDetectors (t);
// 2. compare ML to the classifiers and save matches
ML' := matchClassifiers ML,P (t);
// 3. highest bidding classifier(s) collected in ML' wins
// the "race" and post the(ir) message(s)
ML' := selectMatchClfiers ML',P (t);
// 4. tax bidding classifiers, reduce their strength
ML' := taxPostingClfiers ML',P (t);
// 5. effectors check new m-list for output msgs
ML := sendEffectors ML' (t);
// 6. receive payoff from environment (REINFORCEMENT)
C := receivePayoff (t);
// 7. distribute payoff/credit to classifiers (e.g. BBA)
P' := distributeCredit C,P (t);
// 8. Eventually (depending on t), an EA (a GA) is
// applied to the classifier population
if criterion then
P := generateNewRules
P' (t);
else
P := P'
od
end LCS.