November 18, 2011 at 2:25 pm (building block hypothesis, generative fixation, genetic algorithms, philosopy)
One of the mainstays of human engineering is the idea of hierarchical assembly—the assembly of useful low level modules (a.k.a. building blocks) into useful modules at higher levels. Artifacts ranging from nuclear submarines to enterprise software are all constructed in this fashion. The building block hypothesis holds that genetic algorithms also construct solutions using hierarchical assembly, and that the basic building blocks used by these algorithms are short chromosomal snippets that confer above average fitness. Tantalizing as this hypothesis may be, it is based on strong assumptions about the distribution of fitness over a search space. I’ve criticized these assumptions in my dissertation and have proposed a different hypothesis based on weaker assumptions. This alternate hypothesis is grounded in a different metaphor—generative fixation.
Though not as ubiquitously recognizable as hierarchical assembly is, generative fixation underlies progress in many areas. Like in the video industry for instance, which only really took off once the VHS/Betamax war had run its course. The “fixation” of VHS within this industry in essence generated new opportunities for advancement. For example, it permitted the development of the video rental business, which brought films from the back rooms of studio houses into living rooms everywhere. Had the tussle between VHS and Betamax continued, many of these opportunities might not have presented themselves. The economics of supporting two formats simultaneously would have been economically crippling for the fledgling industry.
VHS v. Betamax was a case where two contestants competed for dominance along a single dimension—the format accepted by video players. Consider a scenario consisting of multiple dimensions and multiple contestants in each dimension. Suppose, moreover, that no contestant in any dimension is outright superior. That is, the superioriority/non-superiority of the contestants in each dimension is dependent on the state of the contests in the other dimensions. This scenario describes the most commonly arising situation in natural evolution. Here, the “dimensions” are genetic loci, and the “contestants” are alleles. (Statistically, the scenario just described is more likely than one where one or more locus has an allele that is superior regardless of the frequencies of the alleles at other loci.)
The danger in such cases is that progress will stall because no contestant will come to dominate its dimension. The generative fixation hypothesis holds that in a system undergoing recombinative evolutionary dynamics, progress will continue. Although no locus has an allele that is outright superior, a small number of alleles belonging to different dimensions that play nice together (i.e. confer above average fitness as a group) will come to dominate their respective dimensions. In doing so, they will set the stage for the next multi-dimensional contest over the remaining dimensions. And so on.
I’ve demonstrated the genetic algorithm’s ability to scaleably identify and fix synergistic sets of unlinked non-competing alleles in a recent manuscript and in my dissertation.
Leave a Comment
March 15, 2011 at 10:33 pm (analytic technique, Bit Frequency Visualization, building block hypothesis, combinatorial optimization, decimation, evolutionary biology, genetic algorithms, hyperclimbing, hyperscapes, max-sat, population genetics, survey propagation, symmetry-analysis, visualization)
Tags: new manuscript
I’m preparing chapter 4 of my dissertation for submission to a journal.
Manuscript: http://s3.amazonaws.com/burjorjee/www/hyperclimbing_hypothesis.pdf
Abstract:
We submit the hyperclimbing hypothesis—an explanation for adaptation in genetic algorithms with uniform crossover (UGAs). Hyperclimbing is a stochastic search heuristic that works by decimating a search space, i.e. by iteratively fixing the values of small numbers of search space attributes. Global decimation is known to be an effective way to approach large instances of hard constraint satisfaction problems. The hyperclimbing hypothesis holds that UGAs work by implicitly implementing efficient global decimation. Proof of concept for this hypothesis comes from the use of a novel analytic technique involving the exploitation of algorithmic symmetry. We also present experimental results that show that a simple tweak inspired by the hyperclimbing hypothesis significantly improves the performance of a UGA on an instance of Uniform Random MAX-3SAT . The hyperclimbing hypothesis suggests that other kinds of evolutionary algorithms may also work by implicitly implementing efficient global decimation.
Leave a Comment
October 12, 2010 at 9:55 pm (analytic technique, Bit Frequency Visualization, building block hypothesis, combinatorial optimization, decimation, generative fixation, genetic algorithms, genetic algorithms, hyperclimbing, max-sat, survey propagation, symmetry-analysis, visualization)
Tags: presentation
Yesterday, I presented my research on genetic algorithms at the University of Washington.
Talk abstract
My slides
Leave a Comment
August 18, 2009 at 10:23 pm (active learning, Bit Frequency Visualization, building block hypothesis, combinatorial optimization, data mining, epistasis, evolutionary biology, function of recombination, generative fixation, genetic algorithms, genetics, hyperclimbing, hyperscapes, machine learning, max-sat, occam's razor, philosophy of science, philosopy, population genetics, QTL, sublinear computation)
I deposited my dissertation today.
Click here to see the final version (single spaced for easy reading).
3 Comments
July 22, 2009 at 11:07 pm (building block hypothesis, generative fixation, genetic algorithms, philosophy of science)
Tags: non-technical, philosophical
From the preface to my dissertation:
The foundations of most computer engineering disciplines are almost entirely mathematical. There is, for instance, almost no question about the soundness of the foundations of such engineering disciplines as graphics, machine learning, programming languages, and databases. An exception to this general rule is the field of genetic algorithmics, whose foundation includes a significant scientific component.
The existence of a science at the heart of this computer engineering discipline is regarded with nervousness. Science traffics in provisional truth; it requires one to adopt a form of skepticism that is more nuanced, and hence more difficult to master than the radical sort of skepticism that suffices in mathematics and theoretical computer science. Many, therefore, would be happy to see science excised from the foundations of genetic algorithmics. Indeed, over the past decade and a half, much effort seems to have been devoted to turning genetic algorithmics into just another field of computer engineering, one with an entirely mathematical foundation.
Broadening one’s perspective beyond computer engineering, however, one cannot help wondering if much of this effort is not a little misplaced. Read the rest of this entry »
Leave a Comment
October 18, 2008 at 8:30 pm (building block hypothesis, epistasis, genetic algorithms, occam's razor, philosophy of science, philosopy, population genetics)
Tags: new manuscript, overview, philosophical
Abstract: Skepticism of the building block hypothesis has previously been expressed on account of the weak theoretical foundations of this hypothesis and anomalies in the empirical record of the simple genetic algorithm. In this paper we focus on a more fundamental cause for skepticism—the extraordinary strength of some of the assumptions undergirding the building block hypothesis. As many of these assumptions have been embraced by the designers of so called “competent” genetic algorithms, our critique is relevant to an appraisal of such algorithms. We argue that these assumptions are too strong to be acceptable without additional evidence. We then point out weaknesses in the arguments that have been provided in lieu of such evidence.
Download manuscript
Leave a Comment
September 4, 2007 at 10:18 am (building block hypothesis, genetic algorithms)
Tags: non-technical
From the introduction of a manuscript that I recently submitted for review
Perceptions of the abilities and limitations of the SGA (and hence the kinds of problems that it can and cannot solve) have been heavily influenced by a theory of adaptation called the building block hypothesis (Goldberg, 1989; Mitchell, 1996; Holland, 1975, 2000). This theory of adaptation has its genesis in the following idea: maybe small groups of closely located co-adaptive alleles propagate within an evolving population of genomes in much the same way that single adaptive alleles do in Fisher’s theories of sexual evolution (Fisher, 1958). Holland called such groups of alleles building blocks. This idea can be taken one step further: maybe small groups of co-adaptive building blocks propagate within an evolving population of genomes in much the same way that single building blocks do. Such groups can be thought of as higher-level building blocks. Pursuing this idea to the fullest extent, maybe Read the rest of this entry »
Leave a Comment
September 4, 2007 at 9:49 am (building block hypothesis, genetic algorithms)
Tags: non-technical
Adaptation in selecto-recombinative genetic systems is widely believed to occur by the recombination of pre-adapted genetic material. This belief is at the core of the paradigm under which most GA and all EDA research currently occurs. It underlies the construction of several new varieties of genetic algorithms that purportedly work by combining pre-adapted genetic material in some sophisticated way (e.g. cohort GAs, messy GAs, LLGA, ECGA, BOA, hBOA, etc.).
In this paradigm, each post-selection population is thought to harbor “good” genetic material. Recombination operators, and estimation of distribution procedures, are thought drive adaptation by composing this material to produce good or better individuals in the next generation.When adaptation stalls it is thought to be because “good” genetic material is unavailable, or because recombination of this material was not performed effectively.
Let us call this general set of beliefs the Compositional Paradigm. This paradigm draws its support from Holland’s Building Block Hypothesis. Its widespread acceptance in the GA community signals Read the rest of this entry »
Leave a Comment
