1

A natural approach to studying schema processing
Submitted to the IEEE Transactions on Evolutionary Computation on 11/05/2017

arXiv:1705.04536v1 [cs.NE] 12 May 2017

Jack McKay Fletcher and Thomas Wennekers

Abstract—The Building Block Hypothesis (BBH) states that
adaptive systems combine good partial solutions (so-called building blocks) to find increasingly better solutions. It is thought
that Genetic Algorithms (GAs) implement the BBH. However,
for GAs building blocks are semi-theoretical objects in that they
are thought only to be implicitly exploited via the selection and
crossover operations of a GA. In the current work, we discover
a mathematical method to identify the complete set of schemata
present in a given population of a GA; as such a natural way
to study schema processing (and thus the BBH) is revealed. We
demonstrate how this approach can be used both theoretically
and experimentally. Theoretically, we show that the search space
for good schemata is a complete lattice and that each generation
samples a complete sub-lattice of this search space. In addition,
we show that combining schemata can only explore a subset of
the search space. Experimentally, we compare how well different
crossover methods combine building blocks. We find that for
most crossover methods approximately 25-35% of building blocks
in a generation result from the combination of the previous
generation’s building blocks. We also find that an increase in
the combination of building blocks does not lead to an increase
in the efficiency of a GA. To complement this article, we introduce
an open source Python package called schematax, which allows
one to calculate the schemata present in a population using the
methods described in this article.
Keywords—Genetic Algorithms, building block hypothesis,
schema processing, complete lattice, order theory, schemata,
schematic lattice, schematic completion

I. I NTRODUCTION
Genetic Algorithms (GAs) are a hugely popular method for
optimization and have found successes on many problems [1].
Sadly, unlike other optimization techniques such as gradient
decent [17], simulated annealing [3], [13], [14], Ant Colony
Optimization [7], [25] or Particle Swarm Optimisation [6],
[28], GAs lack a rigorous explanation of exactly why and on
what functions they perform well. There is, however, a chief
approach to studying the power GAs, which is by considering
the schemata GAs are processing.
Schemata are simple mathematical objects which describe
points and hyper planes in the space of all possible words
over an alphabet of the same length [16]. Specifically, a
schema is a word made with an additional symbol ∗ called
the wild card symbol, which stands for ‘dont’t care’. For
example, the schema over the binary alphabet 1 ∗ 1∗ represents
the set of binary strings which have a 1 in positions one
and three and a 1 or 0 in positions two and four. In this
Jack McKay Fletcher and Thomas Wennekers are with the Centre for
Robotics and Neural Systems (CRNS), University of Plymouth, Plymouth,
Devon, United Kingdom (contact jack.mckayfletcher@plymouth.ac.uk).

way, the wild card symbol is similar to a blank tile in the
popular board game Scrabble. Schemata have properties. For
a schema s, the order of s, denoted o(s) is the number of
non-wild card symbols (that is symbols which are not ‘∗’)
in s. For example, the order of the above schema is 2. The
defining length of s, denoted d(s) is the distance between the
first and last non wild card symbol. The above schema has a
defining length of 2. A word is said to be an instance of s
if it matches s. For example, the word 1111 is an instance
of the above schema. In the context of a GA, the fitness
of s in a population is the average fitness of all of it’s instances.
Holland, in his partly philosophical work on adaptation,
argues that any adaptive process test subsets of the search
space through schema [16]. As each individual in the search
space belongs to several schemata at once, by evaluating one
individual many schemata are implicitly sampled. The idea
being, if an individual is fit it suggests the schemata of which
it is an instance are also fit. Thus, by testing a few individuals
many schemata are sampled. This property is called implicit
or intrinsic parallelism. Holland claims that natural evolution
exploits this property. From this concept, Holland created a
statement about the schema processing performed by GAs:
Definition I.1. A building block is a low order, low defining
length and above average fitness schema.
Hypothesis I.1. The BBH (The building block hypothesis):
competent GAs find increasingly better solutions by combining
building blocks.
Holland’s idea of building blocks is threefold. Firstly, as
building blocks have above average fitness, they have a high
probability of surviving and generating offspring. Secondly,
as they have a low order, they have a low probability of being
disrupted by mutations. Thirdly, as they have a low defining
length they have a low probability of disruption because of
crossover. All of these properties point towards the BBH,
that is: building blocks surviving and being combined in
subsequent generations. Note that the BBH is a statement
about adaptive systems in general, but in this case it is applied
specifically to GAs.
The BBH was the putative explanation for the power of
GAs for a long time. Schema theorems, which provide
a lower bound on the expected number of instances of
a schema in one generation occurring in the subsequent
generation [5], [12], [21] seemed to add credence to the
BBH as they show that building blocks have a high chance
of surviving. However, in later times the BBH came under
many philosophical and theoretical criticisms. In his paper

2

titled ’The building block fallacy’ [27], Thorton questions the
reasoning leading to the BBH and proposes contradictions
between the schema theorem and the BBH. Others, such as
Vose calls the earlier theory of GA ”myths and folklore”
and argues there is a lack of a standard GA theory [29].
In Holland’s framing, the schemata being manipulated by
a GA are semi-theoretical objects in that they are not
directly manipulated by the genetic algorithm. Rather, it is
proposed that the distribution of offspring should change as
if the schemata of the parents had been sampled and combined.
There is one article which studies schema processing in
a non-theoretical manner. Namely, Mitchell et al.’s [19]
insightful work on building blocks. In this article, building
blocks are indirectly studied through “Royal Road Functions”.
“Royal Road Functions” are fitness functions which have
building blocks explicitly built into them. These functions
reward individuals for finding good partial solutions, in a
way setting up ‘stepping stones’ along the way to the optimal
solution. Assuming the BBH, one would expect to find an
optimal solution very quickly as ‘building blocks’ are written
directly into the fitness function. However, the authors find
that when the fitness function does not have stepping stones
it performs better, that is a GA finds the optimal solution
in a fewer number of steps. It is suggested that the reward
for partial solutions in Royal Road Functions causes early
convergence, specifically the GA gets stuck in local optima
created by the stepping stones. While the authors offer an
indirect insight into BBH, it is still unclear what exactly
happens to schemata in the course of a genetic algorithm.
The ‘building blocks’ in Mitchell et al.’s paper are somewhat
artificial as they are defined in the fitness function rather than
discovered by the population itself. It is not obvious if the
same findings would apply to ‘real’ building blocks found by
a GA. In practical terms, the most common application of the
BBH is as a heuristic in the design of efficient encodings for
GAs. In particular, encodings are often chosen as to allow
building blocks to be combined meaningfully by the genetic
operators [15].
We believe the fundamental problem with using the BBH
as a narrative for GAs (and with seeing GAs as schema
processors to begin with for that matter) is that there is no
method to observe schemata being manipulated by a GA,
as such it is hard, if not impossible to test accurately any
meaningful statement about the type of schema processing
performed by a GA. Thus, in the current work, we present
a natural method for identifying the set of schemata being
tested by a population. We call this method the ‘schematic
completion’. We also find that the schemata found by the
schematic completion always forms a mathematical structure
called a complete lattice, we call ‘the schematic lattice’.
Using these methods, one can observe the exact schema
processing performed by a GA by simply calculating the
schemata present in each population and thus. These methods,
we hope, are useful tools for studying GAs through the
conceptual lens of schema processing and we hope that they
will deepen the understanding of GAs. Specifically, we hope

to be able to explore what makes a function difficult or easy
for a GA to optimize, understand how useful it is to see
GAs as ‘schema processors’ and perhaps inform the design
of better selection, crossover and mutation methods as to
improve schema processing of a GA.
In the text that follows firstly the basics of order and
lattice theory are introduced, this theory will be used to
define our method for calculating the schemata present in a
populating. Secondly, schemata are formally defined and the
notions of schematic completion and the schematic lattice are
introduced. To demonstrate the usefulness of these methods,
in section 4 and 5, we show how these novel notion can
be used to study GAs both theoretically and experimentally.
In section 4, theoretically we show the search space for
good schemata is a complete lattice and that each generation
samples a complete sublattice of this search space. We also
find that combining schemata is not a good method to explore
the search space of schemata as in most cases only a subset
of the search space can be reached by combining schemata
alone. In section 5, we experimentally examine how well
various crossover methods combine building blocks. We
find that only 25-35% of building blocks in a generation
result from the combination of the previous generation’s
building blocks. We also find that an increase in building
block combinations does not correspond to increase in the
efficiency of the GA. In the appendix of this article, an open
source Python package called schematax is introduced, which
efficiently calculates the schematic completion and to draws
the schematic lattice. We encourage readers interested in the
following work to exploit this package for their research into
GAs.
It should be noted that the mathematical insights presented
in this article are not particularly difficult to understand
in and of themselves. However to situate schemata in the
broader mathematics of order and lattice theory some basic
mathematical definitions and proofs are required. If the reader
is not acquainted with this subject area we advise them to
look simply at the examples and figures in section 3 to intuit
the notions of the schematic completion and schematic lattice.
II. BACKGROUND M ATHEMATICS
In this section, we cover the background mathematics required to introduce the basic insights into schemata presented
in the next section. Many of the following definitions regarding
order theory and lattice theory are adapted from Ganter and
Wille’s book on Formal Concept Analysis [10] and also
Birkhoff’s seminal book on lattice and order theory [4]. If
these areas are understood, please skip ahead to the next
section. Firstly we cover Order and Lattice theory, secondly,
we introduce Closure Systems and Galois Connections.
A. Order and Lattice theory
Definition II.1. A relation ≤ is called a partial order on a set
S if for all a, b, c ∈ S it satisfies:
1) reflexivity: a ≤ a

3

2) antisymmetry: a ≤ b and b ≤ a =⇒ a = b
3) transitivity: a ≤ b and b ≤ c =⇒ a ≤ c
A partially ordered set (poset for short) is a pair (S, ≤) with
≤ being a partial order on the set S. We use a < b if a ≤ b
and a 6= b. ≥ denotes the inverse of ≤.
Definition II.2. A lower neighbour of an element b is another
element a such that there is no element c with: a < c < b. In
this case, b is an upper neighbour of a and we write a ≺ b
to indicate this. In the literature, it is also said as b covers a.
Every finite partially ordered set, (S, ≤) can be represented
by a Hasse diagram. Each element in S is depicted by a circle.
For any a, b ∈ S if a ≺ b a line is drawn between the circles
representing a and b. Using a Hasse diagram one can read off
any order relation: a < b iff there is a descending path from
b to a. Figure 1 shows two Hasse Diagrams.

Every complete lattice is of course a lattice. Moreover, every
finite non-empty lattice is a complete lattice.
Example II.1. The left Hasse Diagram in figure 1 is not
a lattice nor a complete lattice as the join on the top most
elements does not exist. However, the right Hasse diagram
in figure 1 is a complete lattice (and thus a lattice) as the
supremum and infimum exist for any subset of elements. Any
closed real interval [x, y] with ≤ under its normal interpretation
as an ordering is a complete lattice. However, any unbounded
set of real numbers is not a complete lattice, but is a lattice.
The power set of any non-empty set with ⊆ as an ordering
is an exemplary complete lattice. The Hasse diagram of the
complete lattice formed by (P({a, b, c}), ⊆) is shown in figure
2.
{a, b, c}

{a, c}

{a, b}

{b, c}

{a}

{b}

{c}

Fig. 1: Two Hasse diagrams with 8 elements

Definition II.3. A rank function, ρ, over a poset (M, ≤)
is a function which maps each element in M to the natural
numbers such that for x, y ∈ M the following two properties
are satisfied:
x ≤ y =⇒ ρ(x) ≤ ρ(y)
x  y =⇒ ρ(y) = ρ(x) + 1
Definition II.4. Let (M, ≤) be a poset and let A ⊆ M . A
lower bound of A is an element m ∈ M with m ≤ a for all
a ∈ A. An upper bound of A can be defined dually. If there
is a largest element in the set of all lower bounds
V of A, this
element is called the infimum of A, denoted A. Dually, if
there is a smallest element in the set of all upper bounds
W of
A, this element is called the supremum of A, denoted A.
If A = {x, y}, the infimum of A is called the join and is
denoted x ∧ y, dually the supremum of A is called the meet
and is denoted x ∨ y
Intuitively, one can think of the supremum of a A as the
“smallest element in M which is greater than or equal to all
elements in A”. The infimum of A can be seen as “the largest
element in M which is less than or equal to all elements in
A”.
Definition II.5. We call an ordered set L := (L, ≤) a lattice
if for every x, y ∈ L, x ∧ y and x ∨ y exist. We call (L,
V≤)
a complete lattice Wif for every X ⊆ L, the infimum X
and the supremum X always
exist. Every complete lattice,
W
L has a largest element L called the unit V
element of L,
denoted 1L . Dually it has a smallest element, L, called the
zero element of L, denoted 0L .

∅
Fig. 2: The complete lattice formed by (P({a, b, c}), ⊆).

Definition II.6. A subset A of a complete lattice L which is
closed under suprema and infima, specifically:
_ ^
X ⊆ A =⇒
X, X ∈ A
is called complete sublattice. If A is only closed under
suprema it is called a meet-subsemilattice. Dually, if A is
closed under infima only, it is called a join-subsemilattice.
Example II.2. The poset ({{a, b, c}, {a, b}, {b, c}, {b}}, ⊆) is
a complete sublattice of the complete lattice defined in figure
2. This complete sublattice can be seen in figure 3 below:
Definition II.7. Let (L, ≤) be a complete lattice. An element
a ∈ L is called an atom of L if 0L < a and there does not
exist an element x ∈ L such that 0L < x < a. L is called
atomic if every element b > 0L implies that b is an atom or
that b has an atom below it. That is, b ≥ a > 0. L is called
atomistic if every element in L can be given by the supremum
of a subset of the atoms.
Example II.3. The set of atoms of the complete lattice shown
in figure 2 is: {{a}, {b}, {c}}. This complete lattice is atomic
and atomistic. The complete lattice shown on the right of figure
1 is atomic, however it is not atomistic as the top element
cannot be reached by the supremum on any subset of the
atoms.

4

{a, b, c}

{a, b}

