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

Created by W.Langdon from gp-bibliography.bib Revision:1.4333

  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
  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

                 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 =        "http://www.cs.dal.ca/news/presentations/2011-02-22-symbiotic-bid-based-framework-problem-decomposition-using-genetic-prog",

Genetic Programming entries for Peter Lichodzijewski