Download and view my resume (PDF)

Thursday, October 8, 2009

Simple Genetic Algorithm In C++

I will soon start a new job for which one of the primary duties is to write and maintain code in C++. In order to brush up on my C++ mojo, I translated my recent genetic algorithm into C++, and also updated the nomenclature. Traditionally, genetic algorithms use chromosomes, not organisms as I used; and chromosomes have genes, not values as I used. So this code uses chromosomes with genes. This code applies the selection criteria from my second genetic algorithm in python, which produces a string which increasingly resembles the alphabet.

This exercise reminded me how subtle pointer arithmetic can be. After not using pointers for seven years, some of the usual patterns I had developed no longer work. For instance, in python I wrote this code:
self.organisms = self.selectOrganisms(
self.mateOrganisms(
self.mutateOrganisms( self.organisms )
)
)
You see I take self.organisms, pass it through mutation, mating, and selection routines, then assign the result back to self.organisms. That's no problem with a language that has garbage collection and no pointers, but in C++ that is a memory leak, because I never explicitly deleted the old self.organisms before assigning the new value. In C++, this became:
vector<chromosome> *nextGenerationChromosomes Environment::DoNaturalSelection(
Environment::MateChromosomes(
Environment::MutateChromosomes(
this->chromosomes
)
)
);

// release the previous generation of chromosomes
for( int i = 0; i <>chromosomes->size(); i++ ) {
delete this->chromosomes->at( i );
}
delete this->chromosomes;

this->chromosomes = nextGenerationChromosomes;
You see that I had to get the new value, and then delete the old value, and then set the new value. I also imagine there are a bunch of patterns I need to remember and learn to make memory management more straightforward. I will work on this code for the rest of the week. This algorithm implemented in C++ runs about a hundred or a thousand times faster than the same one in Python.

Download Genetic-A C++ Code

In a terminal open to the same directory as the code file, issue
g++ genetic-a.cpp -o GeneticAlgorithm
./GeneticAlgorithm

No comments:

Post a Comment