Example II.7. The complete lattice formed by the closure
system A appearing in the example above is seen in figure 4,
below:
{a, b, c}

{b, c}

{a, b}
{b}
Fig. 3: The complete lattice ({{a, b, c}, {a, b}, {b, c}, {b}}, ⊆). This
is a complete sublattice of the complete lattice (P({a, b, c}), ⊆)
shown in figure 2.

{a}

∅
B. Closure Systems and (monotone) Galois Connections
Definition II.8. A closure system on a set S is a set of
subsets of S which contains S and is closed under intersection.
Specifically, A ⊆ P(S) is called a closure system on S if
S ∈ A and:
\
X ⊆ A =⇒
X∈A
Example II.4. Consider, S = {a, b, c} and let A =
{{a, b, c}, {a, b}, {a}}. A is a closure system on S, as S
is included in A and A is closed under intersection as any
intersection of elements in A is also a member of A.
Definition II.9. A closure operator on a set S is map, cl :
P(S) 7→ P(S) which satisfies the following for all X, Y ⊆ S
1) extensity: X ⊆ cl(X).
2) monotonicity: X ⊆ Y =⇒ cl(X) ⊆ cl(Y ).
3) idempotency: cl(cl(X)) = cl(X).
Closure operators and closure systems are closely linked, as
can be seen in the following theorem.
Theorem II.5. If cl is a closure operator on a set S then the
set:
Acl := {cl(X)|X ⊆ S}
(the set of all closures of a closure operator) is a closure
system. Conversely if A is a closure system on S then the
following operator:
\
clA (X) := {a ∈ A|X ⊆ a}
Defines a closure operator.
There is a bijection between closure operators and closure
systems. Every closure operator has a corresponding closure
system and every closure system has a corresponding closure
operator. A closure system can be seen as the set of all closures
of a closure operator. Whats more, closure systems (and thus
closure operators) are closely linked with complete lattices, as
will be seen in the next proposition.
Proposition II.6. If A is a closure system thenV(A, ⊆) is a
complete
lattice, where for X
T
W ⊆ A the infinum, SX is given
by X and the supremum X is given by clA ( X). Every
complete lattice is isomorphic to the lattice of all closures of
a closure system.

Fig. 4: The complete lattice formed by the closure system A with ⊆
as an ordering.

Definition II.10. Suppose we have two partially ordered sets,
(A, ≤) and (B, ≤). Two montone functions over these sets,
F : A 7→ B and G : B 7→ A are called a Galois connection
of A and B if we have for all a ∈ A and b ∈ B:
F (a) ≤ b ⇐⇒ a ≤ G(b)
In this case, F is called the lower adjoint and G the upper
adjoint. Equivalently, if F and G satisfy the following conditions they also form a Galois Connection. For all a1 , a2 ∈ A
and all for call b1 ∈ B we have:
1) a1 ≤ a2 =⇒ F (a1 ) ≤ F (a2 )
2) a1 ≤ GF (a1 )
3) a1 ≤ G(b1 ) =⇒ F (a1 ) ≤ b1
Proposition II.8. The composition GF : A 7→ A is a closure
operator.
III.

S CHEMATA

In this section we define schemata and define two basic
operations, the expansion and compression. Secondly, using
these operators we define the notions of the schematic completion and the schematic lattice and prove properties about
these notions.
Let Σ be a finite alphabet which does not contain symbol ∗.
We use Σl to denote the set of all words of length l over Σ.
Definition III.1. The schematic alphabet of Σ is Σ with an
extra symbol, ∗, the wild card symbol. We use Σ∗ to denote
the schematic alphabet of Σ. Symbols in Σ∗ which are not the
wild card symbol are called fixed symbols.
Definition III.2. A schema is a word over Σ∗ . We use Σl∗ to
denote all schemata of length l over Σ∗ including the empty
schema, ∗ .
Example III.1. Let Σ be the binary alphabet, that is {1, 0}.
The schematic alphabet of Σ, denoted Σ∗ , is the alphabet
{1, 0, ∗}. An example of a schema in Σ3∗ is 1 ∗ ∗.

5

Definition III.3. For any schema s ∈ Σl∗ we define the
following operator ↑s, called the expansion of s, which maps
s to a subset of words in Σl :
l

↑s := {b ∈ Σ |bi = si or si = ∗ for each i ∈ {1, ..., l}}
where subscript i denotes the character at position i in a word
or schema. When s = ∗ then ↑s = ∅. More simply put, ↑s is
the set of all words in Σl that can be made by exchanging the
∗ symbols in s with symbols from Σ.
Example III.2. Continuing the example above, ↑1 ∗ ∗ =
{100, 110, 101, 111}. The 1 in the first position is fixed. Note
↑111 = {111} and ↑∗ = ∅.
Definition III.4. Conversely, for any A ⊆ Σl we define ↓A,
called the compression of A, which maps A on to a schema
s ∈ Σl∗
↓A := s
where s is a schema of length l such that the symbol at position
i in s is determined in the following way: if xi = yi for all
x, y ∈ A then si = xi otherwise si = ∗. If A = ∅ then
↓A = ∗ . One can think of this operator as stacking up all the
items in A and if all elements in a column are equivalent, the
symbol at that position in s takes this value, otherwise there
is a wild card symbol.
Example III.3. Let A = {100, 000, 010} then ↓A = ∗ ∗ 0.
Note if A = ∅ then ↓A = ∗ . If A = {100} then ↓A = 100
Definition III.5. Schemata can be ordered. For any a, b ∈ Σl∗
we say a ≤ b if and only if ↑a ⊆ ↑b. It follows that ≤ is
a partial ordering on a set of schemata from the reflexivity,
antisymmetry and transitivity of the subset relation.

definitions 6 and 7 are useful in proving properties about
schemata.
Proposition III.5. For any schema s ∈ Σl∗ , we have ↓↑s = s.
Proof: Let A = ↑s definition III.6 trivially yields ↓A = s,
thus ↓↑s = s.
Proposition III.6. For A ⊆ Σl , we have A ⊆ ↑↓A.
Proof: Let s = ↓A, definition III.7 trivially yields A ⊆ ↑s,
thus A ⊆ ↑↓A.
Proposition III.7. Compression is monotonic, that is for
A, B ⊆ Σl :
A ⊆ B =⇒ ↓A ≤ ↓B
Proof: Assume A ⊆ B we will show ↓A ≤ ↓B.
Proposition III.6 gives B ⊆ ↑↓B. Since A ⊆ B ⊆ ↑↓B the
transitivity of the subset relation yields A ⊆ ↑↓B. Let ↓A = a
and ↓B = b. Since we have A ⊆ ↑b, definition III.6 applied
to ↓A yields a ≤ b. Thus we have ↓A ≤ ↓B.
Proposition III.8. For A ⊆ Σl and b ∈ Σl∗ we have:
A ⊆ ↑b =⇒ ↓A ≤ b
Proof: We will assume A ⊆ ↑b and show ↓A ≤ b.
Proposition III.7 gives us, ↓A ≤ ↓↑b. Proposition III.5 yields
↓A ≤ b.
Lemma III.9. The compression and expansion operators form
a Galois connection, where ↓ is the lower adjoint and ↑ the
upper adjoint.

