empirical

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.

The maximum and average fitness in each generation of this run are shown below avg_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.

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

Continue reading “Bit Dynamics Visualization” →

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.

evorithmics

Understanding and Harnessing the Computational Power of Evolution

Bit Dynamics Visualization

What Are GAs Good For?