Ooot by DesignEngrLab

A Study of C# implementations of GAs

I am completed a simple genetic algorithm in OOOT (Oct ‘10). But instead of re-inventing the wheel, I wanted to first check out other approaches found online. I found five, but they do not fit the needs that I want. For my reference (and perhaps yours), I am jotting down my notes on these. Some of my conclusions are seat-of-the-pants and may offend the contributing authors of these. If so, cordially respond with a correction.

Genetic Algorithm

Source: unknown

This one was downloaded in June 2005 by some of my research assistants. I can find no URLs within it, but it would be interesting to see the state of the project now if it has continued. I have been unable to find the site, the name, or the author. You can download a copy of the zip here.

It seems very thorough with nice example applications and a modular approach as is adopted in OOOT. The controlling exe would setup the options and then invoke:

GeneticAlgorithm ga = new GeneticAlgorithm();
ga.Selector = new WeightedSelector(ga.Genomes);
ga.Crossover = new BinaryCrossover();
ga.Crossover.CrossoverProbability = 0.1;
ga.Crossover.MutationProbability = 0.07;
ga.GenomeFactory = new BinaryGenomeFactory(typeof(SimpleSolution));
ga.Evaluator = new SimpleEvaluator();
ga.NewGlobalBest += new GeneticAlgorithmEventHandler(onNewGBest);
ga.CreateGenomes(15);
ExitConditions whenToQuit = new ExitConditions();
whenToQuit.Duration = new TimeSpan(0, 0, 15);
Genome maxima = ga.FindOptima(whenToQuit);

+ the use of a TimeSpan for convergence is brilliant. Since then, I have felt that this is really the only true convergence for optimization.
+ the variety and delineation of clear selectors and crossover
- unfortunately, the generation seems to be fixed to a strange for-loop (as part of the main search process, the FindOptima function) where each member of the previous generation contributes to exactly one individual in the subsequent iteration. I am unfamiliar with this method being used in the literature.

EVO

Source: http://evo.codeplex.com/

provides some nice interfaces and the code is modular. The approach to having a list of operators in any order makes it possible to capture many approaches found in the literature. For example, crossover before mutation before tournament; or tournament then crossover, etc. Nice! But no example applications are provided, so needs some work to set up.
Also, after further study, this seems mostly a skeleton/framework that needs more work.

Simple(r) GA in C#

Source: http://www.codeproject.com/KB/recipes/btl_ga.aspx
http://www.codeproject.com/KB/recipes/simplegenalg.aspx

This one pops up first in Google (genetic algorithm C#), but it really lacks the necessary encode/decode building block sophistication to be call a GA. Solutions to only real-valued problems and since crossover only happens between the variables (read dimensions), no new values can be created other than what’s in the initial population unless accomplished by mutation.

AForge’s GA

Source: http://www.codeproject.com/KB/recipes/aforge_genetic.aspx

AForge does a lot more than GA’s now, but I gather this was one of the earliest projects that comprise it. There are four nice example projects that work interactively with a Windows Form (and thus events are part of the algorithm), but the main body of the algorithm is defined not within the library but with functions in the examples (tucked away in the MainForm.cs files). But basically this is the RunEpoch function as part of the library embedded in a loop to control convergence. The RunEpoch[sic] has some nice simplicity and modularity to it:

public void RunEpoch()
{
  Crossover();
  Mutate();
  Selection();
  if (autoShuffling) Shuffle();
}

But these functions are not modules, they are hard-coded, and suffer from the same problem as the previous two – no encoding to a low-level schemata (i.e. binary numbers).

Implementing a Genetic Algorithms in C# and .NET

http://www.c-sharpcorner.com/UploadFile/mgold/Genetic
Algorithm12032005044205AM/GeneticAlgorithm.aspx

Like the Simple one above this also take a major shortcut on crossover so as to remove the implicit parallelism or “building block hypothesis” that provides the real power of GAs

GALib

Source: http://sourceforge.net/projects/csgalib/
http://www.codeproject.com/KB/recipes/galib.aspx

this one shares it’s moniker with a very well known C-implementation (Matthew’s GALib; http://lancet.mit.edu/ga/) but makes no mention that it is derived from it. Like EVO, it lacks example applications to understand how it is to be used. In a sense, this one takes a wholly asynchronous event driven approach, where selection, mutation and crossover happen as separate events. Unfortunately, this one too, is incomplete with no approach to doing crossover correctly (with low level building blocks).

Discussion

In the GA that I have developed, the bit-string is made to a length dependent on the ‘size’ of the variable range as described in the DesignSpaceDescription. Therefore if you have a problem with one variable with 10 possible values and another with 1 million. The bit-string will be 4 + 20 = 24 bits. Four bits to make a value between 1 and 10 (the remaining 6 for values are repeats of the first 6, and 20 bits for the one million range. In this way, the most compact genome is created, and the search process does not waste computation flipping bits that are of no consequence. On my to do list (or if anyone else is so inclined), I would like to make “Generators” for other encodings other than bit-string encodings. What about 4-ary or hexadecimal encoding? Also, I would like to see/create a real-valued encoding ala differential evolution.