Thursday, October 05, 2006

Genetic Algorithms with Ruby

I was very excited when Shark Hunter presented his first session on AI. He started with Genetic Algorithms. The idea that a solution "magically" evolves is fascinating. All you need to do is present your candidate solutions as a sequence "chromosome" of some objects "genes", then assign a fitness to each chromosome, then mimic nature by mating and mutating the population. Eventually "life finds a way", and solution is found.

One of the nice sites with demos is here.

So I thought this will be a very cool exercise to practice my newly acquired Ruby skills. It took me a few hours to come up with a simple "framework" to represent a general GA.

I will keep updating my GA framework and add more tools and functionality to it. Ultimately I want to be able to modify my sub Chromosome class only, and just add a fitness method, then fire my simulation and let the search begin.

Basically the framework consists of a Chromosome class, and a Population Class.

The Chromosome Class

This class represents a Base Chromosome. It is basically a sequence of genes that have a fitness, and possibly represent a certain value. The Base class knows how to marry, or crossover. The Base class crossover is a single point, and no mutation is done. A subclass will be created that can have two crossover points. The framework is still in very early stages, and will be re-factored. But basically, that is all there is to it.

The Population Class

This class represents a Population of Chromosomes. It holds the entire population and is responsible for Selection and Generating offsprings. The Base class does a simple Roulette Wheel Selection based on a fitness value. To make the initial code simple, the fitness value must be higher for fitter solutions. So, a chromosome of fitness = 10 will be 10 times likely to be selected that a chromosome with fitness = 1.


I did not create any classes for genes. I wanted to make things simple, so the sequence itself will represent any kind of genes. It is tested as a Strings in this initial version. The main thing is finding a way to represent the fitness of the chromosome. I will see if representing binary numbers, integers as sequences, or real numbers will require any changes in the sequence attribute or require the creation of a Gene class. But since Ruby is so dynamic, I doubt this will be needed.

The Code

Anxious to see the code and try it out? Drop my a line, and I will send it to you or publish the current version somewhere. It is still in very early stages, but works for simple problems.


- said...

Have you ever posted this somewhere?

Ayman said...

I have not, and it's been a while. Sorry, not much memories of this anymore.

Just Google it!