Collective Adaptation: The Sharing of Building Blocks   [CA] [BB]

@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",
  URL =          "http://www.cs.twsu.edu/~haynes/thesis.ps",
  size =         "147 pages (normal spacing)",
  abstract =     "Weak search heuristics utilize 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).",
}