|
|
Generative Fixation A Unified Explanation for the Adaptive Capacity of Simple Recombinative Genetic Algorithms A Dissertation by Computer Science Department, August, 2009
|
|
|
Abstract:
Recombinative genetic algorithms have been used in a wide range of engineering
and scientific fields to quickly procure usable solutions to poorly understood
combinatorial optimization problems. Unfortunately, despite the routine use of
these algorithms for over three decades, their remarkable adaptive capacity has
not been adequately accounted for. We develop, submit, and support the
generative fixation hypothesis---a unified explanation for the adaptive
capacity of simple recombinative genetic algorithms. This hypothesis is based on
two key inferences about the simple genetic algorithm: 1) this algorithm can
robustly and scalably tackle certain kinds of seemingly intractable
computational problems which are straightforwardly related to the open problem
of interacting attributes in data-mining, and 2) by iteratively tackling such
problems, the simple genetic algorithm can efficiently implement a very
reasonable general-purpose search heuristic called hyperclimbing. Because
hyperclimbing is sensitive, not to the local features of a search space, but to
certain global features, this heuristic is not susceptible to the kinds
of issues that waylay local search heuristics. We compare the generative fixation hypothesis with the building block hypothesis and argue that the former surpasses the latter on three counts: First, the former hypothesis can account for the adaptive capacity of a wider class of recombinative genetic algorithms. Second, the former hypothesis presumes less about the distribution of fitness over the chromosome set. Third, the former hypothesis can successfully pass a demanding test of validity. In breaking from the building block hypothesis, the generative fixation hypothesis reverts back to two classical positions in population genetics: 1) that fixation is the vehicle by which adaptive gains are secured, and 2) that the function of recombination is to prevent hitchhiking. On a third matter, that of the unit of selection, the generative fixation hypothesis is at odds with the position taken by orthodox neo-darwinists, which is that the unit of selection in an evolving population is always reducible to the unit of inheritance---that the gene, in other words, is the ultimate unit of selection. In contrast, the generative fixation hypothesis holds that the unit of selection can be a small irreducible set of unlinked or weakly linked genes. This difference between the two theories has crucial computational implications which we highlight. |