Soft Comput
DOI 10.1007/s00500-013-1044-4

Discrete and fuzzy dynamical genetic programming in the
XCSF learning classifier system

arXiv:1201.5604v2 [] 25 Jan 2015

Richard J. Preen · Larry Bull

The final version of this paper is published in Soft Computing 2014, 18(1):153–167.

Abstract A number of representation schemes have
been presented for use within learning classifier systems, ranging from binary encodings to neural networks.
This paper presents results from an investigation into
using discrete and fuzzy dynamical system representations within the XCSF learning classifier system. In
particular, asynchronous random Boolean networks are
used to represent the traditional condition-action production system rules in the discrete case and asynchronous fuzzy logic networks in the continuous-valued
case. It is shown possible to use self-adaptive, openended evolution to design an ensemble of such dynamical systems within XCSF to solve a number of wellknown test problems.
Keywords Fuzzy logic networks · Learning classifier
systems · Memory · Random Boolean networks ·
Reinforcement learning · Self-adaptation · XCSF

1 Introduction
Traditionally, learning classifier systems (LCS; Holland
1976) use a ternary encoding to generalize over the environmental inputs and to associate appropriate actions.
A number of representations have previously been presented beyond this scheme however, including real numbers (Wilson 2000), fuzzy logic (Valenzuela-Rendón
1991) and artificial neural networks (Bull 2002). Temporally dynamic representation schemes within LCS
represent a potentially important approach since temporal behaviour of such kinds is viewed as a significant
Richard J. Preen · Larry Bull
Department of Computer Science and Creative Technologies
University of the West of England, Bristol, BS16 1QY, UK
E-mail: richard2.preen@uwe.ac.uk, larry.bull@uwe.ac.uk

aspect of artificial life, biological systems, and cognition
in general (Ashby 1952).
In this paper we explore examples of a dynamical
system representation within the XCSF learning classifier system (Wilson 2001)—termed dynamical genetic
programming (DGP; Bull 2009). Traditional tree-based
genetic programming (GP; Koza 1992) has been used
within LCS both to calculate the action (Ahluwalia and
Bull 1999) and to represent the condition (e.g., Lanzi
and Perrucci 1999). DGP uses a graph-based representation, each node of which is constantly updated with
asynchronous parallelism, and evolved using an openended, self-adaptive scheme. In the discrete case, each
node is a Boolean function and therefore the representation is a form of random Boolean network (RBN;
e.g., Kauffman 1993). In the continuous case, each node
performs a fuzzy logical function and the representation is a form of fuzzy logic network (FLN; e.g., Kok
and Wang 2006). We have recently introduced the use
of RBN within LCS (Bull and Preen 2009; Preen and
Bull 2009). Here we extend that work to the most recent form of LCS, and to the continuous-valued domain,
exploring the potential to harness the collective emergent behaviour for computation. We show that XCSF
is able to solve a number of well-known immediate and
delayed reward tasks using this temporally dynamic
knowledge representation scheme with competitive performance with other representations. Moreover, we exploit the memory inherent to RBN for the discrete case.
The remainder of this paper is organised as follows.
Section 2 provides a brief discussion of related work.
Section 3 introduces RBN, giving a detailed description of the form and temporal behaviour. Section 4
describes the XCSF learning framework. Section 5 details how asynchronous RBN are here evolved and used
for computation within XCSF. Section 6 discusses and

2

presents results from a set of maze experiments requiring the exploitation of inherent memory within the discrete dynamical ensemble. Section 7 introduces FLN as
a continuous-valued extension of RBN and discusses the
dynamical behaviour. Section 8 describes how FLN are
here used as continuous production system rules within
XCSF. Section 9 presents results from experimentation
with a continuous-input, discrete-action, maze environment, and a fully continuous reinforcement learning
problem. Section 10 provides final conclusions.
2 Related work
The most common form of discrete dynamical system
is the cellular automaton (CA; Von Neumann 1966),
which consists of an array of cells (lattice of nodes)
where the cells exist in states from a finite set and update their states with synchronous parallelism in discrete time. CA have been extensively used to model
genetic regulatory networks (GRN). However, continuous network models of GRN exist which are an extension of Boolean networks, where nodes still represent
genes and the connections between them regulate the
influence on gene expression. Indeed, there is a growing
body of work exploring the evolution of different forms
of such continuous-valued GRN. Differential equations
wherein gene interactions are incorporated as logical
functions are a typical approach (e.g., Glass and Kauffman 1973). Reiter (2002) investigated the affect of the
fuzzy background on the dynamics of CA with various fuzzy logic sets and found that the choice of logic
used leads to significantly different behaviours. For example, applying the various logical functions to create
fuzzy versions of the game of life, it was noted that
certain sets of logics generated fuzzy-CA that tended
toward homogeneous fuzzy behaviour, whereas others
were consistent with chaotic or complex behaviour.
Most relevant to the form of GP used herein is
the relatively small amount of prior work on graphbased representations. In particular, neural programming (NP; Teller and Veloso 1996) uses a directed graph
of connected nodes, each performing an arbitrary function. Potentially selectable functions include READ,
WRITE, and IF-THEN-ELSE, along with standard arithmetic and zero-arity functions. Additionally, complex
user defined functions may be used. Significantly, recursive connections are permitted and each node is executed with synchronous parallelism for some number
of cycles before an output node’s value is taken.
Other examples of graph-based GP typically contain
sequentially updating nodes, e.g., finite state machines
(e.g., Fogel et al 1965), cartesian GP (Miller 1999),
genetic network programming (Hirasawa et al 2001),

Richard J. Preen, Larry Bull

linear-graph GP (Kantschik and Banzhaf 2002), and
graph structured program evolution (Shirakawa et al
2007). Schmidt and Lipson (2007) have recently demonstrated a number of benefits from graph encodings over
traditional trees, such as reduced bloat and increased
computational efficiency, and a significant benefit of
symbolic representations is the expressive power to represent relationships between the sensory inputs (Mellor
2005).
Landau et al (2001) used a purely evolution-based
form of LCS (Pittsburgh style; Smith 1983) in which
the rules are represented as directed graphs where the
genotypes are tokens of a stack-based language, whose
execution builds the labeled graph. Bit-strings are used
to represent the language tokens and applied to nonMarkov problems. The genotype is translated into a
sequence of tokens and then interpreted similarly to a
program in a stack-based language with instructions to
create the graph’s nodes, connections and labels. Subsequently, the unused conditions and actions in the stack
are added to the structure which is then popped from
the stack. Tokens are used to specify the matching conditions and executable actions as well as instructions to
construct the graph, and to manipulate the stack. The
bit-strings were later replaced with integer tokens and
again applied to non-Markov problems (Landau et al
2005).
Bull and O’Hara (2002) presented a form of fuzzy
representation within LCS using radial basis function
neural networks (RBF; Moody and Darken 1989) to embody each condition-action rule. That is, a simple class
of neural-fuzzy hybrid system. Furthermore, Su et al
(2006) explored a similar representation based on RBF
within LCS. However, here the contribution of each rule
is determined by its strength (which is updated by a
fuzzy bucket brigade algorithm) as well as the extent
to which the antecedent matches the environment. Furthermore, in contrast to Bull and O’Hara (2002), each
condition-action rule corresponds to a hidden node instead of a fully-connected network and rules are added
incrementally instead of being evolved through the GA.
To date, only the use of RBF has been explored as a
neuro-fuzzy hybrid representation within LCS.

3 Random Boolean networks
RBN were originally introduced by Kauffman (see, e.g.,
Kauffman 1993) to explore aspects of biological genetic
regulatory networks. Since then they have been used as
a tool in a wide range of areas, such as self-organisation
(e.g., Kauffman 1993) and computation (e.g., Mesot
and Teuscher 2005) and robotics (e.g., Quick et al 2003).

