Collective Adaptation: The Sharing of Building Blocks

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

@PhdThesis{haynes:thesis,
  author =       "Thomas Dunlop Haynes",
  title =        "Collective Adaptation: The Sharing of Building
                 Blocks",
  school =       "Department of Mathematical and Computer Sciences,
                 University of Tulsa",
  year =         "1998",
  address =      "Tulsa, OK, USA",
  month =        apr,
  keywords =     "genetic algorithms, genetic programming",
  broken =       "http://www.cs.twsu.edu/~haynes/thesis.ps",
  URL =          "http://tulsalabs.com/Documents/thesisDS.pdf",
  URL =          "http://blogs.tulsalabs.com/?p=274",
  size =         "147 pages (normal spacing). 208",
  abstract =     "Weak search heuristics use minimal domain knowledge
                 during the search process. Genetic algorithms (GA) and
                 genetic programming (GP) are population based weak
                 search heuristics which represent candidate solutions
                 as chromosomes. The Schemata Theorem forms the basis of
                 the theory of how GAs process building blocks during
                 the domain independent search for a solution to a given
                 problem. Building blocks are templates describing
                 subsets of the chromosome which have a small defining
                 length and are highly fit. The main differences between
                 typical GP and GA implementations are a variable length
                 tree versus a fixed length linear string representation
                 and a n-ary versus a binary alphabet. A consequence of
                 the differences is that what constitutes a building
                 block has been difficult to answer for GP and has led
                 to theories that the Schemata Theorem does not hold for
                 GP.

                 This thesis defines building blocks to be coding
                 segments, which are those subsets of the chromosome
                 that contribute fitness to the evaluation of the
                 chromosome. Building blocks can be extracted from
                 chromosomes and stored in a collective memory, which
                 becomes a repository of partial solutions for both
                 recently discovered building blocks and those
                 discovered earlier. The contributions of this thesis
                 are the mechanisms by which building blocks can be
                 effectively shared both inside and outside
                 chromosomes.

                 The duplication of building blocks inside a chromosome
                 is shown to increase the exploratory power of the weak
                 search heuristics. The perturbation of a candidate
                 solution will affect one copy of the building blocks
                 and if the fitness of the perturbed copy is not better
                 than the original, the duplicate copies may still
                 maintain the overall fitness of the chromosome. The
                 duplication of coding segments is significant in
                 finding better partial solutions with the following
                 weak search heuristics: GP, GA, random search (RS),
                 hill climbing (HC), and simulated annealing (SA). Each
                 algorithm is systematically validated in the clique
                 detection domain against a particular family of graphs,
                 which have the properties that the set of partial
                 solutions is known, the set of partial solutions is
                 larger than viable chromosome lengths, and pruning
                 algorithms are not effective.

                 Collective adaptation is the addition of the collective
                 memory to the weak search heuristic. The solution no
                 longer has to be found inside the chromosomes; the
                 chromosomes can collectively contribute partial
                 solutions such that the overall solution is formed
                 inside the collective memory. Strong search heuristics
                 can extend the partial solutions inside the collective
                 memory and these partial solutions can be transfered
                 back into the chromosomes. The thesis empirically
                 demonstrates that collective adaptation finds
                 significantly better partial solutions with weak search
                 heuristics (GP, GA, RS, HC, and SA).",
  notes =        "a ROUGH DRAFT available via
                 http://citeseer.ist.psu.edu/haynes96explicit.html

                 Directed by Sandip Sen",
}

Genetic Programming entries for Thomas D Haynes

Citations