# Selected Completed Doctoral Thesis

### Stephen Kelly

Scaling Genetic Programming to Challenging Reinforcement Tasks through Emergent Modularity
: June 2018

**Abstract:** Algorithms that learn through environmental interaction and delayed rewards,
or reinforcement learning, increasingly face the challenge of scaling to dynamic,
high-dimensional environments. Video games model these types of real-world decision making and
control scenarios while being simple enough to implement within experiments. This work
demonstrates how emergent modularity and open-ended evolution allow genetic programming (GP)
to discover strategies for difficult gaming scenarios while maintaining relatively low model
complexity. Two related learning algorithms are considered: Policy Trees and Tangled Program
Graphs (TPG).
In the case of Policy Trees, a methodology for transfer learning is proposed which
specifically leverages both structural and behavioural modularity in the learner
representation. The utility of the approach is empirically evaluated in two challenging task
domains: RoboCup Soccer and Ms. Pac-Man. In RoboCup, decision-making policies are first
evolved for simple subtasks and then reused within a policy hierarchy in order to learn the
more complex task of Half-Field Offense. The same methodology is applied to Ms. Pac-Man, in
which case the use of task-agnostic diversity maintenance enables the automatic discovery of
suitable sub-policies, removing the need for a prior human-specified task decomposition. In
both task domains, the final GP decision-making policies reach state-of-the-art levels of play
while being significantly less complex than solutions from temporal difference methods and
neuroevolution.
TPG takes a more open-ended approach to modularity, emphasizing the ability to adaptively
complexify policies through interaction with the task environment. The
challenging Atari video game environment is used to show that this approach builds
decision-making policies that broadly match the quality of several deep learning methods while
being several orders of magnitude less computationally demanding, both in terms of sample
efficiency and model complexity. Finally, the approach is capable of evolving solutions to
multiple game titles simultaneously with no additional computational cost. In this case, agent
behaviours for an individual game as well as single agents capable of playing up to 5 games
emerge from the same evolutionary run.
### Ali Vahdat

Symbiotic evolutionary subspace clustering
: Nov 2012

**Abstract:** Application domains with large attribute spaces, such as genomics and text analysis,
necessitate clustering algorithms with more sophistication than traditional clustering
algorithms. More sophisticated approaches are required to cope with the large dimensionality
and cardinality of these data sets. Subspace clustering, a generalization
of traditional clustering, identies the attribute support for each cluster as well as the
location and number of clusters. In the most general case, attributes associated with
each cluster could be unique. The proposed algorithm, Symbiotic Evolutionary Subspace
Clustering (S-ESC) borrows from `symbiosis' in the sense that each clustering
solution is dened in terms of a host (a single member of the host population) and a
number of coevolved cluster centroids (or symbionts in an independent symbiont population).
Symbionts dene clusters and therefore attribute subspaces, whereas hosts
dene sets of clusters to constitute a non-degenerate solution. The symbiotic representation
of S-ESC is the key to making it scalable to high-dimensional data sets, while
an integrated subsampling process makes it scalable to tasks with a large number of
data items. A bi-objective evolutionary method is proposed to identify the unique
attribute support of each cluster while detecting its data instances. Benchmarking
is performed against a well-known test suite of subspace clustering data sets with
four well-known comparator algorithms from both the full-dimensional and subspace
clustering literature: EM, MINECLUS, PROCLUS, STATPC and a generic genetic
algorithm-based subspace clustering. Performance of the S-ESC algorithm was found
to be robust across a wide cross-section of properties with a common parameterization
utilized throughout. This was not the case for the comparator algorithms. Speci-
cally, performance could be sensitive to a particular data distribution or parameter
sweeps might be necessary to provide comparable performance. A comparison is
also made relative to a non-symbiotic genetic algorithm. In this case each individual
represents the set of clusters comprising a subspace cluster solution. Benchmarking
indicates that the proposed symbiotic framework can be demonstrated to be superior
once again. The S-ESC code and data sets are publicly available.
### Peter Lichodzijewski

A Symbiotic Bid-Based Framework for Problem Decomposition
using Genetic Programming: Feb 2011

**Abstract: (para 1 of 3)**
This thesis investigates the use of symbiosis as an evolutionary metaphor for problem decomposition using Genetic Programming. It begins by drawing a connection between lateral
problem decomposition, in which peers with similar capabilities coordinate their actions, and
vertical problem decomposition, whereby solution subcomponents are organized into
increasingly complex units of organization. Furthermore, the two types of problem
decomposition are associated respectively with context learning and layered learning. The thesis then proposes the Symbiotic Bid-Based framework modeled after a
three-staged process of symbiosis abstracted from biological evolution. As such, it is
argued, the approach has the capacity for both types of problem decomposition.
### Gunes Kayacik

Can the best
defense be a good offense? Evolving (mimicry) attacks for detector
vulnerability testing under a 'black-box' assumption: 2009 (co-supervised with Prof. Nur Zincir-Heywood)

**Abstract: (para 1 of 3)**
This thesis proposes a 'black-box' approach for automating attack generation by way of Evolutionary Computation. The
proposed 'black-box' approach employs just the anomaly rate or detection feedback from the detector. Assuming a
'black-box' access in vulnerability testing presents a scenario different from a 'white-box' access assumption, since
the attacker does not possess sufficient knowledge to constrain the scope of the attack. As such, this thesis
contributes by providing a 'black-box' vulnerability testing tool for identifying detector weaknesses and aiding
detector research in designing detectors which are robust against evasion attacks.
### Andrew R. McIntyre

Novelty Detection + Coevolution = Automatic Problem Decomposition: A framework for scalable
Genetic Programming Classifiers: Nov 2007

**Abstract: **
A novel approach to the classi cation of large and unbalanced multi-class data sets is
presented where the widely acknowledged issues of scalability, solution transparency,
and problem decomposition are addressed simultaneously within the context of the
Genetic Programming (GP) paradigm. A cooperative coevolutionary training environment
that employs multi-objective evaluation provides the basis for problem
decomposition and reduced solution complexity. Scalability is achieved through a
Pareto competitive coevolutionary framework, allowing the system to be readily applied
to large data sets without recourse to hardware-speci c speedups. A key departure
from the canonical GP approach to classi cation involves expressing the output
of GP in terms of a non-binary, local membership function (Gaussian), where it is
no longer necessary for an expression to represent an entire class. Decomposition
is then achieved through reformulating the classi cation problem as one of cluster
consistency, where individuals learn to associate subsets of training exemplars with
each cluster. Classi cation problems are now solved by several specialist classi ers
as opposed to a single `super' individual. Finally, although multi-objective methods
have been reported previously for GP classi cation domains, we explicitly formulate
the objectives for cooperative behavior. Without this the user is left to choose a
single individual as the overall solution from a front of solutions. This work is able
to utilize the entire front of solutions without recourse to heuristics for selecting one
individual over another or duplicating behaviors between di erent classi ers.
Extensive benchmarking is performed against related frameworks for classi cation
including Genetic Programming, Neural Networks, and deterministic methods.
In contrast to classi ers evolved using competitive coevolution alone, we demonstrate
the ability of the proposed coevolutionary model to provide a non-overlapping decomposition
or association between learners and exemplars, while returning statistically
signi cant improvements in classi er performance. In the case of the Neural Network
methods, benchmarking is conducted against the more challenging second order neural
learning algorithm of conjugate gradient optimization (previous comparisons limit
Neural Network training to rst order methods). The ensuing comparison indicated
that most data sets bene t from the proposed algorithm, which remains competitive
even against the well-established deterministic algorithms, such as C4.5.
### Garnett C. Wilson