Discrete and fuzzy dynamical genetic programming in the XCSF learning classifier system

1

2

3

Node 2
Inputs

Encoding
State

Connections

[1,3]

1

3

0

0

0

0

1

0

1

0

0

1

1

1

Truth Table

0001
Current State

1
Fig. 1: Example RBN and node encoding.

An RBN typically consists of a network of N nodes,
each performing a Boolean function with K inputs from
other nodes in the network, all updating synchronously
(see Figure 1). As such, RBN may be viewed as a generalization of binary CA and unorganized machines (Turing 1948). Since they have a finite number of possible states and they are deterministic, the dynamics of
RBN eventually fall into a basin of attraction. It is wellestablished that the value of K affects the emergent behaviour of RBN wherein attractors typically contain an
increasing number of states with increasing K. Three
phases of behaviour are suggested: ordered when K =
1, with attractors consisting of one or a few states;
chaotic when K > 3, with a very large number of states
per attractor; and, a critical regime around K = 2,
where similar states lie on trajectories that tend to neither diverge nor converge and 5-15% of nodes change
state per attractor cycle (for discussions of this critical
regime, e.g., with respect to perturbations see Kauffman 1993). Analytical methods have been presented
by which to determine the typical time taken to reach
a basin of attraction and the number of states within
such basins for a given degree of connectivity K (see,
e.g., Kauffman 1993).
Closely akin to the work described here, Kauffman
(1993) describes the use of simulated evolution to design
RBN which must play a (mis)matching game wherein
mutation is used to change connectivity, the Boolean
functions, K and N . He reports the typical emergence
of high fitness solutions with K=2 to 3, together with
an increase in N over the initialised size. Sipper and
Ruppin (1997) extended Sipper’s heterogeneous CA ap-

3

proach (Sipper 1997) to enable heterogeneity in the
node connectivity, along with the node function; they
evolved a form of RBN. Van den Broeck and Kawai
(1990) explored the use of a simulated annealing-type
approach to design feedforward RBN for the four-bit
parity problem and Lemke et al (2001) evolved RBN of
fixed N and K to match an arbitrary attractor.
Figure 2 shows the affect of K on a 13 node RBN;
results are an average of 100 runs for each value of
K. It can be seen that the higher the value of K, the
greater the number of states the networks will cycle
through, as shown by the higher rate of change of node
states. Further, that after an initial rapid decline in
the rate of change, this value stabilises as the states fall
into their respective attractors. In the synchronous case
(Figure 2a) when K = 2, the number of nodes changing state converges to around 20%, and when K = 3
to just above 35%; thus we can see that the ordered
regime occurs when approximately 20% or less nodes
are changing state each cycle, and the chaotic regime
occurring for larger rates of change.
As noted above, traditional RBN consist of N nodes
updating synchronously in discrete time steps, but asynchronous versions have also been presented, after Harvey and Bossomaier (1997), leading to a classification of
the space of possible forms of RBN (Gershenson 2002).
Asynchronous forms of CA have also been explored
(e.g., Ingerson and Buvel 1984) wherein it is often suggested that asynchrony is a more realistic underlying assumption for many natural and artificial systems since
“discrete time, synchronously updating networks are
certainly not biologically defensible: in development the
interactions between regulatory elements do not occur
in a lock-step fashion” (Wuensche 2004).
Asynchronous logic devices are known to have the
potential to consume less power and dissipate less heat
(Werner and Akella 1997), which may be exploitable
during efforts towards hardware implementations of
such systems. Asynchronous logic is also known to have
the potential for improved fault tolerance, particularly
through delay insensitive schemes (e.g., Di and Lala
2007). This may also prove beneficial for hardware implementations.
Harvey and Bossomaier (1997) showed that asynchronous RBN exhibit either point attractors, as seen in
asynchronous CAs, or loose attractors where “the network passes indefinitely through a subset of its possible
states” (as opposed to distinct cycles in the synchronous
case). Thus the use of asynchrony represents another
feature of RBN with the potential to significantly alter their underlying dynamics thereby offering another
mechanism by which to aid the simulated evolutionary
design process for a given task. Di Paulo (2001) showed

4

