Generative Fixation

A Unified Explanation for the Adaptive Capacity of
Simple Recombinative Genetic Algorithms

A Dissertation by

Keki M. Burjorjee

Computer Science Department,
Brandeis University

August, 2009

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.