Created by W.Langdon from gp-bibliography.bib Revision:1.4891
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).",
Directed by Sandip Sen",
Genetic Programming entries for Thomas D Haynes