Tracking fitness in a genetic algorithm

Question

I'm still hacking on my old ruby for the undead post (I know, I know, stop trying to bring the post back from the dead Chuck). But the code has gotten a little out of hand and now I'm working on a genetic algorithm to create the ultimate battle of living and dead with the fitness being how long the battle lasts.

So, I've got the basics of it down; how to adjust attributes of the game and how to acquire the fitness of a solution, what I can't figure out is how to store the fitness so that I know when I've tried a combination before.

I've not been able to find much genetic code to look at let alone code that I can read well enough to tell what's going on. Does anyone have an idea how this is normally done or just simply an algorithm that could help point me in the right direction?

Answer 1

what I can't figure out is how to store the fitness so that I know when I've tried a combination before.

Normally in a GA solution you are not concerned about generating the same "solution" what you are concerned about is when the rate of improvement in your 'score' stabilises.

Now if your wanting to log/track the "solution" history you many want to know when it reappears latter, but I assume there is some random nature to your "game" therefore you would want object to repeat runs.

Answer 2

In a GA you don't want to reevaluate a solution if the fitness test takes a long time. Use a hash table to store your fitness scores and make the hash key the chromosome. Use the "Orcish Maneuver"; check the cache first, if it is there retrieve it and continue, else compute it and put it in the hash for next time.

Answer 3

If you would like a full example of a GA you could get the free, open source, Matlab GA Toolbox from the evolutionary computing team at the University of Sheffield in the UK, available here:

http://www.sheffield.ac.uk/acse/research/ecrg/gat.html

Even if you don't want to look at the matlab code, the manual which comes with the toolbox has a really good and accessible description of exactly how GAs work which may help you with your Ruby code.