Example III.4. Again let Σ = {1, 0}. Consider the following
schema in Σ2∗ : ∗ , 11, 1∗, ∗∗. They are ordered in the following
way: ∗ ≤ 11 ≤ 1∗ ≤ ∗∗. This is because ↑∗ ⊆ ↑11 ⊆ ↑1∗ ⊆
↑ ∗ ∗ = ∅ ⊆ {11} ⊆ {11, 10} ⊆ {11, 10, 01, 00}.

Proof: Let A, B ⊆ Σl and s ∈ Σl∗ . From definition II.9,
it is sufficient to show:
1) A ⊆ B =⇒ ↓A ≤ ↓B
2) A ⊆ ↑↓A
3) A ⊆ ↑s =⇒ ↓A ≤ s
1) was shown in proposition III.7, 2) was shown in III.6 and
3) in proposition III.8 .

Definition III.6. It is possible to define compression in terms
of expansion:
↓A := s

Definition III.8. For a set A ⊆ Σl , we call the process
of calculating the compression on each subset of A, that is
{↓X|X ⊆ A}, the schematic completion of A, denoted S(A).

such that A ⊆ ↑s and for any r ∈ Σl∗

Example III.10. Let Σl
=
{1, 0}3 and A
=
{110, 100, 001, 000} the schematic completion of A, results
in the following set:

A ⊆ ↑r =⇒ s ≤ r
That is, ↓A is the schema whose expansion includes A and is
the smallest such schema to do so.
Definition III.7. Conversely we can define expansion in terms
of compression:
↑s := A
such that ↓A = s and for any B ⊆ Σl we have:
↓B = s =⇒ B ⊆ A
That is, ↑s is the largest subset of words whose compression
is equal to s.
We will soon see that definitions 3 and 4 of the expansion
and compression operators are useful computationally while

{001, 100, 000, 110, 00∗, ∗00, 1 ∗ 0, ∗ ∗ 0, ∗0∗, ∗ ∗ ∗, ∗ }
For example, the schema ∗00 comes from the compression on
the subset {110, 000}.
Theorem III.11. (The fundamental theorem of schemata)
For any A ⊆ Σl , the schematic completion of A, S(A) ordered
by ≤ forms a complete lattice, that is the poset (S(A), ≤) is a
complete lattice. We call this lattice
W the schematic lattice
S of
A. Let X ⊆ S(A), the supremum, X, is given by ↓(
↑s).
s∈X
V
T
The infimum, Y , is given by ↓{a ∈
↑s|a ∈ A}.
s∈X

Proof: Lemma III.9 tells us ↓ and ↑ form a Galois
connection, where ↓ is the lower adjoint and ↑ is the upper

6

adjoint. As such, proposition II.8 yields ↑↓ as a closure
operator. Hence, from Theorem II.5, {↑↓X|X ⊆ A} is a
closure system. Thus, the poset ({↑↓X|X ⊆ A}, ⊆) forms
a complete Lattice (proposition II.6). Proposition II.6 also
yields S
for Y ⊆ {↑↓X|X ⊆ T
A}, the supremum is given
by ↑↓ Y and the infimum,
Y . From the definition of
ordering over schemata, we then have ({↓X|X
⊆ A}, ≤)
V
as a complete
lattice
and
the
infimum,
Y
,
is
given by
T
↓{a ∈
↑s|a ∈ A}.

∗ ∗ l∗
∗el∗
∗elp
help

∗ell

kelp

yell

t ∗ l∗
tell

∗alk
talk

walk

s∈X

It is easy to check that the atoms of the schematic lattice
(S(A), ≤) is the set A and (S(A), ≤) is atomistic.
Example III.12. Continuing the above example, the schematic
lattice formed from schematic completion on A can be seen
in figure 5.

∗
Fig. 6: The complete lattice formed from the schematic completion
on X, that is (S(X), ≤). Notice, as each word in X has an l in the
3rd position the unit element of this lattice is ∗ ∗ l∗.

∗∗∗
∗∗0
1∗0

Proposition III.15. If we set, o0 (∗ ) = −1 then o0 is a rank
function over schemata.

∗0∗
∗00

Proof: To show o0 is a rank function over schemata, it is
sufficient to show for x, y ∈ Σl∗ :

00∗

1.) x ≤ y =⇒ o0 (x) ≤ o0 (y)
110

100

000

001

∗
Fig. 5: The schematic lattice formed by the schematic completion on
the set A = {110, 100, 001, 000} ordered by ≤, that is the complete
lattice (S(A), ≤)

Example III.13. Of course, the schematic completion is
not restricted to words over the binary alphabet. Let Σ =
{a, b, c, . . . , z} and consider the set X ⊆ Σ4 :
X := {help, kelp, yell, tell, talk, walk}
The schematic completion of this set gives us the schematic
lattice in figure 6.
We can more precisely define some of the original properties
of schema using the above definitions.
Definition III.9. The order (not to be confused with partial
order) of schema s ∈ Σl∗ is the number of fixed symbols in s
and is denoted o(s). The order of s can be equivalently defined
as:
o(s) := l − log|Σ| (|↑s|)
Similarly the antiorder, denoted o0 of s is the number of wild
card symbols in s, which can be defined as:

2.) x  y =⇒ o0 (y) = o0 (x) + 1
First we will show 1). Assume x ≤ y, using the definition of
ordering we have ↑x ⊆ ↑y. It follows then that |↑x| ≤ |↑y|, and
thus o0 (x) ≤ o0 (y). Now we show 2). Assume x  y we then
have ↑x ⊂ ↑y with |↑y| = |↑x| + |Σ|, thus o0 (y) = o0 (x) + 1.
Corollary III.15.1. Using the same method, it is possible to
show that the order of a schema is a dual rank function over
schemata if we make o(∗ ) = l + 1. That is for x, y ∈ Σl∗ :
1.) x ≤ y =⇒ o(x) ≥ o(y)
2.) x  y =⇒ o(x) = o(y) + 1
Definition III.10. A word a ∈ Σl is said to be an instance of
schema s if and only if a ∈ ↑s.
Example III.16. The word 111 is an instance of the schema
1 ∗ ∗ as 111 ∈ ↑1 ∗ ∗ = 111 ∈ {111, 110, 101, 100}
We now introduce some novel properties of schemata not
originally described in previous works.
Definition III.11. For some A ⊆ Σl , the confidence of a
schema s ∈ S(A) is given as:
|{a ∈ ↑s|a ∈ A}|
|↑s|

o0 (s) := log|Σ| (|↑s|)

In more simple terms, the confidence of s ∈ S(A) is the
proportion of ↑s that is found in A.

Example III.14. Let s = 11 ∗ ∗. We can count the number of fixed symbols to give us o(s) = 2. Equivalently
l − log|Σ| (|↑s|) = 4 − log2 (|{1100, 1110, 1101, 1111}|) =
4 − log2 (4) = 2.

The confidence of a schema is useful in GAs for
understanding how confident one can be in the fitness
assigned to a schema. In particular, the more instances of a
schema has, the more we can trust it’s fitness.

7

