- title = "A Symbiotic Bid-Based Framework for Problem Decomposition using Genetic Programming",
- author = "Peter Lichodzijewski",
- school = "Dalhousie University",
- year = "2011",
- address = "Halifax, Canada",
- month = "22 " # feb,
- keywords = "genetic algorithms, genetic programming, problem decomposition, symbiosis, Coevolution, Machine Learning",
- bibsource = "OAI-PMH server at amican.webapps1.lac-bac.gc.ca",
- language = "en",
- oai = "oai:collectionscanada.gc.ca:NSHD.ca#10222/13260",
-
URL = "
http://hdl.handle.net/10222/13260",
-
URL = "
http://dalspace.library.dal.ca/bitstream/handle/10222/13260/Lichodzijewski_Peter.pdf",
- size = "330 pages",
-
abstract = "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 organised into increasingly complex
units of organisation. 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 modelled
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 compartmentalised inside a host. Communication between symbionts is realised 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.",
- notes = "broken Nov 2023 http://www.cs.dal.ca/news/presentations/2011-02-22-symbiotic-bid-based-framework-problem-decomposition-using-genetic-prog",
