Page 22 of 29 APJKTU CS464 ARTIFICAL INTELLIGENCE

Classifier Systems and Genetic Programming

Q)explain how classifier systems can be implemented using Genetic
programming

We focus on whether genetic algorithms can be defined for still richer

representations, such as if… then... rules or pieces of computer code. it is difficult to
define genetic operators that capture the syntactic and semantic structure of logical
relationships while enabling effective application of operators such as crossover or
mutation. we may define variations of crossover that can be applied directly to higher
level representations such as if... then... rules or chunks of code in a higher level
programming language

Classifier Systems

input
decoder input message list

working memory
internal messages
environment

output
effector output message list

genetic
production memory
operators for
classifier rules
rule changes

feedback bucket brigade

decoder
credit assignment

Figure 12.3A classifier system interacting with the environment,

adaptedafrom
Holland (1986) developed Holland (1986).architecture called classifier systems
problem-solving
that applies genetic learning to rules in a production system.
provides a means of evaluating the fitness of candidate classifiers, as required in genetic
A classifier
learning. system
The classifier (Figure
system ) includes
of Figure thethe
12.3 has familiar elements
following of a production system:
major components:
production rules (here called classifiers), working memory, input sensors (or
decoders),
1. andofoutputs
Detectors (or effectors).
input messages from the environment.
classifier
2. system
Detectors includemessages
of feedback the usefrom
of the
competitive bidding for conflict resolution,
environment.
genetic algorithms for learning, and the bucket brigade algorithm to assign credit and
blame
3. to rulestranslating
Effectors during learning.
results of rule applications back to the environment.
Feedback
4. from the
A production outside
rule environment
set made providesofa classifiers.
up of a population means of evaluating the has
Each classifier fitness of
candidate classifiers,
an associated asmeasure.
fitness required in genetic learning.

Ref: A
5. George F Luger,
working Elaine
memory Rich
for theKevin Knight
classifier Prepared
rules. This by:integrates
memory Abin Philip,
the Asst.Prof,
results of Toc H
production rule firing with input information.
Page 23 of 29 APJKTU CS464 ARTIFICAL INTELLIGENCE
The classifier system of Figure has the following major components:

1. Detectors of input messages from the environment. 


2. Detectors of feedback messages from the environment. 


3. Effectors translating results of rule applications back to the environment. 


4. A production rule set made up of a population of classifiers. Each classifier has

an associated fitness measure. 


5. A working memory for the classifier rules. This memory integrates the results
of production rule firing with input information. 


6. A set of genetic operators for production rule modification. 


7. A system for giving credit to rules involved in producing successful actions. 


Q) explain the purpose of bidding scheme and bucket brigade procedure used in
Classifier systems ( these need to be explain while explaining classifier systems too)

The environment sends a message, perhaps a move in a game, to the classifier

system’s detectors. This event is decoded and placed as a pattern on the internal
message list, the working memory for the production system. These messages, match
the condition patterns of the classifier rules. The selection of the “strongest activated
classifiers” is determined by a bidding scheme, where a bid is a function of both the
accumulated fitness of the classifier and the quality of the match between the input
stimulus and its condition pattern. The classifiers with the closest match add
messages (the action of the fired rules) to working memory. The revised message list
may send messages to the effectors which act upon the environment or activate new
classifier rules as the production system processing continues.

Classifier systems implement a form of reinforcement learning, Based on feedback

from a teacher or fitness evaluation function, the learner computes the fitness of a
population of candidate rules and adapts this population using a variation of genetic
learning. Classifier systems learn in two ways. First, there is a reward system that
adjusts the fitness measures of the classifier rules, rewarding successful rule firings
and penalizing errors. The credit assignment algorithm passes part of the reward or
penalty back to any classifier rules that have contributed to the final rule firing.

This distribution of differential rewards across interacting classifiers, as well as those