The following lemmas and proposition are useful for
computations over schemata as they allow us to determine
the ordering of schemata by considering only the characters
and wild cards rather than having to compute the expansion
explicitly.
Lemma III.17. Let A, B ⊆ Σl , a = ↓A and b = ↓B. A ⊆ B
if and only if for all i we have:
ai = bi or bi = ∗
Proof: This follows directly from the definition of compression. Let C = B \ A. If C is empty, then clearly ai = bi
for all i, otherwise, for any x ∈ C and any i, xi can either
differ from ai , thus bi = ∗ or xi can equal ai , thus bi = ai .
Proposition III.18. For a, b ∈ Σl∗ , a ≤ b if and only if for all
i
ai = bi or bi = ∗
Proof: Let a, b be any schema in Σl∗ .
( =⇒ ) We will assume a ≤ b and show ai = bi or bi = ∗
for all i. From the definition of order over schema we have
↑a ⊆ ↑b, let a0 = ↓↑a, b0 = ↓↑b, since ↑a ⊆ ↑b lemma III.18
yields
a0i = b0i or b0 = ∗
for all i. Proposition III.5 gives us ↓↑a = a and ↓↑b = b,
meaning a = a0 and b = b0 , thus:
ai = bi or bi = ∗
for all i.
( ⇐= ) We will assume (ai = bi or bi = ∗ for all i) and
show a ≤ b. From Lemma III.18, there exist A, B ⊂ Σl with
↓A = a and ↓B = b such that A ⊆ B.
Proposition III.6 yields: B ⊆ ↑b. Since we have A ⊆ B and
B ⊆ ↑b, the transitivity of the subset relation yields A ⊆ ↑b.
As ↓A = ↑a, we have ↑a ⊆ ↑b.
This concludes out order theoretical interpretation of
schemata. However, for brevity’s sake, many interesting many
properties regarding schemata have not been mentioned here.
For example a link to a area of mathematics called Formal
Concept Analysis, which is concerned with finding concept
hierarchies in object-feature relationships [10]. Secondly, as
schemata are a (small) subset of regular expressions, this
makes the schematic completion akin to the induction of
regular languages [18], [22] where the search space is known
to be a complete lattice [8].
In the subsequent section it is shown how these simple
insights into schemata, specifically the schematic completion
and the schematic lattice, can be used to study how combining
schemata explores the search space.
IV.

H OW DOES COMBINING SCHEMATA EXPLORE THE
SEARCH SPACE ?
It is common to visualize the search space of GAs as
a hypercube in which each schema defines a hyperplane

[31]. In this section, we offer a complementary view based
on the mathematics in the previous section. We show that
the search space of schemata is a complete lattice and that
each generation of a GA samples a complete sublattice of
this complete lattice. Finally, we consider how combining
schemata explores the search space.
For a GA working on binary strings (that is, Σ = {0, 1}) of
size n, the search space of all schemata is the set Σn∗ . If we
order this set the search space is revealed to be the complete
lattice (Σn∗ , ≤). We could also construct the search space by
using the schematic completion on the set of all possible
words of length n, meaning:
(Σn∗ , ≤) = (S(Σn ), ≤)
Figure 8 shows the search space of schemata for GAs working
on binary strings of length 3.
Given a generation Gt at time t of a GA, the schematic
completion on Gt , S(Gt ), yields at least a subset of the
schemata being tested by Gt . However, it is still unclear if
the schematic completion on Gt yields all the schemata being
tested by Gt . To explore this possible limitation, consider the
population
Gt = {1010, 1111, 1100, 1000},
The schematic completion on Gt returns the set:
{1111, 1010, 1100, 1000, 1∗1∗, 11∗∗, 10∗0, 1∗00, 1∗∗0, 1∗∗∗, ∗ }
Which forms the schematic lattice shown below in figure 7.
1 ∗ ∗∗
1 ∗ ∗0
1 ∗ 1∗

11 ∗ ∗

10 ∗ 0

1 ∗ 00

1111

1010

1100

1000

∗
Fig. 7: The complete lattice formed from the schematic completion
on the population Gt . That is, the lattice (S(Gt ), ≤)

Is S(Gt ) the set of all schemata being tested by population
Gt ? It is possible to argue that the schema ∗ ∗ 00 is being
tested by Gt as the individuals 1100 and 1000 both end
in 00 yet the schematic completion on Gt does not yield
∗ ∗ 00. Thus it follows that the schematic completion does not
return the complete set of all the schemata being tested by
Gt . However, we can see that whenever an individual ends
in 00, it also begins with 1. Thus ∗ ∗ 00 cannot be tested

8

without having a 1 in the beginning (as both 1100 and 1000
begin with a 1), hence the schema which is being sampled by
this population is 1 ∗ 00 which does appear in the schematic
lattice. Indeed, as the fitness of a schema is given by the
average of it’s instances the fitness of ∗ ∗ 00 and 1 ∗ 00 have
the same fitness, however 1 ∗ 00 is the accurate description of
the schema being tested. A similar argument can be made for
any schema which appears to be omitted, thus, the schematic
completion returns all schemata being sampled by Gt . Each
generation of a GA then defines a set of schemata, S(Gt ),
which is the set of schemata being sampled by Gt . When
S(Gt ) is ordered by ≤, it is a complete sublattice of the
search space (Σn∗ , ≤).
By calculating the schematic completion on the population for
each generation, one can observe how schemata change during
the course of a GA. There are many natural experiments
and questions which can be examined using this method (for
example, one could test how well various schema theorems
apply to a GA with a finite population size), however in this
section we will focus on the more fundamental question of
how combining schemata explores the search space.
It is proposed that a GA combines ‘good’ schemata,
however it is unknown how directly combining schemata
explores the space of all schemata. To investigate, a method
is required to identify when a schema results from the
combination of a set of schemata. To do this we introduce the
notion of schematic blending.
Definition IV.1. For X ⊆ Σl∗ the schematic blending of X,
denoted bl(X) is the schema given by
\
bl(X) := ↓(
↑s)
s∈X

If bl(X) returns the empty schema then X is said to be
unblendable, otherwise X is said to be blendable. Given a
set of schemata A, the set of all schematic blends in A, that
is {bl(x)|x ⊆ A} is denoted B(A).
Example IV.1. bl(11∗∗∗, ∗∗11∗) = 1111∗, 11∗∗∗ and 01∗∗∗
are unblendable, bl(1 ∗ 10 ∗ ∗, ∗110 ∗ 1) = 110 ∗ 1.
It is clear that the order of the schematic blend of A, (if
it is not empty) is greater than or equal to the order of any
member of A. In addition, when performing the schematic
blend on schemata which result from the schematic completion
on a set of words, it is common for the blend to result in
schemata which already exist in schematic completion. Indeed,
the following lemma explores this idea and is useful for
understanding how combining schemata explores the schema
space.
Lemma IV.2. (The schematic blending lemma) For a set of
schemata A ⊆ Σl∗ , bl(A) returns the largest schema s ∈ Σl∗
such that s ≤ s0 for all s0 in A.
Proof: Let A ⊆ Σl∗ . Then we have:
\
bl(A) = ↓(
↑s)
s∈A