Probabilistic Adaptive Mapping Developmental Genetic
Programming: March 2007

**Abstract: **
Developmental Genetic Programming (DGP) algorithms explicitly enable the search
space for a problem to be divided into genotypes and corresponding phenotypes. The
two search spaces are often connected with a genotype-phenotype mapping (GPM)
intended to model the biological genetic code, where current implementations of this
concept involve evolution of the mappings along with evolution of the genotype
solutions. This work presents the Probabilistic Adaptive Mapping DGP (PAM DGP)
algorithm, a new developmental implementation that provides research contributions in
the areas of GPMs and coevolution. The algorithm component of PAM DGP is
demonstrated to overcome coevolutionary performance problems as identified and
empirically benchmarked against the latest competing Adaptive Mapping algorithm with
both algorithms using the same (non-redundant) mapping encoding process. Having
established that PAM DGP provides a superior algorithmic framework given equivalent
mapping and genotype structures for the individuals, a new adaptive redundant mapping
is incorporated into PAM DGP for further performance enhancement and closer
adherence to developmental modeling of the biological code. PAM DGP with two
mapping types is then compared to the competing Adaptive Mapping algorithm and
Traditional GP with respect to three regression benchmarks. PAM DGP using redundant
mappings is then applied to two medical classification domains, where PAM DGP with
redundant encodings is found to provide better classifier performance than the alternative
algorithms. PAM DGP with redundant mappings is also given the task of learning three
sequences of increasing recursion order given a function set consisting of general (not
implicitly recursive) machine-language instructions; where it is found to more efficiently
learn second and third order recursive Fibonacci functions than the related developmental
systems and Traditional GP. PAM DGP using redundant encoding is also demonstrated
to produce the semantically highest quality solutions for all three recursive functions
considered (Factorial, second and third order Fibonacci). PAM DGP is shown for
regression, medical classification, and recursive problems to have produced its solutions
by evolving redundant mappings to emphasize appropriate members within relevant
subsets of the problem's original function set.
### Samuel Howse

NUMMSQUARED 2006a0 Explained, Including a new Well-Founded
Functional Foundation for
Logic, Mathematics and Computer Science: October 2006

**Abstract: **
Set theory is the standard foundation for mathematics, but often does not include rules of reduction
for function calls. Therefore, for computer science, the untyped lambda calculus or type theory
is usually preferred. The untyped lambda calculus (and several improvements on it) make functions
fundamental, but suffer from non-terminating reductions and have partially non-classical logics.
Type theory is a good foundation for logic, mathematics and computer science, except that, by making
both types and functions fundamental, it is more complex than either set theory or the untyped
lambda calculus. This document proposes a new foundational formal language called NummSquared that
makes only functions fundamental, while simultameously ensuring that reduction terminates, having a
classical logic, and attempting to follow set theory as much as possible. NummSquared builds on
earlier works by John von Neumann in 1925 and Roger Bishop Jones in 1998 that have perhaps not
received sufficient attention in computer science. A soundness theorem for NummSquared is proved.
Usual set theory, the work of Jones, and NummSquared are all well-founded. NummSquared improves upon
the works of von Neumann and Jones by having reduction and proof, by supporting computation and
reflection, and by having an interpreter called NsGo (work in progress) so the language can be
practically used. NummSquared is variable-free. For enhanced reliability, NsGo is an F#/C# .NET
assembly that is mostly automatically extracted from a program of the Coq proof assistant. As a
possible step toward making formal methods appealing to a wider audience, NummSquared minimizes
constraints on the logician, mathematician or programmer. Because of coercion, there are no types,
and functions are defined and called without proof, yet reduction terminates. NummSquared supports
proofs as desired, but not required.