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

by

Haynes, T., D.

Literature search on Evolutionary ComputationBBase ©1999-2013, Rasmus K. Ursem
     Home · Search · Adv. search · Authors · Login · Add entries   Webmaster
Note to authors: Please submit your bibliography and contact information - online papers are more frequently cited.

Info: 1998
Keywords:genetic algorithms, genetic programming
Abstract:
Weak search heuristics [SH] utilize minimal domain knowledge during the search process. Genetic algorithms (GA) [GA] [GAG] and genetic programming (GP) [GP] are population based weak search heuristics [SH] which represent candidate solutions as chromosomes. The Schemata Theorem forms the basis of the theory of how GAs process building blocks [BB] during the domain independent search for a solution to a given problem. Building blocks [BB] 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 [VL] 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 [BB] 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 [BB] be coding segments, [CS] which are those subsets of the chromosome that contribute fitness to the evaluation of the chromosome. Building blocks [BB] can be extracted from chromosomes and stored in a collective memory, [CM] which becomes a repository of partial solutions for both recently discovered building blocks [BB] and those discovered earlier. The contributions of this thesis are the mechanisms by which building blocks [BB] can be effectively shared both inside and outside chromosomes. The duplication of building blocks [BB] inside a chromosome is shown to increase the exploratory power of the weak search heuristics. [SH] The perturbation of a candidate solution will affect one copy of the building blocks [BB] 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 [CS] is significant in finding better partial solutions with the following weak search heuristics: GP, GA, random search [SH] [RS] (RS), hill climbing [HC] (HC), and simulated annealing (SA). [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 [CA] is the addition of the collective memory to [CM] 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 [CM] [SH] can extend the partial solutions inside the collective memory [CM] and these partial solutions can be transfered back into the chromosomes. The thesis empirically demonstrates that collective adaptation [CA] finds significantly better partial solutions with weak search heuristics (GP, GA, [SH] RS, HC, and SA).
URL(s):Postscript
(G)zipped postscript

Review item:

Mark as doublet (will be reviewed)

Print entry




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