Let:
bl(A) = t = ↓(↑s1 ∩ ↑s2 ∩ · · · ∩ ↑sn )
Thus from the definition of compression we have t as the
largest schema with:
↑t ⊆ ↑s1 and ↑t ⊆ ↑s2 and ↑t ⊆ ↑s3 and . . . and ↑t ⊆ ↑sn
and from the definition of partial ordering for schemata we
have:
t ≤ s1 and t ≤ s2 and t ≤ s3 and . . . and t ≤ sn
In simple terms this lemma says: blending a set of schemata
A returns the largest schema s ∈ Σl∗ which is smaller than all
elements in A. In this way the schematic blending is similar
to the infimum operator over the schematic lattice. However,
instead of returning a schema s ∈ A, a schema s ∈ Σl∗ is
required.
So far we understand this much: given a generation at
time t, Gt of a genetic algorithm, the schemata being tested
by this generation is the schematic completion of Gt , S(Gt ),
this samples a complete sub-lattice of the lattice all the
possible schemata. The set of schemata which can be reached
by blending these schemata is then B(S(Gt )). However,
the schematic blending lemma tells us that blending only
searches the spaces inbetween the layers of the lattice,
and not ‘sideways’ or upwards. What is more, schematic
blending is idempotent that is: B(B(S(Gt ))) = B(S(Gt )).
Thus, by combining schemata alone, only a search over the
lower neighbours of pre-existing schemata can be performed,
meaning only a subset of the space of all schemata can
be reached. Figure 8 demonstrates how blending explores
the space of all schemata and is a good visual summary of
the results from this section. Thus we conclude, blending
schemata alone is not a good tool for exploring the space of
all schemata.
It is proposed that the power of GAs comes through
the combination of a particular type of schemata, namely
building blocks. However, as combining schemata in general
is not a good exploratory tool, it sheds a serious doubt on
how useful combining building blocks is as a search tool.
Specifically, if a building block is not ‘enclosed’ within
the schematic lattice defined by the initial generation of a
GA, combining schemata alone will not discover it. This
suggests the disruption and construction of schemata through
the imperfect combination of schemata (via crossover)
and mutation may play a vital role in allowing a greater
exploration of the search space. This contrasts with the
traditional view of GAs, where the disruption of schemata via
crossover is traditionally seen as a nuisance as they hinder the
combination of good schemata [30], [31]. There has been some
work however which suggests that the construction of novel
schemata through crossover play a useful exploratory role [23].
In the next section, we demonstrate how the concepts
of the schematic completion and the schematic lattice can

9

***

00*

*00

0*0

000

*0*

0**

**0

**1

1**

*1*

*01

10*

0*1

1*0

01*

*10

010

101

001

100

011

110

1*1

*11

11*

111

e

Fig. 8: The search space for all schema of length three arranged as a complete lattice. The schemata surrounded by bold circles are those
sampled by the generation Gt = {010, 011, 001, 101, 100}, that is the elements in the complete sub-lattice S(Gt ). The schemata in dotted
circles are those which cannot be reached through any combination of schemata in S(Gt ), while the plain circles show the schemata which
can be reached through the combination schema in S(Gt ). This figure was made using the schematax package.

be used experimentally to observe the schema processing
performed by a GA.
V.

O BSERVING BUILDING BLOCKS

BBH states the building blocks in generation t + 1 should to
some degree result from the combination of building blocks
in generation t

Using this definition one can find the building blocks
present in a given generation by firstly using the schematic
completion on the generation to find all schemata being
tested, then by secondly filtering out the building blocks using
the definition above. In our framing, the BBH is a statement
about the map from a schematic lattice in generation t to
the schematic lattice in generation t + 1. In particular, the

However, before we examine how well building blocks
are combined using the above updated version of the building
block hypothesis and the notion of schematic blending, it is
first interesting to examine how the average order and defining
length of building blocks change over the course of a GA.
If the order and defining length of building blocks increase,
it suggests that building blocks are getting larger and more
clumped together (as suggested by the BBH). To investigate,
we consider the Canonical GA2 [11] solving the all ones
problem (where the fitness of an individual is the number of
ones found in the string). We use binary strings of length 64
and pick the mutation rate to be 0.005 and the population
size as 30. We run the GA for 120 generations, and for each
generation, we calculate the schematic completion on each to
yield all the schemata being tested by that generation, filter
out the building blocks using our modified definition of the
BBH above and then calculate the average order and defining
length of the set of building blocks. We plot the results in
Figure 9 averaged over 20 simulations, where each simulation
is started with a random initial population. In addition, to give
the reader an indication of what the building blocks may look
like for the all ones problem, we display the 3 building blocks
from generations, 0, 40, 80 and 120 from one simulation in
figure 9. As can be seen in Figure 9, the order and defining

1 It should be noted that when computing the average order, fitness and
defining length of schemata we do not include the empty schema nor schema
with no wildcards (i.e the individuals of the population).

2 The Canonical GA is a binary GA, with roulette wheel selection, single
point crossover and mutation.

In this section, we use the schematic completion to observe
the building blocks during the course of a GA. First, however, to study the building block hypothesis using the above
methods, we must more precisely define building blocks. In
Holland’s framing (definition I.1), the phrases ‘low order’ and
‘low defining length’ could refer to an absolute value, such
that ‘low order’ schema are schema whose order is less than
say 4. However, for the purpose of this article we take ‘low’ to
be relative to the given generation, so that ‘low order’ refers
to schemata with below average order, similarly ‘low defining
length’ refers to schemata with below average defining length.
Building blocks are then redefined as follows:
Definition V.1. A building block is a schema with below average order, below average defining length and above average
fitness 1 .

10

length of the building blocks is indeed increasing during the
course of a GA. It seems, at least for the all ones problem,
that the defining length and order of the building blocks
quickly increase, and then level out around generation 60.
The results in figure 9, hint at the BBH being implemented
GA. However, it is still unclear if and how many building
blocks are being explicitly combined by the genetic operators
of a GA. Perhaps the results in figure 9 are not best explained
by building blocks being combined but instead it is to
be expected when a population becomes less random. In
particular, when a set of words is more random the average
order and defining length of the schemata will be lower
because the words ‘agree’ less. As such, the less random the
population becomes (as is the case in a GA working on a
reasonable fitness function), the more the words ‘agree’ and
thus the schemata as result will have higher order and defining
length. It is interesting to note that the building blocks which
are found are far less neat than those suggested by [19] in the
royal road fitness functions.
For our second experiment, we use the concept of schematic
blending to examine exactly how many building blocks from
a generation t + 1 result from the combination of building
blocks in generation t. We test how well building blocks
are combined using different crossover methods. The GA is
setup the same as above, however to keep the calculation
of the schematic completion and blends tractable, we use
a population of size 12 working over individuals of length
16. We calculate the building blocks of generation t as
before, we then find the set of all schematic blends on the
building blocks, let’s call this set B. It is then checked what
percentage of the building blocks in generation t + 1 are
members of B. Figure 10 displays the results. The results,
in this case, are averaged over 100 simulations. On average
only approximately 25% − 35% of building blocks from a
generation are created by the combination of building blocks
from the previous generation in the case of 1 to 9 point
crossover as well as uniform crossover (UX). Interestingly,
it is proposed that UX disturbs the combination of building
blocks compared to traditional crossover methods [24], [26],
however we find it combines building blocks equally well as
other crossover methods. In general the reason why building
blocks are not combined optimally are several and mostly
well known: firstly individuals which are instances of building
blocks are not guaranteed to be selected by roulette wheel
selection for crossover, thus those building blocks cannot
be blended, secondly mutation can disrupt the blending of
building blocks if a fixed symbol is mutated after crossover,
thirdly crossover is not guaranteed to blend schemata if a
suboptimal crossover point is chosen. Thus, we can conclude
combining building blocks from generation t only accounts
for 25 − 35% of the building blocks in generation t + 1, the
remaining building blocks from generation t + 1 are created
by other means.
Probabilistic crossover (PX) which is similar to UX but
chooses bits using a weighted probability proportional

