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