@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).",
}
|