Playing-around with Genetic Algorithms

 
Way-back machine: this post was made on 9 Nov 2007 on Spaces.Live.com
Comments were not migrated.
 
I’ve tried some code samples around genetic algorithms previously and they’ve been surprisingly simple in the code and concept which drives them.
 
The first that I tried was Sacha Barber’s Simple Genetic Algorithm project on Code Project (available here).  I have subsequently found that Sadavoya has created a new article and upgraded the concepts to utilise .NET 2 capabilities, specifically generics (does that make it a “Generic Genetic Algorithm” – someone always has to go one better).  This article is also on Code Project here.
 
Bear in mind that Code Project has many projects about Genetic Algorithms (use the search) and some facinating (but sligtly off-topic for this blog) Ant Colony Optimisation projects too (such as Lawrence Botley’s excellent article).
 
But these are just simple demos.  At the end of it you have no real visual demonstration of the individual states in the process which is the genetic algorithm.  You start with a problem and you end with a solution.  You can break in the code and stop to look at interesting numbers and intermediate states but this doesn’t tell you much about the way the solution has changed and genetic concepts such as inherited traits and recessive traits are hidden (and in many of these examples isn’t immediately obvious as being part of the solution).
 
The demo that I found recently blew me out of the water. Visit the Mathematics Department at Hobart and William Smith Colleges where they have developed a Java application which visually demonstrates the concepts of genetic algorithms in the best possible way.  Unfortunately you must have the JRE (Java Runtime Environment) installed to run the demo – this does not run inside a Java compatible browser, it runs as an application outside of your browser.  The problem which is posed to the program is to make creatures (red T-pieces) which eat as many plants (green O-pieces) in their life time – this is their measure of success.  You control the world to choose how much variation is introduced by breeding and the crossover and mutation probability, where plants grow and so on and so on.
 
The interesting thing is that you find that early on there are some individuals who are lucky to be born near lots of food and their traits are passed-on to their offspring (even if it is the useless trait of moving around in a circle until you die).  As offspring are born further from food, mutations in this silly behaviour are required otherwise they die with a low score.  You see that over time they develop some ingenious traits that result in ever higher and higher scores. Run at maximum speed for a while and then stop a few thousand years in the future where you return to a world populated by much more efficient eating machines.  You still see some regressing to silly behaviours but these bad mutations are often short lived (like spinning around on one spot for a lifetime).
 
I have played with this world in many combinations of world designs and after thousands of years you see a completely new solution to the plant eating problem which is “perfect” for that world and would be useless in other worlds.  I was often amazed when I slowed the world every now and then and observe the individual traits of these eaters.  I then thought about which of those observed traits would do well in the future (knowing what I knew of the world design) and being completely floored by how the trait I thought would work didn’t turn-out to be the best aproach – very few still demonstrated this trait later on.
 
In this program, what I’m refering to as a trait is the list of internal instructions that an eater would follow depending on the scenario they were faced with.  It may be a list of rules as follows (this is a short list because it’s late – and I’m sure you’d rather try it for yourself anyway):
  1. When I leave a block where I ate something, immediately turn left 90 degrees.
  2. Travel in a straight line until the block I am in is different from the previous block.
  3. When I can’t go forward (edge of the world or another eater) turn right 90 degrees.

Now another eater may have the following similar trait, but notice how the places that they go would be vastly different:

  1. When I leave a block where I ate something, immediately turn left 90 degrees.
  2. Travel in a straight line until the block I am in is different from the previous block.
  3. When I can’t go forward (edge of the world or another eater) then move backwards (reverse my direction, not turn 180 degrees).
So … GO!!  Try it out.  I’m sure you’ll find it facinating too!
Advertisements

~ by James on 9 November 2007.

 
%d bloggers like this: