Description
This is some code to simulate a basic "holland-style"
(google: "
holland genetic algorithm")
genetic algorithm, to
illustrate some concepts talked about in a CS class i took in college.
I updated it a little bit further as i was reading "The Blind Watchmaker" by
Richard Dawkins to play with some of his word-based examples.
A "cell" contains "dna". dna can be anything, a list of bits, an image,
a string. It doesn't matter as long as you code up a corresponding
fitness function that understands the dna and can judge it's fitness.
For example: say that we define dna as "a 4-character string", and the fitness
function as: "the closer you get to 'asdf' the fitter you are".
Every time we see a cell with an "a" in the first place of it's dna, we award
it 25 points (out of 100, because there are 4-characters), with a "d" in
second-place, another 25, etc... if it has all 4 in the right place, it gets
100 points, a perfect score, because it has hit the target.
The way to use this code is to generate a bunch of initial
"seed cells" with random dna to get the population started.
Then, "Nature" runs all the cells through your custom fitness function
to figure out how close each was to the "target". The ones with the
highest scores (by default, 10% of the group, but it can be adjusted)
are grouped together and 2-at-a-time are randomly picked and "mated" until
you have as many children as parents. Then, the parent population is
replaced with the child population and the whole process is
ready to run again.
Each successive generation should be (on average) closer to the
target you specified and eventually converge on the target.
Program overview
- Subclass 'Cell' to define your own cell and what kind of 'dna' it holds
- Define your own Fitness function to judge the fitness of your cell's dna (on a scale of 0..100)
- Create an initial population of random cells
- Hand the population and the fitness function over to "Nature" and let it go
Examples & Sample Code
Example 1: Using numeric bit-strings as dna.
Example 2: Using strings as dna.
ChangeLog
v0.3 - May 18, 2006 -
Worked on the code further to make it more modular and abstract and now
it supports arbitrary DNA instead of solely bitstrings.
v0.2 - Dec 21, 2005 -
Separated the test code from the genetic module and added
some more comments to everything.