that enabled their firing, is often implemented in a bucket brigade algorithm. The
bucket brigade algorithm addresses the problem of assigning credit or blame in
situations where the system’s output may be the product of a sequence of rule firings.
In the event of an error, how do we know which rule to blame? Is the responsibility
that of the last rule to fire, or of some previous rule that provided it with faulty
Ref: George F Luger, Elaine Rich Kevin Knight Prepared by: Abin Philip, Asst.Prof, Toc H
Page 24 of 29 APJKTU CS464 ARTIFICAL INTELLIGENCE
information? The bucket brigade algorithm allocates both credit and blame across a
sequence of rule applications according to measures of each rule’s contribution to the
final conclusion.

The second form of learning modifies the rules themselves using genetic operators
such as mutation and crossover. This allows the most successful rules to survive and
combine to make new classifiers, while unsuccessful rule classifiers disappear.

Each classifier rule consists of three components: the rule’s condition matches data in
the working memory in the typical production system sense. In learning, genetic
operators can modify both the conditions and the actions of the production rules. The
second component of the rule, the action, can have the effect of changing the internal
message list (the production memory). Finally, each rule has a fitness measure. This
parameter is changed, as just noted, both by successful as well as by unsuccessful
activity. This measure is originally assigned to each rule on its creation by the genetic
operators; for example, it may be set as the average fitness of its two parents.

EXAMPLE FOR CLASSIFIER SYSTEM USING GENETIC

PROGRAMMING
Assume that a set of objects to be classified are defined by six attributes (conditions
c1, c2, ..., c6), and further suppose that each of these attributes can have five different
val- ues. Although the possible values of each attribute are of course different (for
example, the value of c3 might be color, while c5 might describe the weather) we
will, without loss of generality, give each attribute an integer value from {1, 2, ..., 5}.
Suppose the conditions of these rules place their matching object in one of four
classes: A1, A2, A3, A4.

Based on these constraints, each classifier will have the form:

(c1 c2 c3 c4 c5 c6) → Ai, where i = 1, 2, 3, 4.


where each ci in the condition pattern denotes the value {1, 2, ..., 5} of the ith
attribute of the condition. Usually, conditions can also assign a value of # or “don’t
care” to an attribute. Ai denotes the classification, A1, A2, A3, or A4. Table 12.2
presents a set of classifiers. Note that different condition patterns can have the same
classification, as in rulesAi1denotes
attribute. and 2, theor the sameA1,patterns,
classification, A2, A3, or as
A4.in rules
Table 12.2 3 and 5,
presents a setcan lead to
of clas-
sifiers. Note that different condition patterns can have the same classification, as in rules 1
different classifications.
and 2, or the same patterns, as in rules 3 and 5, can lead to different classifications.

Condition (Attributes) Action (Classification) Rule Number

(1 # # # 1 #) → A1 1
(2 # # 3 # #) → A1 2
(# # 4 3 # #) → A2 3
(1 # # # # #) → A2 4
(# # 4 3 # #) → A3 5
etc.

Table 12.2 A set of condition → action classifiers to be learned.

Ref: George F Luger, Elaine Rich Kevin

As described Knight
so far, Prepared
a classifier system by:another
is simply Abin Philip,
form of Asst.Prof, Toc H
the ubiquitous
production system. The only really novel feature of classifier rules in this example is their
use of strings of digits and #s to represent condition patterns. It is this representation of
conditions that constrains the application of genetic algorithms to the rules. The remainder
 Page 25 of 29 APJKTU CS464 ARTIFICAL INTELLIGENCE
In order to simplify the remainder of the example, we will only consider the classifier
system’s performance in learning the classification A1. That is, we will ignore the
other classifications, and assign condition patterns a value of 1 or 0 depending on
whether or not they support classification A1.

For example, the classifiers of Table may be summarized by:

(1 # # # 1 #) → (1 0 0 0)
(2 # # 3 # #) → (1 0 0 0)
(1 # # # # #) → (0 1 0 0)
(# # 4 3 # #) → (0 1 1 0)
In this example, the last of these summaries indicates that the condition attributes
support classification rules A2 and A3 and not A1 or A4. By replacing the 0 or 1
assignment with these vectors, the learning algorithm can evaluate the performance
of a rule across multiple classifications.

In this example, we will use the rules in Table 12.2 to indicate the correct classifica-
tions; essentially, they will function as teachers or evaluators of the fitness of rules in
the learning system. As with most genetic learners, we begin with a random
population of rules. Each condition pattern is also assigned a strength, or fitness,
parameter (a real num- ber between 0.0, no strength, and 1.0, full strength. This
strength parameter, s, is com- puted from the fitness of each rule’s parents, and
measures its historical fitness.

At each learning cycle, the rules attempt to classify the inputs and are then ranked by
the teacher or fitness metric. For example, assume that at some cycle, the classifier
has the

following population of candidate classification rules, where the conclusion of 1

following population
indicates of candidate
that the classification
pattern led rules,classifcation
to a correct where the conclusion of 1itindicates
and 0 that did not:
that the pattern led to a correct classifcation and 0 that it did not:
Suppose a new input message arrives from the
(# # # 2 1 #) → 1 s = 0.6 environment: (1 4 3 2 1 5), and the teacher (using the
(# # 3 # # 5) → 0 s = 0.5
first rule of Table 12.2) classifies this input vector as a
(2 1 # # # #) → 1 s = 0.4
(# 4 # # # 2) → 0 s = 0.23 positive example of A1. Let’s consider what happens
when working memory receives this pattern and the four
Suppose a new input message arrives candidate
from the classifier rules(1try
environment: 4 3to2 1match
5), andit.theRules 1 and 2
match.
teacher (using Conflict resolution
the first rule is done
of Table 12.2) through
classifies competitive
this input bidding
vector as a positive among matching
example
of A1.rules. In our example, bidding is a function of the sum of the matchesthe
Let’s consider what happens when working memory receives this pattern and of the attribute
four candidate classifier rules try to match it. Rules 1 and 2 match. Conflict
values times the strength measure of the rule. “Don’t care” matches have the value resolution is
done0.5,
through
whilecompetitive bidding have
exact matches amongvaluematching
1.0. rules. In our
To nor- example,
malize bidding this
we divide is a result by the
function of the sum of the matches of the attribute values times the strength measure of the
length of the input vector. Since the input vector matches the first classifier with two
rule. “Don’t care” matches have the value 0.5, while exact matches have value 1.0. To nor-
exact and four “don’t cares,” its bid is ((4 * 0.5 + 2 * 1) * 0.6) / 6, or 0.4. The second
malize we divide this result by the length of the input vector. Since the input vector
classifier
matches the firstalso matches
classifier twoexact
with two attributes
and four and hascares,”
“don’t four “don’t
its bid iscares,” so+its
((4 * 0.5 2 *bid is 0.33. In
our /example,
1) * 0.6) only
6, or 0.4. The the classifier
second making
classifier also matchesthe twohighest
attributesbid
andfires, but“don’t
has four in more complex
situations,
cares,” it 0.33.
so its bid is may In beour
desirable
example,for onlya percentage
the classifierof the bids
making to be accepted.
the highest bid fires,
but in more complex situations, it may be desirable for a percentage of the bids to be
accepted.
Ref: George F Luger, Elaine Rich Kevin Knight Prepared by: Abin Philip, Asst.Prof, Toc H
The first rule wins and posts its action, a 1, indicating that this pattern is an example
of A1. Since this action is correct, the fitness measure of rule 1 is increased to between its
present value and 1.0. Had the action of this rule been incorrect, the fitness measure would
malize we divide this result by the length of the input vector. Since the input vector
matches the first classifier with two exact and four “don’t cares,” its bid is ((4 * 0.5 + 2 *
1) Page
* 0.6) 26
/ 6,of
or290.4. The second classifier also matches two attributes
APJKTU CS464and has four “don’t
ARTIFICAL INTELLIGENCE
cares,” so its bid is 0.33. In our example, only the classifier making the highest bid fires,
butThe first complex
in more rule wins and posts
situations, its action,
it may a 1, for
be desirable indicating
a percentage that this
of thepattern
bids toisbean example
of A1. Since this action is correct, the fitness measure of rule 1 is increased to
accepted.
between
The first its
rulepresent
wins andvalue and
posts its 1.0.a Had
action, the action
1, indicating of pattern
that this this ruleis anbeen incorrect, the
example
of A1. Since this action is correct, the fitness measure of rule
fitness measure would have been lowered. If the system required multiple 1 is increased to between its firings of
present valueset
the rule andto1.0. Had the some
produce action of this rule
result on been incorrect, the fitness
the environment, measure
all the ruleswould
responsible for
have been lowered. If the system required multiple
this result would receive some proportion of the reward. firings of the rule set to produce some
result on the environment, all the rules responsible for this result would receive some pro-
portion
Onceofthe the reward.
fitness The of theexactcandidate
procedure by which
rules hasthebeen
rule’scomputed,
fitness is calculated varies algorithm
the learning
across systems and may be fairly complex, involving the use of the bucket brigade algo-
applies genetic operators to create the next generation of rules. First, a selection
rithm or some similar credit assignment technique. See Holland (1986) for details.
algorithm will decide the most fit members of the rule set. This selection is based on
Once the fitness of the candidate rules has been computed, the learning algorithm
the fitness
applies mea- sure,
genetic operators but may
to create alsogeneration
the next include of anrules.
additional
First, a random value. The random
selection algorithm
willvalue
decidegives rules
the most fit with
members a poor
of thefitness
rule set.the opportunity
This to reproduce,
selection is based on the fitnesshelping
mea- to avoid a
toobuthasty
sure, elimination
may also include anofadditional
rules that, while
random performing
value. The random poorly
value overall,
gives rules may
withincorporate
somefitness
a poor element of the desired
the opportunity solution.
to reproduce, Suppose
helping to avoidthea too
firsthasty
twoelimination
classifier ofrules of the
example
rules areperforming
that, while selected poorlyto survive
overall, and reproduce.some
may incorporate Randomly
element of selecting
the desired a crossover
solution. Suppose the first two classifier
position between the fourth and fifth elements, rules of the example are selected to survive and
reproduce. Randomly selecting a crossover position between the fourth and fifth elements,
The fitness measure of the children is a weighted
(# # # 2 | 1 #) → 1 s = 0.6 function of the fitness of the parents. The weighting is
(# # 3 # | # 5) → 0 s = 0.5 a function of where the crossover point lies. The first
offspring has 1/3 of the original 0.6 classifier and 2/3
produces the offspring:
of the original 0.5 classifier. Thus, the first offspring
(# # 3 # | 1 #) → 0 s = 0.53 has strength of (1/3 * 0.6) + (2/3 * 0.5) = 0.53. With a
(# # # 2 | # 5) → 1 s = 0.57 similar calculation, the fitness of the second child is
0.57. The result of firing the classifier rule, always 0 or
1, goes with the majority of the attributes, thus
preserving the intuition that these12patterns
CHAPTER areLEARNING:
/ MACHINE important in the
SOCIAL outcomes
AND EMERGENT of the rules.
523
In a typical classifier system these two new rules, along with their parents, would
make up the subset of classifiers for the operation of the system at the next time step.

Q) Explain Programming with Genetic Operators with example

It can quite naturally be asked if genetic and evolutionary techniques might be
applied to the production of other larger scale computational tools. There have been
two major examples of this: the generation of computer programs and the evolution
of systems of finite state machines.

The learning algorithm maintains a population of candidate programs. The fitness of

a program will be measured by its ability to solve a set of tasks, and programs are
modified by applying crossover and mutation to program subtrees. Genetic
programming searches a space of computer programs of varying size and complexity;
in fact, the search space is the space of all possible computer programs composed of
functions and terminal symbols appropriate to the problem domain.

Genetic programming starts with an initial population of randomly generated pro-

grams made up of appropriate program pieces. These pieces, suitable for a problem

Ref: George F Luger, Elaine Rich Kevin Knight Prepared by: Abin Philip, Asst.Prof, Toc H
Page 27 of 29 APJKTU CS464 ARTIFICAL INTELLIGENCE
domain, may consist of standard arithmetic operations, other related programming
opera- tions, and mathematical functions, as well as logical and domain-specific
functions. Pro- gram components include data items of the usual types: boolean,
integer, floating point, vector, symbolic, or multiple-valued.

After initialization, thousands of computer programs are genetically bred. The

production of new programs comes with application of genetic operators. Crossover,
mutation, and other breeding algorithms must be customized for the production of
com- puter programs The fitness of each new program is then determined by seeing
how well it performs in a particular problem environment. The nature of the fitness
measure will vary according to the problem domain. Any program that does well on
this fitness task will survive to help produce the children of the next gen- eration.

To summarize, genetic programming includes six components, many very similar to

the requirements for GAs:

1. A set of structures that undergo transformation by genetic operators.

2. A set of initial structures suited to a problem domain.

3. A fitness measure, again domain dependent, to evaluate structures.

4. A set of genetic operators to transform structures.

5. Parameters and state descriptions that describe members of each generation.

6. A set of termination conditions.

To initialize the structures for adaptation by genetic operators, we must create two
sets: F, the set of functions and T, the set of terminal values required for the domain.
F can be as simple as {+, *, −, /} or may require more complex functions such as
sin(X), cos(X), or functions for matrix operations. T may be the integers, reals,
matrices, or more complex expressions. The symbols in T must be closed under the
functions defined in F.

Next, a population of initial “programs” is generated by randomly selecting elements

from the union of sets F and T. For example, if we begin by selecting an element of T,
we have a degenerate tree of a single root node. More interestingly, when we start
with an element from F, say +, we get a root node of a tree with two potential
children. Suppose the initializer next selects * (with two potential children) from F, as
the first child, and then terminal 6 from T as the second child. Another random
selection might yield the ter- minal 8, and then the function + from F. Assume it
concludes by selecting 5 and 7 from T.

The program we have randomly produced is represented in Figure Figure a gives the
tree after the first selection of +, fig b after selecting the terminal 6, and fig c, the
final program. A population of similar programs is created to initialize the genetic
programming process.
Ref: George F Luger, Elaine Rich Kevin Knight Prepared by: Abin Philip, Asst.Prof, Toc H
 Page 28 of 29 APJKTU CS464 ARTIFICAL INTELLIGENCE

+
Genetic operators
applied on a tree
+
* 6

+
* 6
8 +

5 7

a. b. c.

Figure 12.4 The random generation of a program to initialize.

The circled nodes are from the set of functions.
Genetic operators on programs include both transformations on a tree itself as well as
the exchange of structures between trees. Koza (1992) describes + −
the primary transforma-
present generation and copies them (unchanged) into the next| generation. + Crossover −
tions as reproduction and crossover. Reproduction simply selects programs from the
exchanges subtrees between the trees representing two programs. |For example, suppose8
we present generation
are working with theand
two copies them (unchanged)
parent programs into*and
of Figure 12.5, thethat
next +random points
thegeneration. Crossover *
exchanges * + 8
suppose*
indicated by | insubtrees between
parent a and parent the
b aretrees representing
selected twoThe
for crossover. programs. For example,
resulting children are |
we are
shown working
in Figure 12.6.with the two
Crossover canparent
also beprograms of Figurea single
used to transform 12.5, and thatbythe
parent, random points
inter- |
changing two subtrees
indicated by | in parent a and
from that parent. Two b
parent identical parentsfor
are selected4 cancrossover.
6 10 SIN
create different
The
SIN
children COS
resulting children
COS
8
4 6 10 8
with randomly selected crossover points. The root of a program can
are shown in Figure 12.6. Crossover can also be used to transform a single also be selected as parent,
a by
crossover point.
inter- changing two subtrees from that parent. Two identical parents can create different
6 3
There are a number of secondary, and much less used, genetic transforms of6program 3
children with randomly selected crossover points. The
trees. These include mutation, which simply introduces random changes
root
a. of a program can also
in the structures
b. be

of selected
a program.asFora crossover point. a terminal value with another a.value or a function
example, replacing
b.
Figure 12.5 Two programs, selected on fitness for crossover. Point |
subtree. The permutation transform, similar to the inversion Figure 12.5 operator
from andon
Twoa programs, strings,
b are also
selected
randomly on fitness for
selected for crossover.
crossover. Point |
works on single programs, exchanging terminal symbols, or subtrees, fromfor a and b are randomly selected for crossover.
example.
The state of the solution is reflected by the current generation of programs. There is
no record keeping for backtrack or any other method for skipping around + the fitness land- −
scape. In this+ aspect genetic programming − +
is much like the hill-climbing algorithm −
described| in Section 4.1. The genetic programming paradigm parallels nature in that the
+ −
evolution of new programs is a continuing process. Nonetheless, +
COS lacking infinite time and *
computation,
*
| + 8
termination conditions are set. These* COS
are usually a function both + of program 8
8 *
+
fitness and* computational resources. 8
| * 3
The fact that genetic programming is a technique for the computational generation of
SIN *
| 3 10 8
computer
4 6programs
10 places it within the automatic8 programming research tradition.
SIN COS 10 SIN From * 8
the earliest
4 days
6 10 of AI,SIN researchers have
COS worked 8 to automatically produce computer
6
programs from fragmentary 6
information (Shapiro 1992). Genetic programming 6 can be 4 6
3
seen as another tool for 6this important research3 domain. We conclude this section with a 4 6
a. b. a. b.
simple examplea. of genetic programming b.
taken from Mitchell (1996).
a. b.
Figure 12.5 Two programs, selected on fitness for crossover. Point | Figure 12.6 The child programs produced by cross-
Figure 12.5fromTwo programs,
a and selected on
b are randomly fitness for
selected forcrossover.
crossover.Point | Figure 12.6 over
Theofchild programs
the points produced
in Figure 12.5.by cross-
from a and b are randomly selected for crossover. over of the points in Figure 12.5.
CHAPTER 12 / MACHINE LEARNING: SOCIAL AND EMERGENT 527
EXAMPLE 3.2.1: EVOLVING A PROGRAM FOR KEPLER’S THIRD LAW OF PLANETARY MOTION
+ + −− EXAMPLE 3.2.1: EVOLVING A PROGRAM FOR KEPLER’S THIRD LAW OF PLANETARY MOTION
Koza (1992, 2005) describes many applications of genetic programming to solve intere
Koza
ing (1992, but
problems, 2005) describes
most of thesemany applications
examples are largeof and
genetic programming
too complex for ourto solve
presentinte
p
Ref: George F+Luger,
COSCOS + Elaine8Rich Kevin * ing problems,
Knight
poses. Prepared
but most
Mitchell (1996), of by:
these
however, hasAbin
examplesPhilip,
created are Asst.Prof,
large
a simple and too Toc
complex
example that H for
illustratesour present
many of
8 *poses. Mitchell (1996), however, has created a simple example that illustrates many o
concepts of genetic programming. Kepler’s Third Law of Planetary Motion describes
concepts relationship
functional of genetic programming. Kepler’s
between the orbital ThirdP,Law
period, of aofplanet
Planetary Motion
and its averagedescribe
distan
3 3 functional relationship
A, from the sun. between the orbital period, P, of a planet and its average dista
10 SINSIN *
Page 29 of 29 APJKTU CS464 ARTIFICAL INTELLIGENCE
There are a number of secondary, and much less used, genetic transforms of program
trees. These include mutation, which simply introduces random changes in the structures
of a program. For example, replacing a terminal value with another value or a function
subtree.The permutation transform, similar to the inversion operator on strings, also
works on single programs, exchanging terminal symbols, or subtrees, for example.

READ FURTHER PAGE 528 GEORGE F LUGER

Ref: George F Luger, Elaine Rich Kevin Knight Prepared by: Abin Philip, Asst.Prof, Toc H