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
January 29, 2010 at 2:01 am (decimation, generative fixation, genetic algorithms, hyperclimbing, survey propagation)
In recent years, probabilistic inference algorithms such as survey propagation and belief propagation have been shown to be remarkably effective at tackling large, random instances of SAT, and other combinatorial optimization problems that lie beyond the reach of previous approaches. These inference algorithms belong to a class of techniques called decimation strategies. Decimation strategies monotonically reduce the size of a problem instance by iteratively fixing partial solutions (partial variable assignments in the case of SAT).
The generative fixation hypothesis essentially states that genetic algorithms work by efficiently implementing a decimation strategy called hyperclimbing.
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
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
