> 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
I have added one of my AI amoebas and I also added a terrain and beat 'superAmoeba'
race: http://sodarace.net/upload/mathchamp/LoserAmoeba.jnlp
|