to the fitness of the parents, combines building blocks
the most effectively (due to it picking fitter bits with a
higher probability), yet finds the optimal solution in a later
generation. It is proposed that “competent genetic algorithms
combine building blocks” [16]. PX offers a counter-example
to this statement as it combines building blocks well, but
is not ‘competent’ in that it takes a greater number of
generations to find the optimal solution compared to other
crossover methods which combine building blocks poorly. It
is possible that greater combination of building blocks limits
the exploration of the GA. To explain further: the schematic
blending lemma tells that combining building blocks will only
explore the lower neighbors of preexisting building blocks,
thus the GA (with PX) explores this subset well, but does not
search other areas of the schematic lattice effectively. Much
like Mitchell et al. [19] we believe that the over emphasis of
building blocks forces the GA into a locally optimal sublattice
of the search space. We conclude that the ability of a genetic
algorithm to combine building blocks does correspond to how
quickly it will find the optimal solution and that the novel
creation of schemata (through methods other than combining
building blocks) is vital for a competent GA.

VI.

D ISCUSSION AND C ONCLUSION

The schematic completion and the schematic lattice, are
fruitful in the field of GAs both theoretically, as demonstrated
in the mathematics presented in sections 4, and experimentally
as demonstrated in section 5. It seems using both methods
however, inconsistencies are found the original schema processing theory for GAs. Specifically, section 4 shows that
combining schemata (and thus building blocks) explicitly is not
a good method to explore the search space of schemata as only
the lower neighbors of pre-existing schemata can be reached.
While section 5 shows that ‘competent’ GAs do not seem to
be very concerned with combining building blocks to begin
with, as only approximately 25-35% of building blocks seem
to come from the combination of the previous generations
building blocks for most crossover methods. In addition, an
increase in the combination of building blocks (as seen in
PX) does not correspond with an increase in efficiency of a
GA, rather, it hinders the GA. The reason for this follows
from the schematic blending lemma, specifically combining
building blocks only explores a subset of the search space,
thus the more a GA combines building blocks the more it gets
stuck in this subset. Finally, the increase of order and defining
length of building blocks over time (as is seen in figure 9), is
better explained by a decrease in randomness in the population
rather than by building blocks being combined. However, we
believe the most significant contribution of this article are
the methods introduced to explicitly calculate the schemata
present in a population and the identification underlying lattice
structures involved in schema processing. We hope that these
methods will deepen the understanding of GAs. If the reader
is interested in these methods, we encourage them to exploit
the schematax software which is introduced in the following
appendix section.

11

Average Order and Defining Length of Building Blocks

70
60

Generation 0:
***1*****11*****************************************************
***1***************0*******************1************************
********************************0**1****************************
Generation 40:
1*101*01011*1***1*******111**1*1*01011***111*1**100*111111*0*1*1
1*101*01011*1***1********110*111*0*0111**111*1**100*111111*0*1*1
1*101*01011*1***1********110*111*0*0*11**111*1**100*111111*0*1*1
Generation 80:
11*01*0101**110***0*111*01***1*110**11*10*11*11**00**11****0*1**
11*01*0101**110***0*111**1***1*110**11*10*11*11**00**11****0*1**
11*01**10*101100****111**1**11*1*****1110*11*11***0**11****0*1**
Generation 120:
*1*****1*1***1**110011110*11*01*1**1****0******0***1*1111*01*111
*1*****1*11**1**110011110*11*01*1**11***0******00**1*1111*01*111
*1*****1*11**1**110011110*11*01*1**1*1**0******00**1*1111*01*111

50
40
30
20
10
00

20

40

60
80
Generation

100

120

140

(a) The average order and defining length of building blocks
during the course of a GA (averaged over 20 simulations). In
this plot, the dashed line represents the average defining length
of the building blocks while the solid line represents the average
order of the building blocks.

(b) A selection of three building blocks from generations: 0, 40, 80 and
120.

Fig. 9

Crossover method
1-point
2-point
3-point
4-point
5-point
6-point
7-point
8-point
9-point
UX
PX

Solution found
107.3 ± 25.0
104.77 ± 28.27
101.16 ± 29.13
105.06 ± 29.55
94.19 ± 38.36
104.41 ± 30.23
103.11 ± 32.28
94.37 ± 36.06
99.51 ± 33.19
99.95 ± 31.20
119.88 ± 1.19

% Building Blocks combined
0.25 ± 0.16
0.37 ± 0.16
0.37 ± 0.17
0.37 ± 0.16
0.37 ± 0.16
0.36 ± 0.17
0.36 ± 0.16
0.36 ± 0.16
0.36 ± 0.17
0.36 ± 0.16
0.53 ± 0.18

Fig. 10: Time taken for various crossover methods to find the optimal
solution and the average percentage of building blocks combined by
the respective crossover method. UX here stand for uniform crossover,
while PX stands for probabilistic crossover. Each GA is solving the
all ones problem on strings of size 16, with a population of size 12
and uses roulette wheel selection. The results are averaged over 100
simulations, each starting with a random initial population.

VII.

S CHEMATAX - A P YTHON S OFTWARE PACKAGE FOR
SCHEMATA

To complement this article, we introduce an open source
python package which implements schemata and all of
their properties defined above. Importantly the package
allows one to compute the schematic completion and
to draw the schematic lattice, it can downloaded from
https://github.com/iSTB/python-schemata.

we introduce an algorithm, algorithm 1 (below), to compute
the schematic completion. This algorithm is based on the
algorithm presented in [20]. In this algorithm, the join
operation is used on each pair of schemata. This algorithm
exploits the commutativity (x ∨ y = y ∨ x) and idempotency
(x ∨ x = x) of the join operation. Meaning we do not have to
compute x ∨ x, and if x ∨ y is computed, we do not need to
compute y ∨ x. This allows the inner loop only to loop over a
subset of schemata. Additionally, we exploit the the atomistic
nature of the schematic lattice to build the lattice from the
bottom up.
Proposition VII.1. Algorithm 1’s worst case time complexity
is O(nkN 2 ) where N is the total number of schemata found, k
is the length of the strings and n the initial number of strings,
that is the size of P .
Proof: The outer loop (line 4) loops over P , thus clearly
looping n times. For each n, the inner loop (line 5) loops
pc · N − c times, where pc ≤ 1 is the proportion of N currently
found. join(x, y) takes k steps (line 6), where k is the length
of the strings. To check if s is not in the current set of schemata
found takes pc · N steps (line 7). So we have:
!
n
X
O
(pc · N − c) · k · (pc · N )
c=1

=O

