We are planning to make a website about how we did this but here's a a quick explanation.
The algorithm we used is generally called a 'genetic algorithm'. They allow you to find
optimum solutions to problems that have a large search space. In this case it allowed us
to find the best amoeba from the huge number of amoeba variations that exist.
evilgoatfiend you pointed out that the best amoebas are the simplest. That is true but you
had to figure that out in your head. The genetic algorithm we used found this out for us and
the final amoeba it produced reflected this. when we wrote the algorithm we didnt know anything
at all about what makes a fast amoeba. The point of the algorithm was for it to find this for us.
We chose to start off with amoebas on flat terrain because it was simple to see to code
and to see how it works. Our next step would be to use terrain and try to evolve more complex
models.
For those interested in knowing more about the technique we used i found this site quite handy
as a good introduction http://cs.felk.cvut.cz/~xobitko/ga/ .
If you've read that or already know a little bit about genetic algorithms i'll go into more detail
about what we specifically did.
Encoding of a chromosome (in this case what defines an amoeba)
This involved finding a way to represent an amoeba as a set of parameters. Just like the blueprint
for making humans is in our DNA we needed to find a suitable representation for our amoeba. We decided
that each ameoba can be represented simply by the number of masses it has and the distance between the centre
and one of the masses on the outer ring. These two numbers define what the amoeba looks like. The other 6 numbers
we need to include are the three settings for the wave (amplitude , phase , speed) and the three settings for
the environment (gravity , friction , springyness). they have to be included because they affect how well the ameobas moves.
We coded a class that takes in these parameters and creates an amoeba, giving back the XML string representation
that can be passed to the race app. this is similar to existing ameoba creators already out where you enter the
numbers and it gives you an amoeba in xml form. our representation allows us to easily breed (cross-over) an amoeba from two models
and also perform mutation. Cross-over involves taking two amoebas and randomly picking parameters from each. for example You may
take the number of masses from one amoeba and the radius the other amoeba. Once we have crossed-over all the parameters
we can create a new amoeba with our amoeba factory. This is step 4 of the algorithm below. step 5, the mutation simply
involves taking the parameters of an amoeba and randomly changing them by some amount. The mutation encourages
genetic variation and ensures that a wider range of amoebas are created.
Main algorithm steps:
with encoding of the chromosome out they way we can proceed with the main algorithm process which goes as follows.
1. create a population of 100 amoebas by passing random numbers into our amoeba factory class.
2. test the speed of all amoebas in the population saving the results.
3. Pick two amoebas with some selection method that favours better performing amoebas.
4. Cross-over the parameters of the amoebas.
5. Mutate the parameters.
6. Test the fitness of this amoeba and compare it to the population. If it is faster than any in the popultion
than add it in and throw out the slowest. Go to step 3.
This carries on until some condition is met, such as an amoeba of sufficient fitness has been produced or the fitness
of the best amoeba hasnt changed for the last 1000 iterations or so.
As you can see even with this simple example of creating amoebas there are a significant number of steps involved. As i
mentioned before we will be making a website to give proper explanations, and make our source code available to those
interested.
The fastest amoeba that our algorithm produced actually does this race in a mere 36 frames (see the race). But it "cheats". The algorithm
eventually learns that setting gravity and friction to close to zero the amoeba can "fly" across the screen without
touching the ground. i had to restrain the the parameters gravity and friction to minimum values so the amoebas always
use the terrain.
just to answer wwans questions:
The initial amoebas didnt even finish. They all timed out. It was through mutation that an amoeba that finished was produced.
first of which finished in about 2000 seconds i think.
The total number of amoebas tested was around the 50,000 mark (500 generations with a population of 100) at which point a memory leak in the race app caused it to crash. i believe they fixed one of these memory leaks but another still exists.
race: http://sodarace.net/upload/Chirag/superAmoeba.jnlp
|
