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.
Three principles capture the essence of the proposed framework. First,
a bid-based approach to context learning is used to separate the
issues of `what to do' and `when to do it'. Whereas the former issue
refers to the problem-specific actions, e.g., class label
predictions, the latter refers to a bidding behaviour that identifies a
set of problem conditions. In this work, Genetic Programming is used
to evolve the bids casting the method in a non-traditional role as
programs no longer represent complete solutions. Second, the proposed
framework relies on symbiosis as the primary mechanism of inheritance
driving evolution, where this is in contrast to the crossover operator
often encountered in Evolutionary Computation. Under this evolutionary
metaphor, a set of symbionts, each representing a solution
subcomponent in terms of a bid-action pair, is compartmentalized
inside a host. Communication between symbionts is realized through
their collective bidding behaviour, thus, their cooperation is
directly supported by the bid-based approach to context
learning. Third, assuming that challenging tasks where problem
decomposition is likely to play a key role will often involve large
state spaces, the proposed framework includes a dynamic evaluation
function that explicitly models the interaction between candidate
solutions and training cases. As such, the computational overhead
incurred during training under the proposed framework does not depend
on the size of the problem state space.
An approach to model building, the Symbiotic Bid-Based framework is
first evaluated on a set of real-world classification problems which
include problems with multi-class labels, unbalanced distributions,
and large attribute counts. The evaluation includes a comparison
against Support Vector Machines and AdaBoost. Under temporal sequence
learning, the proposed framework is evaluated on the truck reversal
and Rubik's Cube tasks, and in the former case, it is compared with
the Neuroevolution of Augmenting Topologies algorithm. Under both
problems, it is demonstrated that the increased capacity for
problem decomposition under the proposed approach results in improved
performance, with solutions employing vertical problem decomposition
under temporal sequence learning proving to be especially effective.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:NSHD.ca#10222/13260 |
| Date | 22 February 2011 |
| Creators | Lichodzijewski, Peter |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
Page generated in 0.0018 seconds