n
X

!
N ·k·N

c=1

Naively calculating the schematic completion using the
definitions given above requires iterations over the powerset
and thus is very computationally expensive (O(2n )). Thus

2

=O N ·k

n
X
c=1

!
1

12

= O(nkN 2 )

[4]

To draw the schematic lattice we exploit the Graphviz
software [9] which allows one to to draw aesthetically pleasing
lattices efficiently. In addition, we use the package cython to
transfer the Python code into C [2]. This dramatically increases
the efficiency of the schematax package. For more information
the reader is referred to the documentation of the software
package at: https://github.com/iSTB/python-schemata.

[5]

Algorithm 1 Schematic completion

[8]

procedure C OMPLETE (P)
schemata ← P
c←1
for x in P do
check ← in schemata[c:]
for y in check do
s ← join(x, y)
if s ∈
/ schemata then
schemata = schemata ∪ {s}
10:
c←c+1
11:
return schemata ∪ {∗ }
1:
2:
3:
4:
5:
6:
7:
8:
9:

[6]

[7]

[9]

[10]
[11]
[12]

[13]

[14]

Algorithm 2 Join
procedure join(x, y)
k ← length(x)
s ← empty string
for for i in [0, . . . ,k] do
if x[i] = y[i] then
s[i] ← x[i]
else
s[i] ← ∗
9:
return s
1:
2:
3:
4:
5:
6:
7:
8:

[15]

[16]

[17]

[18]
[19]

ACKNOWLEDGMENT
This work was supported by the Marie Curie Initial Training
Network FP7-PEOPLE-2013-ITN (CogNovo, grant number
604764), the Engineering and Physical Sciences Research
Council (BABEL, grant number EP/J004561/1), and the University of Plymouth (through a PhD studentship to Jack McKay
Fletcher). We also wish to thank Diego Maranan, Sue Denham
and John Matthias for their valuable comments.
R EFERENCES
Chang Wook Ahn and R. S. Ramakrishna. A genetic algorithm for
shortest path routing problem and the sizing of populations. IEEE
Transactions on Evolutionary Computation, 6(6):566–579, Dec 2002.
[2] S. Behnel, R. Bradshaw, C. Citro, L. Dalcin, D.S. Seljebotn, and
K. Smith. Cython: The best of both worlds. Computing in Science
Engineering, 13(2):31 –39, 2011.
[3] Claude JP Bélisle. Convergence theorems for a class of simulated
annealing algorithms on rd. Journal of Applied Probability, pages 885–
895, 1992.

[20]
[21]
[22]

[23]

[1]

[24]
[25]

[26]

Garrett Birkhoff, Garrett Birkhoff, Garrett Birkhoff, and Garrett
Birkhoff. Lattice theory, volume 25. American Mathematical Society
New York, 1948.
Clayton L Bridges and David E Goldberg. An analysis of reproduction
and crossover in a binary-coded genetic algorithm. Grefenstette, 878:9–
13, 1987.
Maurice Clerc and James Kennedy. The particle swarm-explosion,
stability, and convergence in a multidimensional complex space. Evolutionary Computation, IEEE Transactions on, 6(1):58–73, 2002.
Marco Dorigo, Mauro Birattari, and Thomas Stützle. Ant colony
optimization. Computational Intelligence Magazine, IEEE, 1(4):28–39,
2006.
Pierre Dupont, Laurent Miclet, and Enrique Vidal. What is the
search space of the regular inference? In International Colloquium
on Grammatical Inference, pages 25–37. Springer, 1994.
Emden R. Gansner and Stephen C. North. An open graph visualization
system and its applications to software engineering. SOFTWARE PRACTICE AND EXPERIENCE, 30(11):1203–1233, 2000.
Bernhard Ganter, Rudolf Wille, and Rudolf Wille. Formal concept
analysis, volume 284. Springer Berlin, 1999.
David E Goldberg and John H Holland. Genetic algorithms and machine
learning. Machine learning, 3(2):95–99, 1988.
David E Goldberg and Kumara Sastry. A practical schema theorem for
genetic algorithm design and tuning. In Proceedings of the genetic and
evolutionary computation conference, pages 328–335, 2001.
Vincent Granville, Mirko Křivánek, and Jean-Paul Rasson. Simulated
annealing: A proof of convergence. Pattern Analysis and Machine
Intelligence, IEEE Transactions on, 16(6):652–656, 1994.
Chii-Ruey Hwang. Simulated annealing: theory and applications. Acta
Applicandae Mathematicae, 12(1):108–111, 1988.
Cezary Z Janikow and Zbigniew Michalewicz. An experimental
comparison of binary and floating point representations in genetic
algorithms. In ICGA, pages 31–36, 1991.
Holland John. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial
Intelligence. MIT Press, Cambridge, MA, 1992.
Krzysztof C Kiwiel. Convergence and efficiency of subgradient methods
for quasiconvex minimization. Mathematical programming, 90(1):1–25,
2001.
GA Miller and N Chomsky. Pattern conception. In Paper for Conference
on pattern detection, University of Michigan, 1957.
Melanie Mitchell, Stephanie Forrest, and John H Holland. The royal
road for genetic algorithms: Fitness landscapes and ga performance. In
Proceedings of the first european conference on artificial life, pages
245–254. Cambridge: The MIT Press, 1992.
Lhouari Nourine and Olivier Raynaud. A fast algorithm for building
lattices. Information processing letters, 71(5-6):199–204, 1999.
Riccardo Poli. Exact schema theorem and effective fitness for gp with
one-point crossover. In GECCO, pages 469–476, 2000.
Ray J Solomonoff. A new method for discovering the grammars of
phrase structure languages. In COMMUNICATIONS OF THE ACM,
volume 2, pages 20–20. ASSOC COMPUTING MACHINERY 1515
BROADWAY, NEW YORK, NY 10036, 1959.
Villiam M Spears and Kenneth A De Jong. On the virtues of
parameterized uniform crossover. In In Proceedings of the Fourth
International Conference on Genetic Algorithms, pages 230–237, 1991.
William M Spears. Recombination parameters. In The Handbook of
Evolutionary Computation, pages 1–3. University Press, 1997.
Thomas Stutzle and Marco Dorigo. A short convergence proof for
a class of ant colony optimization algorithms. IEEE Transactions on
evolutionary computation, 6(4):358–365, 2002.
Gilbert Syswerda. Uniform crossover in genetic algorithms. In Proceedings of the 3rd International Conference on Genetic Algorithms, pages
2–9, San Francisco, CA, USA, 1989. Morgan Kaufmann Publishers Inc.

13

[27]
[28]

[29]
[30]
[31]

Chris Thornton. The building block fallacy. Complexity International,
4, 1997.
Ioan Cristian Trelea. The particle swarm optimization algorithm:
convergence analysis and parameter selection. Information processing
letters, 85(6):317–325, 2003.
Michael D Vose. The simple genetic algorithm: foundations and theory,
volume 12. MIT press, 1999.
Michael D Vose and Gunar E Liepinsl. Punctuated equilibria in genetic
search. Complex systems, 5:31–44, 1991.
Darrell Whitley. A genetic algorithm tutorial. Statistics and computing,
4(2):65–85, 1994.

