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
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
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
May 23, 2008 at 7:50 pm (combinatorial optimization, epistasis, genetic algorithms, genetics, QTL, symmetry-analysis)
Tags: empirical, rough-draft, technical
Researchers studying the foundations of genetic algorithms have not, to the best of my knowledge, identified a non-trivial computational problem that a simple GA can solve robustly and scaleably (I’ve previously raised this issue here) . In my opinion, this singular fact is the most clear evidence for the inadequacy of current paradigm within which we understand/study the adaptive capacity of GAs—the question of what GAs are good for is, after all, intimately related to the question of how GAs work.
In a draft of one of my dissertation chapters I identify a hard computational problem and show that a GA can solve it robustly and scalably. Remarkably, this problem is closely related to a hairy statistical problem in computational biology. How might a GA leverage this kind of computational ability to perform adaptation? I’ll be presenting my theory about this in future chapters. The idea behind this theory is delightfully simple. Presenting it formally, however, is a another story. Stay tuned.
Leave a Comment
September 4, 2007 at 10:28 am (genetic algorithms, population genetics)
Tags: non-technical, philosophical
The conclusion of a manuscript that I recently submitted for review
The biosphere is replete with organisms that are exquisitely well adapted to the environmental niches they inhabit. Natural sexual evolution has been crucial to the generation of what are arguably the most highly adapted of these organisms — cheetahs, owls, humans etc. A deeply intriguing idea is that we can build adaptation algorithms which, at an abstract level, mimic the behavior of natural sexual evolution, and in doing so, “harness” something of the adaptive power of this incredibly effective process. But what is the abstract level at which natural sexual evolution should be mimicked? In other words Read the rest of this entry »
Leave a Comment
