Optimization By Decimation: Explaining Adaptation in Genetic Algorithms with Uniform Crossover

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:

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

Presentation at the University of Washington: Optimization by Hyperclimbing

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:

Yesterday, I presented my research on genetic algorithms at the University of Washington.

Talk abstract

My slides

Leave a Comment

Screencast Presentation: An Introduction to the Generative Fixation Hypothesis

February 13, 2010 at 7:01 pm (Bit Frequency Visualization, generative fixation, genetic algorithms, hyperclimbing, symmetry-analysis)
Tags:

http://cs.brandeis.edu/~kekib/genfix/GAsAndHyperclimbing.html

Enjoy!

1 Comment

Dissertation Deposition

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

Red Dots, Blue Dots

June 29, 2009 at 7:02 pm (Bit Frequency Visualization, epistasis, generative fixation, symmetry-analysis)

In this blog entry I’d like to showcase just one of a number of remarkable findings that comprise the basis for the generative fixation hypothesis—a new explanation for the adaptive capacity of recombinative genetic algorithms.

Consider the following stochastic function which takes a bitstring of length \ell as input and returns a real value as output.

fitness(bitstring)
  accum = 0
  for i = 1 to 4
     accum = accum + bitstring[pivotalLoci[i]]
  end
  if accum is odd
     return a random value from normal distribution N(+0.25,1)
  else
     return a random value from normal distribution N(-0.25,1)
  end

The variable pivotalLoci is an array of four distinct integers between 1and \ell which specifies the location of  four loci—let’s call them A, B, C, D—of an input bitstring that matter in the determination the bitstring’s fitness. These four loci are said to be pivotal. Read the rest of this entry »

2 Comments

Bit Dynamics Visualization

December 30, 2008 at 1:07 pm (Bit Frequency Visualization, genetic algorithms, visualization)
Tags:

I’ve found the bit dynamics visualizer included in speedyGA very useful for understanding the dynamics of SGAs with bitstring genomes. In each generation the visualizer plots/updates the frequency of the bit 1 at each locus (the frequency of the bit 0 is straightforwardly deducible) .

Here’s a visualization of the bit dynamics of an SGA with 1pt crossover when applied to the the Royal Roads fitness function. Going by the building block hypothesis one expects to see the dots marching orderly to the top of the plot in groups of eight or more.

That’s not what happens. Instead, one gets to see hitchhiking in action—look for a swift downward movement of certain dots in tandem with the swift upward movement of other dots at close by loci.

speedygarun_crossovertype12

speedygarun_crossovertype12

This movie requires Adobe Flash for playback.

The maximum and average fitness in each generation of this run are shown belowavg_max_fitness_crossover1

The matlab code used to generate these and other figures in this blog post can be found here.

Let’s visualize the bit dynamics of a population when an SGA with uniform-crossover is applied to the Royal Roads function.

speedygarun_crossovertype21

speedygarun_crossovertype21

This movie requires Adobe Flash for playback.

The maximum and average fitness in each generation of this run are shown below

Read the rest of this entry »

Leave a Comment

Follow

Get every new post delivered to your Inbox.