SpeedyGA v1.3

Keki1 Comment

Download the latest version of SpeedyGA (version 1.3) from Matlab Central’s File Exchange or from Google Code.

Version 1.3 of speedyGA is faithful to the specification for a simple GA given on page 10 of Melanie Mitchell’s book “Introduction to Genetic Algorithms”; that is if none of the bells and whistles (mask repositories, stochastic universal sampling, and sigma scaling) are used. SpeedyGA has also been changed from a function to a script. This makes it easier to inspect variables and plot data after a run has completed.

[Update Jan 27, 2013: SpeedyGA.py is a port of SpeedyGA to Python]

SpeedyGA v1.3

Bit Dynamics Visualization

KekiLeave a comment

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 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.

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

Continue reading “Bit Dynamics Visualization” →

Bit Dynamics Visualization

VectorGA is now SpeedyGA

KekiLeave a comment

With VectorGA being downloaded from Matlab Central over 611 times in the past 30 days, I thought I’d release some of the tweaks I’ve been using to speed it up. I’m calling the result SpeedyGA .

Download SpeedyGA from Matlab Central’s File Exchange or from Google Code.

Release notes:

SpeedyGA is a vectorized implementation of the Simple Genetic Algorithm in the Matlab programming language.

Matlab is optimized for performing operations on arrays. Loops, especially nested loops, tend to run slowly in Matlab. It is possible to significantly improve the performance of Matlab programs by converting loops into array operations. This process is called vectorization. Matlab provides a rich set of functions and many expressive indexing schemes that make it possible to vectorize code. Such code not only runs faster, it is also shorter, and simpler to understand and change (provided that you know a little about Matlab of course).

Genetic Algorithms that are implemented in C/C++ or Java typically have multiple nested loops. Therefore direct ports of such implementations to Matlab will run very slowly. Many of the nested loops found in a typical GA implementation have been eliminated from SpeedyGA. The resulting code is short, fast and simple. It is indeed a delightful coincidence when the constructs of a programming language match a programming task so well that a program can be written this succinctly.

SpeedyGA is proof that Matlab is a useful language for the rapid prototyping of Genetic Algorithms. This, in addition to Matlab’s extensive data visualization capabilities, make Matlab an extremely useful platform for the experimental analysis of GAs.

SpeedyGA has been created and tested under Matlab 7 (R14). Out of the box it evolves a population against the one-max fitness function. The royal-roads fitness function has also been included but is not currently being called. If you find vectorGA useful or find any bugs please let me know.

Enjoy!

SpeedyGA is a revision of the old VectorGA. SpeedyGA has (not surprisingly) been further optimized for speed.

Changes since VectorGA

  1. Added mutation  and crossover mask pregeneration
  2. Added the option to visualize the changing bit frequencies of a population (very handy for understanding GA dynamics)
VectorGA is now SpeedyGA

The Fundamental Problem with the Building Block Hypothesis (new manuscript)

Keki, , Leave a comment

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

The Fundamental Problem with the Building Block Hypothesis (new manuscript)

What Are GAs Good For?

Keki, , Leave a comment

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.


What Are GAs Good For?

The Need for a Sound Theory of Adaptation for the Simple Genetic Algorithm

Keki, Leave a comment

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 Continue reading “The Need for a Sound Theory of Adaptation for the Simple Genetic Algorithm” →

The Need for a Sound Theory of Adaptation for the Simple Genetic Algorithm

The Dubious History of the Building Block Hypothesis

KekiLeave a comment

From the introduction of a manuscript that I recently submitted for review

Perceptions of the abilities and limitations of the SGA (and hence the kinds of problems that it can and cannot solve) have been heavily influenced by a theory of adaptation called the building block hypothesis (Goldberg, 1989; Mitchell, 1996; Holland, 1975, 2000). This theory of adaptation has its genesis in the following idea: maybe small groups of closely located co-adaptive alleles propagate within an evolving population of genomes in much the same way that single adaptive alleles do in Fisher’s theories of sexual evolution (Fisher, 1958). Holland called such groups of alleles building blocks. This idea can be taken one step further: maybe small groups of co-adaptive building blocks propagate within an evolving population of genomes in much the same way that single building blocks do. Such groups can be thought of as higher-level building blocks. Pursuing this idea to the fullest extent, maybe Continue reading “The Dubious History of the Building Block Hypothesis” →

The Dubious History of the Building Block Hypothesis