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