4 XCSF overview
An LCS rule (also termed a classifier) traditionally takes
the form of an environment string consisting of the
ternary alphabet [0,1,#], a binary action string, and
subsequent information including the classifier’s expected
payoff (reward) P , the error rate ǫ (in units of payoff
predicted), and the fitness f . The # symbol in the environment condition provides a mechanism to generalise
the inputs received by matching for both logical 0 and
1 for that bit.
For each phase in the learning cycle, a match set [M]
is generated from the population set [P], composed of all
of the classifiers whose environment condition matches
the current environmental input. In the event that the
number of actions present in [M] is less than a threshold value, θmna , covering is used to produce a classifier
that matches the current environment state along with
an action assigned randomly from those not present in
[M]; typically θmna is set to the maximum number of
possible actions so that there must be at least one classifier representing each action present.
Subsequently, a system prediction is made for each
action in [M], based upon the fitness-weighted average
of all of the predictions of the classifiers proposing the
action. If there are no classifiers in [M] advocating one
of the potential system actions, covering is invoked to
generate classifiers that both match the current environment state and advocate the relevant action. An
action is then selected using the system predictions,
typically by alternating exploring (by either roulette

0.6

Fraction of Nodes Changing State

0.5

0.4

0.3

0.2

K=2
K=3
K=4
K=5

0.1

0.0
0

10

20

30

40

50

60

70

80

90

100

T Cycles
(a) Synchronous.
0.6

K=2
K=3
K=4
K=5

0.5

Fraction of Nodes Changing State

it is possible to evolve asynchronous RBN which exhibit
rhythmic behaviour at equilibrium. Asynchronous CAs
have also been evolved (e.g., Sipper and Ruppin 1997).
Figure 2b shows the percentage of nodes changing
state on each cycle for various values of K on a 13 node
asynchronous RBN. It can be seen that, similar to the
synchronous case (see Figure 2a), the higher the value
of K, the greater the number of states the networks
will cycle through in an attractor. These values are
significantly lower than in the synchronous case however. For example, when K = 2, approximately 20% of
nodes change each synchronously updated cycle compared with 5% when updated asynchronously. The difference is to be expected because, in the asynchronous
case, “the lack of synchronicity increases the complexity of the RBN, enhancing the number of possible states
and interactions. And this complexity changes the attractor basins, transforming and enlarging them. This
reduces the number of attractors and states in attractors” (Gershenson 2002). As previously mentioned, in
the asynchronous case there are no cycle attractors,
only point and loose attractors.

Richard J. Preen, Larry Bull

0.4

0.3

0.2

0.1

0.0
0

10

20

30

40

50

60

70

80

90

100

T Cycles
(b) Asynchronous.

Fig. 2: The affect of K on a 13 node RBN.

wheel or random selection) and exploiting (the best action). In multistep problems a biased selection strategy
is often employed wherein exploration is conducted at
probability pexplr otherwise exploitation occurs (Lanzi
1999). An action set [A] is then built composed of all the
classifiers in [M] advocating the selected action. Next,
the action is executed in the environment and feedback
is received in the form of a payoff, P .
In a single-step problem, [A] is updated using the
current reward. The GA is then run in [A] if the average time since the last GA invocation is greater than the
threshold value, θGA . When the GA is run, two parent
classifiers are chosen (typically by roulette wheel selection) based on fitness. Offspring are then produced from
the parents, usually by use of recombination and mutation. Typically, the offspring then have their payoff,
error, and fitness set to the average of their parents’.
If subsumption is enabled and the offspring are sub-

Discrete and fuzzy dynamical genetic programming in the XCSF learning classifier system

sumed by either parent, it is not included in [P]; instead
the parents’ numerosity is incremented. In a multistep
problem, the previous action set [A]−1 is updated using a Q-learning (Watkins 1989) type algorithm and the
GA may be run as described above on [A]−1 as opposed
to [A] for single-step problems. The sequence then loops
until it is terminated after a predetermined number of
problem instances.
In XCSF each classifier also maintains a vector of a
series of weights, where there are as many weights as
there are inputs from the environment, plus one extra,
x0 . That is, each classifier maintains a prediction (cl.p)
which is calculated as a product of the environmental
input (st ) and the classifier weight vector (w):
X
cl.wi × st (i)
(1)
cl.p(st ) = cl.w0 × x0 +
i>0

Each of the input weights is initially set to zero, and
subsequently adapted to accurately reflect the prediction using a modified ∆ rule (Mitchell 1997). The ∆ rule
was modified such that the correction for each step is
proportional to the difference between the current and
correct prediction, and controlled by a correction rate,
η. The modified ∆ rule for the reinforcement update is
thus:
η
∆wi =
(P − cl.p(st ))st (i)
(2)
|st (i)|2
Where η is the correction rate and |st |2 is the norm of
the input vector st . The values ∆wi are used to update
the weights of the classifier cl with:
cl.wi ← cl.wi + ∆wi

(3)

Subsequently, the prediction error ǫ is updated with:
cl.ǫ ← cl.ǫ + β(|P − cl.p(st )| − cl.ǫ)

(4)

This enables a more accurate, piecewise-linear, approximation of the payoff (or function), as opposed to
a piecewise-constant approximation, and can also be
applied to binary problems such as the Boolean multiplexer and maze environments, resulting in faster convergence to optimality as well as a more compact rulebase (Loiacono and Lanzi 2008). See Wilson (2002) for
further details.

5 Discrete DGP-XCSF
To use asynchronous RBN as the rules within XCSF
(see example rule in Figure 3), the following scheme
is adopted. Each of an initial randomly created rule’s
nodes has K randomly assigned connections, here 1 ≤
K ≤ 5. There are initially as many nodes N as input

5

fields I for the given task and its outputs O, plus one
other, as will be described, i.e., N = I + O + 1. The first
connection of each input node is set to the corresponding locus of the input message. The other connections
are assigned at random within the RBN as usual. In
this way, the current input state is always considered
along with the current state of the RBN itself per network update cycle by such nodes. Nodes are initialised
randomly each time the network is run to determine
[M], etc. The population is initially empty and covering
is applied to generate rules as in the standard XCSF
approach.
Matching consists of executing each rule for T cycles
based on the current input. The value of T is chosen to
be a value typically within the basin of attraction of the
RBN. Asynchrony is here implemented as a randomly
chosen node being updated on a given cycle, with as
many updates per overall network update cycle as there
are nodes in the network before an equivalent cycle to
one in the synchronous case is said to have occurred.
See Gershenson (2002) for alternative schemes.
In this study, where well-known maze problems are
explored there are eight possible actions and accordingly three required output nodes. An extra matching
node is also required to enable RBNs to (potentially)
only match specific sets of inputs. If a given RBN has
a logical ‘0’ on the match node, regardless of its output
node’s state, the rule does not join [M]. This scheme has
also been exploited within neural LCS (Bull 2002). A
windowed approach is utilised where the output is decided by the most common state over the last W steps
up to T . For example, if the last few states on a node
updating prior to cycle T is 0101001 and W = 3, then
the ending nodes state would be ‘0’ and not ‘1’.
When covering is necessitated, a randomly constructed RBN is created and then executed for T cycles
to determine the status of the match and output nodes.
This procedure is repeated until an RBN is created that
matches the environment state.
Self-adaptive mutation was first applied within LCS
by Bull et al (2000) where each rule maintains its own
mutation rate µ. This is similar to the approach used
in evolution strategies (ES; Schwefel 1981) where the
mutation rate is a locally evolving entity in itself, that
is, it adapts during the search process. Self-adaptive
mutation not only reduces the number of hand-tunable
parameters of the evolutionary algorithm, it has also
been shown to improve performance.
Following Bull and Hurst (2003), mutation only is
used here. A node’s truth table is represented by a binary string and its connectivity by a list of K integers
in the range [1, N ]. Since each node has a given fixed
K value, each node maintains a binary string of length

6

Richard J. Preen, Larry Bull

M

Input 3

Out

4
Input 6

8

3

7

Input 2
Input 1
2

Input 5
Input 4

5

6

Prediction 1000. Error: 0.0. Accuracy: 1.0.
Experience: 822. GASetSize: 70.1. GATimeStamp: 99947

Node
Node
Node
Node
Node
Node
Node
Node
Node

0
1
2
3
4
5
6
7
8

(M):
(out):
(I):
(I):
(I):
(I):
(I):
(I):
(N):

Truth Table:
10011000100000001110011010101000
10
00011111
0001
11101110
0110110100001010
0001011101010101
0100
00010111

Connections:
7, 4, 0, 3, 1
3
Input1, 2, 5
Input2, 2
Input3, 6, 3
Input4, 2, 7, 6
Input5, 5, 2, 3
Input6, 3
3, 1, 5

Fig. 3: An evolved asynchronous dDGP-XCS 6-bit multiplexer rule.
2K which forms the entries in the look-up table for each
of the possible 2K input states of that node, that is, as
in the aforementioned work (Packard 1988) on evolving
CAs, for example. These strings are subjected to mutation on reproduction at the self-adapting rate µ for
that rule. Hence, within the RBN representation, evolution can define different Boolean functions for each
node within a given network rule, along with its connectivity map. Specifically, each rule has its own mutation
rate stored as a real number and initially seeded uniform randomly in the range [0.0, 1.0]. This parameter
is passed to its offspring. The offspring then applies its
mutation rate to itself using a Gaussian distribution,
i.e., µ′ = µeN (0,1) , before mutating the rest of the rule
at the resulting rate. Due to the need for a possible

different number of nodes within the rules for a given
task, the DGP scheme is also of variable length. Once
the truth table and connections have been mutated, a
new randomly connected node is either added or the
last added node is removed with the same probability
µ. The latter case only occurs if the network currently
consists of more than the initial number of nodes. In
addition, each rule maintains its own T value which is
initially seeded randomly between 1 and 50. Thereafter,
offspring potentially increment or decrement T by 1 at
probability µ. W is evolved in a similar fashion, however
it is initially seeded between 0 and T , and cannot be
greater than T . Thus DGP is temporally dynamic both
in the search process and the representation scheme.

Discrete and fuzzy dynamical genetic programming in the XCSF learning classifier system

Whenever an offspring classifier is created and no
changes occur to its RBN when undergoing mutation,
the parent’s numerosity is increased and mutation rate
set to that of the offspring.
6 Discrete DGP-XCSF experimentation
The simplest form of short-term memory is a fixed length
buffer containing the n most recent inputs; a common
extension is to then apply a kernel function to the buffer
to enable non-uniform sampling of the past values, e.g.
an exponential decay of older inputs (Mozer 1994). However it is not clear that biological systems make use
of such shift registers. Registers require some interface
with the environment which buffers the input so that it
can be presented simultaneously. They impose a rigid
limit on the duration of patterns, defining the longest
possible pattern and requiring that all input vectors
be of the same length. Furthermore, such approaches
struggle to distinguish relative temporal position from
absolute temporal position (Elman 1990).
Whereas many GP systems are expression based,
some have also utilised a form of memory or state.
For example, linear GP (Banzhaf et al 1997); indexed
memory (e.g., Teller 1994; Brave 1996; Angeline 1997);
and work on evolving data structures which maintain
internal state (e.g., Langdon 1998). In addition, some
systems have used (instead of evolved) data structures
to manipulate the internal state (e.g., PushGP; Spector and Robinson 2002). Recently, Poli et al (2009) explored the use of soft assignment and soft return operations as forms of memory within linear and tree-based
GP.
Here we explore and extend the hypothesis of inherent content-addressable memory existing within synchronous RBN due to different possible routes to a
basin of attraction (Wuensche 2004) for the asynchronous
case by maintaining the node states across each inputupdate-output cycle. A significant advantage of this approach is that each rule/network’s short-term memory
is variable-length and adaptive, that is, the networks
can adjust the memory parameters, selecting within the
limits of the capacity of the memory, what aspects of
the input sequence are available for computing predictions (Mozer 1994). In addition, as we use open-ended
evolution, the maximum size of the short-term memory
is also open-ended, increasing as the number of nodes
within the network grows.
Here, nodes are initialised at random for the initial
random placing in the maze but thereafter they are not
reset for each subsequent matching cycle. Consequently,
each network processes the environmental input and the
final node states then become the starting point for the

7

next processing cycle, whereupon the network receives
the new environmental input and places the network
on a trajectory toward a (potentially) different locally
stable limit point. Therefore, a network given the same
environmental input (that is, the agent’s current maze
perception) but with different initial node states (representing the agent’s history through the maze) may
fall into a different basin of attraction (advocating a
different action). Thus the rules’ dynamics are (potentially) constantly affected by the inputs as the system
executes.
We now apply dDGP-XCSF to two well-known multistep non-Markov maze environments that require memory to resolve perceptual aliasing: Woods101 (see Figure 4a) and Woods102 (see Figure 4b).
Each cell in the maze environments is encoded with
two binary bits, where white space is represented as
a ‘*’, obstacles as ‘O’, and food as ‘F’. Furthermore,
actions are encoded in binary as shown in Figure 4c.
The task is simply to find the shortest path to the food
(F) given a random start point. Obstacles (O) represent
cells which cannot be occupied. In Woods1 the optimal
number of steps to the food is 1.7, in maze4 optimal
is 3.5 steps, in Woods101 it is 2.9, and in Woods102
it is 3.23. A teletransportation mechanism is employed
whereby a trial is reset if the agent has not reached the
goal state within 50 discrete movements.
6.1 Woods101
The Woods101 maze (see Figure 4a) is a non-Markov
environment containing two communicating aliasing
states, that is, two positions which border on the same
non-aliasing state and are identically sensed, but require different optimal actions. Thus, to solve this maze
optimally, a form of memory must be utilised (with at
least two internal states). Optimal performance has previously been achieved in Woods101 through the addition of a memory register mechanism in LCS (Lanzi and
Wilson 2000), by a Corporate LCS using rule-linkage
(Tomlinson 2001), and by a neural LCS using recurrent
links (Bull and Hurst 2003). Furthermore, in a proof
of concept experiment, the cyclical directed graph from
NP has been shown capable of representing rules with
memory to solve Woods101, however it was only found
to do so twice in fifty experiments (Balan and Luke
2004).
Figure 5 shows the performance of dDGP-XCSF in
the Woods101 environment with P = 2000, ν = 5,
θGA = 25, θdel = 20, β = 0.2, η = 0.2, x0 = 1,
pexpl = 1.0, and Ninit = 20 (16 inputs, 3 outputs,
1 match node). Here, optimality is observed after approximately 6,000 trials (Figure 5a). This is similar to

8

Richard J. Preen, Larry Bull

O
*
*
*
O

O
*
O
O
O

O
*
*
F
O

O
*
O
O
O

O
*
*
*
O

35

O
O
O
O
O

(a) Woods101 environment.
Optimal number of steps is
2.9.

O O O O O O
O * O F O *
O * O * O *
O * * * * *
O * O * O *
O O O O O O
O * O * O *
O * * * * *
O * O * O *
O * O F O *
O O O O O O

dDGP-XCSF

30

Number of Steps to Goal

O
O
O
O
O

O
O
O
O
O
O
O
O
O
O
O

(b) Woods102 environment. Optimal
number of steps is 3.23.

Optimum (2.9)

25
20
15
10
5
0

0

5000

10000

15000

Trials

(a) Number of steps to goal (circle).
1.0

0.8
Macro-classifiers/2000
Mutation Rate

0.6

0.4

0.2

Cell
*
O
F

Binary
00
01
11

Actions
111 000 001
110
010
101 100 011

(c) Maze encoding.

Fig. 4: Experimental maze environments and encoding.

0.0
0

5000

10000

15000

Trials

(b) Average mutation rate (square) and number of macroclassifiers (circle).
40
35

the performance of LCS using a 1-bit memory register
(∼7,000 trials, P = 800; Lanzi and Wilson 2000). The
number of macro-classifiers in the population converges
to around 1800 (Figure 5b). Furthermore, the average
number of nodes in the networks increases by almost
one and the number of connections declines fractionally (Figure 5c). The mutation rate (also Figure 5b)
declines rapidly from approx 35% to its lowest point,
1.2%, around the 6,000 trial, which is at the same moment optimal performance is also observed. Lastly, Figure 5c conveys that the first thousand trials sees a rapid
increase in the number of cycles, T , (30.6 to 34.4) and
a rapid decrease in the value of W (17 to 14.7). Subsequently, T continues to increase, (although at a much
slower rate) along with the average number of nodes in
the networks; W remains stable at just fewer than 15.

Avg. Nodes

30

Avg. Connections

T
W

25
20
15
10
5
0

0

5000

10000

15000

Trials

(c) Average number of nodes (square), connections (diamond), T (circle) and W (triangle).

Fig. 5: dDGP-XCSF Woods101 performance.

Discrete and fuzzy dynamical genetic programming in the XCSF learning classifier system
25

6.2 Woods102

dDGP-XCSF
Optimum (3.23)

20
Number of Steps to Goal

The Woods102 maze (see Figure 4b) is a non-Markov
environment containing aliasing conglomerates, that is,
adjacent aliasing states. The introduction of aliasing
conglomerates increases the complexity of the learning task facing the agent significantly. “It would appear
that three memory-register bits are required to resolve
[the] perceptual aliasing. However, since the two situations occur in separate parts of the environment, there
is the possibility that an optimal policy could evolve in
which certain register bits are used in more than one
situation, thus requiring fewer bits in all. It is therefore
not clear how large a bit-register is strictly necessary”
(Lanzi and Wilson 2000). However, in practice, register redundancy was found to be important and an 8bit memory register was required within LCS to solve
the maze optimally, with 2 and 4-bit registers achieving only 4 and 3.7 steps respectively (Lanzi and Wilson 2000). Figure 6 shows the performance of dDGPXCSF in Woods102 with the same parameters used in
the prior experiment, however, here pexpl = 0.1 and
P = 20, 000. Although a population size of 20,000 may
seem disproportionate, a population of 2,000 classifiers
was required for Woods101, representing a scale up of
10×, which can be compared with the increase required
by LCS with a memory register (800 to 6,000, or 7.5×),
where the potential number of internal actions required
rises from 31 = 3 to 38 = 6561 (Lanzi and Wilson 2000),
thus resources are clearly not increasing as quickly as
the search space.
Optimality is observed after approximately 80,000
trials (Figure 6a), this is slower than LCS with an explicit 8-bit memory register (∼30,000 trials, P = 6000;
Lanzi and Wilson 2000). However here the size of the
memory did not need to be predetermined as it is inherent within the networks, and the action selection
policy remains constant, with constant GA activity, unlike in Lanzi and Wilson (2000). The number of macroclassifiers in the population converges to around 17,750
(Figure 6b). Furthermore, the average number of nodes
in the networks increases fractionally to 20.6 and the
number of connections declines on average from 2.95
to 2.82 (Figure 6c). The mutation rate (Figure 6b) declines rapidly over the first 40,000 trials from 32% to
5% and reaches its lowest point, 3.5%, at 100,000 trials.
Lastly, from Figure 6c it can be seen that on average T
increases from 30 to 35 and W from 17.5 to 20.5.

9

15

10

5

0

0

20000

40000

60000

80000

100000

Trials

(a) Number of steps to goal (circle).
1.0

0.8
Macro-classifiers/20000
Mutation Rate

0.6

0.4

0.2

0.0
0

20000

40000

60000

80000

100000

Trials

(b) Average mutation rate (square) and number of macroclassifiers (circle).
40
35
Avg. Nodes

30

Avg. Connections

T
W

25
20
15
10
5
0

0

20000

40000

60000

80000

100000

Trials

7 Fuzzy logic networks
FLN (Kok and Wang 2006; Cao et al 2007) can be
seen as both a generalization of fuzzy-CA and RBN,

(c) Average number of nodes (square), connections (diamond), T (circle) and W (triangle).

Fig. 6: dDGP-XCSF Woods102 performance.

10

Richard J. Preen, Larry Bull

where the Boolean functions from RBN are replaced
with fuzzy logical functions from fuzzy set theory. Thus,
FLN generalize RBN through a continuous representation and generalize fuzzy-CA through a less restricted
graph topology. Kok and Wang (2006) explored 3-gene
regulation networks using FLN and found that not only
were FLN able to represent the varying degrees of gene
expression but also that the dynamics of the networks
were able to mimic a cell’s irreversible changes into an
invariant state or progress through a periodic cycle.
FLN are defined as, given a set of N variables (genes),
F (t) = (F1 (t), F2 (t), ..., FN (t)),

(5)

Fi (t) ∈ [0, 1](i = 1, 2, ..., N )

index t represents time; and the variables are updated
by means of dynamic equations,
Fi (t + 1) = Λi (Fi1 (t), Fi2 (t), ..., FiK (t)

(6)

where Λi is a randomly chosen fuzzy logical function.
The total number of choices for fuzzy logical functions
is decided only by the number of inputs. If a node has
K(1 ≤ K ≤ N ) inputs, then there are 2K different
fuzzy logical functions. In the definition of FLN, each
node, Fi (t) has K inputs (see Figure 7). The membership function is defined as a function Λu : U → [0, 1]
where Λu is the degree of membership (Cao et al 2007).
In all work thus far, all nodes are updated simultaneously, that is, synchronously.
A number of different fuzzy logic sets have been
introduced since the original Max/Min method was
proposed. Other commonly used fuzzy logics include
CFMQVS, Probabilistic, MV, and gcd/lcm (Reiter
2002). As previously mentioned, the choice of fuzzy set
can result in significantly different behaviour. Therefore, in this paper a range of the most commonly used
logics is potentially selectable (see Table 1), leaving evolution to identify the most appropriate combinations for
a given problem.

Node 2 Encoding
Connections (x,y)

1

2

[1,3]
Function ID

1
3

min(1,x+y)

Current State

0.283331

Fig. 7: Example FLN and node encoding. Node 2 receives inputs from node 1 and 3 and performs a fuzzy
OR.

Table 1: Selectable fuzzy logic functions.
ID
0
1
2
3
4
5

Function
Fuzzy OR (Max/Min)
Fuzzy AND (CFMQVS)
Fuzzy AND (Max/Min)
Fuzzy OR (CFMQVS and MV)
Fuzzy NOT
Identity

Logic
max(x, y)
x×y
min(x, y)
min(1, x + y)
1−x
x

As previously mentioned, FLN are typically updated
synchronously, however asynchronous schemes in CA,
RBN, and fuzzy-CA have been shown to provide a number of benefits, such as modeling the dynamics of GRN
more realistically. Figure 8a shows the affect of K on
a 13 node FLN updated asynchronously and Figure 8b
when updated synchronously; results are an average of
100 experiments for each value of K. In contrast to
RBN where larger K results in an increased percentage
of nodes changing state per update cycle (Kauffman
1993), it can be seen that with FLN the greater the
value of K, the less the number of states the networks
will cycle through within an attractor. This is due to
the tendency of the fuzzy logic functions to gravitate
to extremes (i.e., 0 or 1) with increased inputs. After an initial rapid decline in the rate of change, the
networks begin to stabilise as the states fall into their
respective attractors. However, similar to RBN, it can
be seen that an asynchronous updating scheme results
in a lower percent of nodes changing state when compared to the synchronous case. In the asynchronous
case, when K = 2, the number of nodes changing state
converges to around 10% compared with 30% of synchronous nodes, and when K = 5 to approximately
2.5% compared with 7% of nodes in the synchronous
case.

8 Fuzzy DGP-XCSF
Whereas FLN have been used previously to model aspects of GRN, no prior studies have explored the evolution of the networks for computation. Furthermore, all
prior studies have only considered a synchronous updating scheme. To use asynchronous FLN as the rules
within XCSF (hereinafter, fDGP-XCSF), the following
scheme is adopted. Each of an initial randomly created
rule’s nodes has K randomly assigned connections, here
0 ≤ K ≤ 5, where a node with K = 0 thus retains a constant node state. There are initially as many nodes N as
input fields I for the given task and its outputs O, plus
one other, for matching, i.e., N = I + O + 1. The first
connection of each input node is set to the corresponding locus of the input message. The other connections

Discrete and fuzzy dynamical genetic programming in the XCSF learning classifier system

used). Further, each node’s connectivity is represented
as a list of M AX K integers (here M AX K = 5) in the
range [0, N ], where 0 represents no input to be received
on that connection. Each integer in the list is subjected
to mutation on reproduction at the self-adapting rate
µ for that rule. Hence, within the representation, evolution can select different fuzzy logic functions for each
node within a given network rule, along with its connectivity map.

1.0

K=2
K=3
K=4
K=5

Fraction of Nodes Changing State

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

9 Fuzzy DGP-XCSF experimentation

0.1

0.0
0

20

40

60

80

100

T Cycles
(a) Asynchronous.
1.0

K=2
K=3
K=4
K=5

0.9

Fraction of Nodes Changing State

11

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0.0
0

20

40

60

80

100

T Cycles
(b) Synchronous.

Fig. 8: The affect of K on a 13 node FLN.

are assigned at random within the FLN. Node states
are initialised at random for the first step of a trial
but thereafter they are not reset for each subsequent
matching cycle. The population is initially empty and
covering is applied to generate rules as in the standard
XCSF approach.
If a given FLN has a (real) value of fewer than 0.5 on
the match node, regardless of the state of its outputs,
the rule does not join [M] (see Figure 7). This scheme
has also been exploited within neural LCS (Bull 2002).
The output nodes are discretised in a similar fashion
where a state fewer than 0.5 translates to a binary
0, otherwise 1. Furthermore, a windowed approach is
utilised whereby the final state of each node is calculated as an average over the last W cycles to T .
A node’s function is represented by an integer which
references the appropriate operation to execute upon
its received inputs (see Table 1 for the fuzzy functions

9.1 2-D continuous gridworld environment
The 2-D continuous gridworld environment (Boyan and
Moore 1995) is a two dimensional environment wherein
the current state is a real valued coordinate (x, y) ∈
[0, 1]2 . The agent is initially randomly placed within
the grid and attempts to find the shortest path to the
goal, located in the upper right corner; more specifically, in this paper the goal is found when x + y > 1.9,
at which point the agent is given a fixed reward of 1000,
otherwise 0 is given. Any action that would take the
system outside of the environment moves the system
to the nearest boundary. A teletransportation mechanism is employed whereby a trial is reset if the agent
has not reached the goal state within 500 movements.
As actions, the agent may choose one of four possible
movements (north, south, east, or west) each of which
is a step size, s, of 0.05. The optimal number of steps is
thus 18.6. The continuous state space, combined with
the long sequence of actions required to reach the goal,
make the Continuous Gridworld one of the most challenging multistep problems hitherto considered by LCS
(Lanzi et al 2005).
Figure 9 shows the performance of fDGP-XCSF in
the continuous gridworld environment using the same
parameters used by Lanzi et al (2005). However, here
P = 20, 000, Ninit = 5 (2 inputs, 2 outputs, 1 match
node). From Figure 9a it can be seen that an optimal solution is learnt around 30,000 trials, which is
slower than XCSF with interval-conditions (∼15,000
trials, P = 10, 000; Lanzi et al 2005), however is similar
in performance to an MLP-based neural-XCSF (Howard
et al 2010). The average mutation rate within the networks (see Figure 9b) declines rapidly from 40% to 5%
after 10,000 trials and then declines at a slower rate
until reaching a bottom around 2.5% after 50,000 trials. The number of (non-unique) macro-classifiers (also
Figure 9b) initially grows rapidly, reaching a peak at
10,000 before declining to around 6,900. Furthermore,
from Figure 9c it can be seen that the average number
of nodes in the FLNs increases from 5 to 7.1 and the

12

9.2 Continuous-action frog problem
The frog problem (Wilson 2004, 2007) is a single-step
problem with a non-linear continuous-valued payoff function in a continuous one-dimensional space. A frog is
given the learning task of jumping to catch a fly that
is at a distance, d, from the frog, where 0 ≤ d ≤ 1.
The frog receives a sensory input, x(d) = 1 − d, before
jumping a chosen distance, a, and receiving a reward
based on its new distance from the fly, as given by:

x+a : x+a ≤1
P (x, a) =
(7)
2 − (x + a) : x + a ≥ 1
In the continuous-action case, the frog may select
any continuous number in the range [0,1] and thus the
optimal achievable performance is 100%.
Wilson (2007) presented a form of XCSF where the
action was computed directly as a linear combination of
the input state and a vector of action weights, and conducted experimentation on the continuous-action Frog
problem, selecting the classifier with the highest prediction for exploitation. Tran et al (2007) subsequently extended this by adapting the action weights to the problem through the use of an ES. Moreover, the exploration
action selection policy was modified from purely random to selecting the action with the highest prediction.
After reinforcement updates and running the ES, the
GA is invoked using a combination of mixed crossover
and mutation. They reported greater than 99% performance after an averaged number of 30,000 trials (P =
2000), which was superior to the performance reported
by Wilson (2007). More recently, Ramirez Ruiz et al
(2008) applied a fuzzy-LCS with continuous vector actions, where the GA only evolved the action parts of
the fuzzy systems, to the continuous-action frog problem, and achieved a lower error than Q-learning (discretized over 100 elements in x and a) after 500,000
trials (P = 200).
To accommodate continuous-actions, the following
modifications were made to fDGP-XCSF. Firstly, the
output nodes are no longer discretized, instead providing a real numbered output in the range [0,1]. After
building [M] in the standard way, [A] is built by selecting a single classifier from [M] and adding matching classifiers whose actions are within a predetermined
range of that rule’s proposed action (here the range,
or window size, is set to ±0.005). Parameters are then

60
55

fDGP-XCSF

50

Optimum (18.6)

45
Number of Steps to Goal

average number of connections within the networks remains near static around 2. Additionally, the average
value of W remains static around 10, while the value of
T increases slightly, on average, from 26 to 2̃7.

Richard J. Preen, Larry Bull

40
35
30
25
20
15
10
5
0

0

10000

20000

30000

40000

50000

Trials

(a) Performance (circle), error (square), macro-classifiers
(triangle) and mutation rate (diamond).
1.0

Macro-classifiers/20000
Mutation Rate

0.8

0.6

0.4

0.2

0.0
0

10000

20000

30000

40000

50000

Trials

(b) Average number of macro-classifiers (circle) and mutation rate (square).
30
27
24

Avg. Nodes
Avg. Connections

T
W

21
18
15
12
9
6
3
0

0

10000

20000

30000

40000

50000

Trials

(c) Average number of nodes (square), connections (diamond), T (circle) and W (triangle).

Fig. 9: fDGP-XCSF continuous grid(0.05) performance.

Discrete and fuzzy dynamical genetic programming in the XCSF learning classifier system

updated and the GA executed as usual in [A]. Exploitation functions by selecting the single best rule
from [M]; the following experiments compare the performance achieved using various criteria to select the
best rule from the match set. The parameters used here
are the same as used by Wilson (2004, 2007) and Tran
et al (2007), i.e., P = 2000, ν = 5, θGA = 48, θdel = 50,
ǫ0 = 0.01, β = 0.2, η = 0.2, x0 = 1. Only one output
node is required and thus Ninit = 3.
Figure 10 illustrates the performance of fDGP-XCSF
in the continuous-action frog problem. From Figure 10a
it can be seen that greater than 99% performance is
achieved in fewer than 4,000 trials (P = 2000), which
is faster than previously reported results (>99% after
30,000 trials, P = 2000; Tran et al 2007), (>95% after
10,000 trials, P = 2000; Wilson 2007), and with minimal changes resulting in none of the drawbacks; that
is, exploration is here conducted with roulette wheel
on prediction instead of deterministically selecting the
highest predicting rule, an approach more suitable for
online learning. Furthermore, in Tran et al (2007) the
action weights update component includes the evaluation of the offspring on the last input/payoff before
being discarded if the mutant offspring is not more accurate than the parent; therefore additional evaluations
are performed which are not reflected in the number of
trials reported.
From Figure 10b it can be seen that the average
number of (non-unique) macro-classifiers rapidly increases to approximately 1400 after 3,000 trials, before
converging to around 150; this is more compact than
XCSF with interval conditions (∼1400; Wilson 2007),
showing that fDGP-XCSF can provide strong generalisation. In addition, the networks grow, on average,
from 3 nodes to 3.5, and the average connectivity remains static around 1.9. The average mutation rate declines from 50% to 2% over the first 15,000 trials before
converging to around 1.2% and the average value of T
increases by from 28.5 to 31.5.

10 Conclusions
This paper has explored examples of a temporally dynamic graph-based representation updated with asynchronous parallelism (DGP). The DGP syntax presented
consists of each node receiving an arbitrary number of
inputs from an unrestricted topology (that is, recursive
connections are permitted), and then performing an arbitrary function. The representation is evolved under
a self-adaptive and open-ended scheme, allowing the
topology to grow to any size to meet the demands of
the problem space.

13

1.0

Performance
Error
0.8

Macro-classifiers/2000
Mutation Rate

0.6

0.4

0.2

0.0
0

20000

40000

60000

80000

100000

Trials

(a) Performance (circle), error (square), macro-classifiers
(triangle) and mutation rate (diamond).
35
30
Avg. Nodes
Avg. Connections

T

25
20
15
10
5
0

0

20000

40000

60000

80000

100000

Trials

(b) Average number of nodes (triangle), average connections (square) and average T (circle).

Fig. 10: fDGP-XCSF Continuous-action frog problem
performance.

In the discrete case, DGP is equivalent to a form of
RBN. It was shown that the XCSF LCS is able to design ensembles of asynchronous RBN whose emergent
behaviour can collectively solve discrete-valued computational tasks under a reinforcement learning scheme.
In particular, it was shown possible to evolve and retrieve the content-addressable memory existing as locally stable limit points (attractors) within the asynchronously (randomly) updated networks when the final node states from the previous match processing cycle become the starting states for the next environmental input. Furthermore, it was shown that the parameters controlling system sampling of the networks’ dynamical behaviour can be made to self-adapt to the

14

temporal complexities of the target environment. The
introduced system thus does not need prior knowledge
of the dynamics of the solution networks necessary to
represent the environment. In particular, the representation scheme was exploited to solve the Woods102 nonMarkov maze (that is, without extra mechanisms), a
maze which has only previously been solved by LCS
using an explicit 8-bit memory register.
A significant advantage of the memory inherent within
DGP is that each rule / network’s short-term memory
is variable-length and adaptive, that is, the networks
can adjust the memory parameters, selecting within the
limits of the capacity of the memory, what aspects of
the input sequence are available for computing predictions. In addition, as the topology is variable length,
the maximum size of the short term memory is openended, increasing as the number of nodes within the
network grows. Thus the maximum size of the contentaddressable memory does not need to be predetermined.
Subsequently, the generality of the DGP scheme was
further explored by replacing the selectable Boolean
functions with fuzzy logical functions, permitting the
application to continuous-valued domains. Specifically,
the collective emergent behaviour of ensembles of asynchronous FLN were shown to be exploitable in solving
continuous-valued input-output reinforcement learning
problems, with similar performance to MLP-based neuralXCSF in the continuous-valued multistep grid environment and superior performance to those reported previously in the frog problem.
Current research is exploring the possibilities of DGP
as a general representation scheme by which to solve
complex problems with LCS. In particular, problems
wherein the additional expressiveness of DGP is most
beneficial, such as those requiring memory and temporal prediction.

References
Ahluwalia M, Bull L (1999) A genetic programming classifier system. In: Proceedings of the genetic and evolutionary computation conference, Morgan Kaufmann, GECCO
’99, pp 11–18
Angeline PJ (1997) An alternative to indexed memory for
evolving programs with explicit state representations. In:
Proceedings of the 2nd Annual Conference on Genetic
Programming, Morgan Kaufmann, pp 423–430
Ashby WR (1952) Design for a Brain. John Wiley and Sons
Balan GC, Luke S (2004) A demonstration of neural programming applied to non-Markovian problems. In: Proceedings
of the 6th annual conference on Genetic and evolutionary
computation, ACM, GECCO ’04, pp 422–433
Banzhaf W, Nordin P, Keller RE, Francone FD (1997) Genetic Programming: An Introduction: On the Automatic
Evolution of Computer Programs and Its Applications.

Richard J. Preen, Larry Bull
The Morgan Kaufmann Series in Artificial Intelligence,
Morgan Kaufmann
Boyan J, Moore A (1995) Generalization in reinforcement
learning: Safely approximating the value function. In: Advances in Neural Information Processing Systems 7, MIT
Press, NIPS 1995, pp 369–376
Brave S (1996) Evolving recursive programs for tree search.
In: Advances in genetic programming, MIT Press, Cambridge, MA, USA, pp 203–220
Van den Broeck C, Kawai R (1990) Learning in feedforward
boolean networks. Physical Review A 42(10):6210–6218
Bull L (2002) On using constructivism in neural classifier systems. In: Merelo JJ, Adamidis P, Beyer HG (eds) Parallel
Problem Solving from Nature: PPSN VII, Lecture Notes
in Computer Science, vol 2439, Springer Berlin / Heidelberg, pp 558–567
Bull L (2009) On dynamical genetic programming: Simple
boolean networks in learning classifier systems. International Journal of Parallel, Emergent and Distributed Systems 24:421–442
Bull L, Hurst J (2003) A neural learning classifier system with
self-adaptive constructivism. In: Evolutionary Computation, 2003. CEC ’03. The IEEE Congress on, IEEE Press,
vol 2, pp 991–997
Bull L, O’Hara T (2002) Accuracy-based neuro and neurofuzzy classifier systems. In: Proceedings of the Genetic and Evolutionary Computation Conference, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA,
GECCO ’02, pp 905–911
Bull L, Preen RJ (2009) On dynamical genetic programming:
Random boolean networks in learning classifier systems.
In: Proceedings of the 12th European Conference on Genetic Programming, Springer-Verlag, Berlin, Heidelberg,
EuroGP ’09, pp 37–48
Bull L, Hurst J, Tomlinson A (2000) Self-adaptive mutation
in classifier system controllers. In: Meyer JA, Berthoz A,
Floreano D, Roitblat H, Wilson SW (eds) From Animals
to Animats 6, Proceedings of the Sixth International Conference on Simulation of Adaptive Behavior, MIT Press,
pp 460–468
Cao Y, Wang P, Tokuta A (2007) Gene regulatory network
modeling: A data driven approach. In: Wang P, Ruan
D, Kerre E (eds) Fuzzy Logic, Studies in Fuzziness and
Soft Computing, vol 215, Springer Berlin / Heidelberg,
pp 247–281
Di J, Lala PK (2007) Cellular array-based delay-insensitive
asynchronous circuits design and test for nanocomputing
systems. Journal of Electronic Testing: Theory and Applications 23:175–192
Di Paulo E (2001) Rhythmic and non-rhythmic attractors
in asynchronous random boolean networks. Biosystems
59:185–195
Elman JL (1990) Finding structure in time. Cognitive Science
14(2):179–211
Fogel LJ, Owens AJ, Walsh MJ (1965) Artificial intelligence
through a simulation of evolution. In: Biophysics and Cybernetic Systems: Proceedings of the 2nd Cybernetic Sciences Symposium, Spartan Book Co., Washington, D.C.,
USA, pp 131–155
Gershenson C (2002) Classification of random boolean networks. In: Proceedings of the eighth international conference on Artificial life, MIT Press, Cambridge, MA, USA,
pp 1–8
Glass L, Kauffman SA (1973) The logical analysis of continuous, non-linear biochemical control networks. Journal of
Theoretical Biology 39:1039–129

Discrete and fuzzy dynamical genetic programming in the XCSF learning classifier system
Harvey I, Bossomaier T (1997) Time out of joint: Attractors
in asynchronous random boolean networks. In: Proceedings of the Fourth European Artificial Life Conference,
MIT Press, pp 67–75
Hirasawa K, Okubo M, Katagiri H, Hu J, Murata J
(2001) Comparison between genetic network programming (GNP) and genetic programming (GP). In: Evolutionary Computation, 2001. Proceedings of the IEEE
Congress on, IEEE Press, vol 2, pp 1276–1282
Holland JH (1976) Adaptation. In: Rosen R, Snell FM (eds)
Progress in Theoretical Biology, vol 4, Academic Press
Inc., pp 263–293
Howard GD, Bull L, Lanzi PL (2010) A spiking neural
representation for XCSF. In: Evolutionary Computation
(CEC), 2010 IEEE Congress on, IEEE Press, pp 1–8
Ingerson TE, Buvel RL (1984) Structure in asynchronous cellular automata. Physica D: Nonlinear Phenomena 10:59–
68
Kantschik W, Banzhaf W (2002) Linear-graph GP - a new
GP structure. In: Proceedings of the 5th European Conference on Genetic Programming, Springer-Verlag, London, UK, EuroGP ’02, pp 83–92
Kauffman SA (1993) The Origins of Order: Self-Organization
and Selection in Evolution. Oxford
Kok T, Wang P (2006) A study of 3-gene regulation networks
using NK-boolean network model and fuzzy logic networking. In: Kahraman C (ed) Fuzzy Applications in Industrial Engineering, Studies in Fuzziness and Soft Computing, vol 201, Springer Berlin / Heidelberg, pp 119–151
Koza JR (1992) Genetic Programming. MIT Press
Landau S, Picault S, Drogoul A (2001) ATNoSFERES: a
model for evolutive agent behaviors. In: Proceedings of
the AISB’01 Symposium on Adaptive Agents and MultiAgent Systems
Landau S, Sigaud O, Schoenauer M (2005) ATNoSFERES
revisited. In: Proceedings of the 2005 conference on Genetic and evolutionary computation, ACM, New York,
NY, USA, GECCO ’05, pp 1867–1874
Langdon WB (1998) Genetic Programming and Data Structures: Genetic Programming + Data Structures = Automatic Programming!, Genetic Programming, vol 1.
Kluwer, Boston
Lanzi PL (1999) An analysis of generalization in the XCS
classifier system. Evolutionary Computation 7:125–149
Lanzi PL, Perrucci A (1999) Extending the representation
of classifier conditions part ii: From messy coding to Sexpressions. In: Proceedings of the genetic and evolutionary computation conference, Morgan Kaufmann, GECCO
’99, pp 345–352
Lanzi PL, Wilson SW (2000) Toward optimal classifier system
performance in non-Markov environments. Evolutionary
Computation 8:393–418
Lanzi PL, Loiacono D, Wilson SW, Goldberg DE (2005) XCS
with computed prediction in continuous multistep environments. In: Evolutionary Computation, 2005. The 2005
IEEE Congress on, IEEE Press, vol 3, pp 2032–2039
Lemke N, Mombach JCM, Bodmann BEJ (2001) A numerical investigation of adaptation in populations of random
boolean networks. Physica A: Statistical Mechanics and
its Applications 301:589–600
Loiacono D, Lanzi PL (2008) Computed prediction in binary
multistep problems. In: Evolutionary Computation, 2008.
CEC 2008. (IEEE World Congress on Computational Intelligence). IEEE Congress on, IEEE Press, pp 3350–3357
Mellor D (2005) A first order logic classifier system. In: Proceedings of the 2005 conference on Genetic and evolution-

15

ary computation, ACM, New York, NY, USA, GECCO
’05, pp 1819–1826
Mesot B, Teuscher C (2005) Deducing local rules for solving
global tasks with random boolean networks. Physica D:
Nonlinear Phenomena 211(1-2):88–106
Miller JF (1999) An empirical study of the efficiency of learning boolean functions using a cartesian genetic programming approach. In: Proceedings of the genetic and evolutionary computation conference, Morgan Kaufmann,
GECCO ’99, pp 1135–1142
Mitchell T (1997) Machine Learning. McGraw Hill
Moody JE, Darken C (1989) Fast learning in networks
of locally-tuned processing units. Neural Computation
1:281–294
Mozer MC (1994) Neural net architectures for temporal sequence processing. In: Weigend AS, Gershenfeld NA (eds)
Time Series Prediction: Forecasting the Future and Understanding the Past, Addison-Wesley, pp 243–264
Packard N (1988) Adaptation toward the edge of chaos. In:
Kelso J, Mandell A, Shlesinger M (eds) Dynamic Patterns
in Complex Systems, World Scientific, pp 293–301
Poli R, McPhee NF, Citi L, Crane E (2009) Memory with
memory in genetic programming. Journal of Artificial
Evolution and Applications 9:2:1–2:16
Preen RJ, Bull L (2009) Discrete dynamical genetic programming in XCS. In: Proceedings of the 11th Annual conference on Genetic and evolutionary computation, ACM,
New York, NY, USA, GECCO ’09, pp 1299–1306
Quick T, Nehaniv C, Dautenhahn K, Roberts G (2003) Evolving embedded genetic regulatory network-driven control
systems. In: Proceedings of the Seventh European Artificial Life Conference, Springer, Heidelberg, pp 266–277
Ramirez Ruiz JA, Valenzuela-Rendón M, Terashima-Marı́n
H (2008) QFCS: A fuzzy LCS in continuous multi-step
environments with continuous vector actions. In: Rudolph
G, Jansen T, Lucas SM, Poloni C, Beume N (eds) Parallel
Problem Solving from Nature: PPSN X, Springer-Verlag,
Berlin, Heidelberg, pp 286–295
Reiter CA (2002) Fuzzy automata and life. Complexity
7(3):19–29
Schmidt M, Lipson H (2007) Comparison of tree and graph
encodings as function of problem complexity. In: Proceedings of the 9th annual conference on Genetic and
evolutionary computation, ACM, New York, NY, USA,
GECCO ’07, pp 1674–1679
Schwefel HP (1981) Numerical Optimization of Computer
Models. John Wiley & Sons, Inc., New York, NY, USA
Shirakawa S, Ogino S, Nagao T (2007) Graph structured program evolution. In: Proceedings of the 9th annual conference on Genetic and evolutionary computation, ACM,
New York, NY, USA, GECCO ’07, pp 1686–1693
Sipper M (1997) Evolution of Parallel Cellular Machines.
Springer
Sipper M, Ruppin E (1997) Co-evolving architectures for cellular machines. Physica D 99:428–441
Smith SF (1983) Flexible learning of problem solving heuristics through adaptive search. PhD thesis, University of
Pittsburgh
Spector L, Robinson A (2002) Genetic programming and
autoconstructive evolution with the push programming
language. Genetic Programming and Evolvable Machines
3:7–40
Su MC, Chou CH, Lai E, Lee J (2006) A new approach
to fuzzy classifier systems and its application in selfgenerating neuro-fuzzy systems. Neurocomputing 69:586–
614

16
Teller A (1994) The evolution of mental models. In: Advances in genetic programming, MIT Press, Cambridge,
MA, USA, pp 199–219
Teller A, Veloso M (1996) Neural programming and an internal reinforcement policy. In: Koza JR (ed) Late Breaking Papers at the Genetic Programming 1996 Conference,
Stanford University, pp 186–192
Tomlinson
A
(2001)
CXCS:
Triggered
linkage.
Tech.
Rep.
UWELCSG01-003,
University
of
the
West
of
England,
URL
http://www.cems.uwe.ac.uk/lcsg/reports/uwelcsg01-003.ps.zip
Tran HT, Sanza C, Duthen Y, Nguyen TD (2007) XCSF with
computed continuous action. In: Proceedings of the 9th
annual conference on Genetic and evolutionary computation, ACM, New York, NY, USA, GECCO ’07, pp 1861–
1869
Turing AM (1948) Intelligent machinery. In: Evans CR,
Robertson ADJ (eds) Cybernetics: Key Papers, University Park Press, Baltimore, MD and Manchester (1968)
Valenzuela-Rendón M (1991) The fuzzy classifier system: A
classifier system for continuously varying variables. In:
Proceedings of the Fourth International Conference on
Genetic Algorithms, Morgan Kaufmann Publishers Inc.,
San Francisco, CA, USA, pp 346–353
Von Neumann J (1966) The Theory of Self-Reproducing Automata. University of Illinois
Watkins CJCH (1989) Learning from delayed rewards. PhD
thesis, Cambridge University
Werner T, Akella V (1997) Asynchronous processor survey.
Computer (USA) 30(11):67–76
Wilson SW (2000) Get real! XCS with continuous-valued inputs. In: Learning Classifier Systems, From Foundations
to Applications, Springer-Verlag, London, UK, pp 209–
222
Wilson SW (2001) Function approximation with a classifier system. In: Proceedings of the genetic and evolutionary computation conference, Morgan Kaufmann, GECCO
’01, pp 974–981
Wilson SW (2002) Classifiers that approximate functions.
Natural Computing 1:211–234
Wilson SW (2004) Classifier systems for continuous payoff
environments. In: Genetic and Evolutionary Computation
GECCO 2004, Lecture Notes in Computer Science, vol
3103, Springer Berlin / Heidelberg, pp 824–835
Wilson SW (2007) Three architectures for continuous action.
In: Proceedings of the 2003-2005 international conference
on Learning classifier systems, Springer-Verlag, Berlin,
Heidelberg, IWLCS’03-05, pp 239–257
Wuensche A (2004) Basins of attraction in network dynamics: A conceptual framework for biomolecular networks.
In: Schlosser G, Wagner GP (eds) Modularity in Development and Evolution, Chicago, University Press, pp 288–
311

Richard J. Preen, Larry Bull

