Home > AI, FuchsGUI, Games Programming, My Thoughts, Programming, XNA > Genetic Algorithms Lab

Genetic Algorithms Lab

Genetic Lab

 

So a few years ago I did a project for the Genetic Algorithms assignment at college. My idea was to have tiny multi-cell organisms that have a simple goal: travel as far as possible! maybe to find new resources or escape from predators, you pick one 🙂
So the fitness of a creature is measured by how far it can go during its life span.

The creatures will start with random moving cells and evolve to more organized creatures with organized movements.

Please watch the video before reading. If the video failed to make you interested then I doubt that the text would succeed. You can also download the executable and the source code available at the end of this post.

 

In the video you’ll notice how creatures start as dumb creatures that are barely moving then evolve through generations to more organized moving structures! I really find the results interesting.

Each creature has a number of cells connected with springs and each cell has a set of properties like the mass and the moving direction or the amount of energy stored in it.

So we have two types of cells:
Pull cells which generate pulling force in a specific direction.
Energy cells which burn gradually while providing the creature with energy required to survive.

While it’s good for a creature to have many energy cells the creature will also need pull cells otherwise it won’t move too far and wont be considered fit! this combination of cell types and properties enabled some relatively complex fitness goal to achieve.

I tested with three kinds of creatures, each with unique cells layout

 

Simple creatures:

Simple Creatures

Simple Creatures

 

Each creature has a maximum number of cells and each cell is at most connected to two cells, the creature only consists of pull cells and doesn’t require energy cells to survive. The simple creature only has to worry about its life span.
The genotype structure of each cell is as follows:

Cell
1 Bit
Mass
5 Bits
Angle
9 Bits
Velocity
4 Bits
Interval
10 Bits

cell: does the creature has this cell (boolean)? the genotype length is constant but some cells will not physically exist.
mass: defines the mass of the cell (integer), this affects the pull speed and the dragging by other cells.
angle: defines the angle of the force produced by this cell relative to the connection angle with the next/previous cell (mapped to [0,2Π])
velocity: the velocity generated by this cell (integer).
interval: the amount of milliseconds between each pull generated by this cell (integer).

So in total the genotype length of a simple creature would be 29 * the predefined maximum number of cells a creature can have.

 

Energy Creature:

Energy Creatures, the creature consumes the energy cells in order to survive

Energy Creatures, the creature consumes the energy cells in order to survive

 

For the energy dependent creature a bit is added to specify the cell type (energy vs pull). For the energy cells, the velocity bits are used to define the energy stored in this cell.

Creatures of this type will consume the energy cells one by one until they run out of cells and eventually die.

 

Complex Creatures:

Complex creatures

Complex creatures are like energy creatures except that each cell it connected to the other cells

 

Same as energy creatures but here every cell is connected to the other cells and the genetic algorithm must do better work if the creature is to survive!
4 bits are added to define the distance of the cell to the initial creature center.

 

Execution of the algorithm:

  1. Create n creatures of the selected type.
  2. Let the creatures move freely until they die (out of energy) or the life span of the current generation is over.
  3. Calculate each creature’s fitness by the distance traveled from the center.
  4. Use a roulette wheel to get an intermediate generation.
  5. Random pairing between creatures of the intermediate generation.
  6. Do some mutations :).

 

 Source Code and Demo

The demo is written in C# with Microsoft XNA 4, I recently started working on an HTML5 + JS port (for this particular post) but when I finally got the minimal project working the organisms didn’t evolve quite well and I was already fed up with debugging Javascript code so I dropped the whole idea.

GeneticLab Source Code.zip (312 KB) (C#, Visual Studio 2010 ,XNA 4)

GeneticLab Exe.zip (43 KB)

For the demo to work you’ll need Microsoft XNA Redistributable 4 to be installed on your device.

 

I hope you give it a try and like it 🙂
Just make sure you don’t forget about them as they might evolve and leak out of your computer’s screen :D.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

What do you think?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: