Final Year Project & Concurrency

Advertisemen

My Final Year Project involves using a Genetic Algorithm to evolve life forms so they optimise the amount of food they collect from an environment. I usually used 50 to 100 life forms per generation of the Genetic Algorithm, the process of evolving them goes something like:

1) Create initial generation where each life form are assigned random behaviour
2) Simulate each life of the generation
3) Save the fittest life form
4) Breed the generation (with more bias towards the fitter life forms breeding)
5) Add the saved fittest into the population (we want to keep an exact copy and not to have the gene structure changed by reproduction or mutation)
6) Repeat from Step 2

Over time I've had to test the simulation lots which involves a lot of waiting since simulating each life form of the generation takes a while. Obviously be able to simulate life forms in parallel would speed it up. But it trying to make it parallel I've had one of those horrible programming experiences where you step through the code for hours and hours and hours, change little things that you think could be causing it not to work but they don't. However, now I'm at the point where I think (I hope) I've finally fixed it.

The problem was that when I was running the simulation on a single thread it would work fine, but on two threads it would work most of the time but sometimes the maximum fitness of the generation would drop. Since the fitness function (the life form collecting food from the map) is deterministic, for a life form with the same attributes (chromosome/genes), the life form must always produce the same fitness value.

The first attempt seemed like the simplest. JGAP (Java Genetic Algorithms and Programming - the open source library I'm using for the Genetic Algorithms) provides two types of fitness functions: FitnessFunction and BulkFitnessFunction, the FitnessFunction only allows you to simulate a single chromosome at once - it is passed a single chromosome into its evaluateFitness function and the latter is passed the whole population. Being passed in the whole population it seemed relatively easy, since you could divide the population by N and use N threads to simulate. But that didn't work single threaded due to a strange bug I found with JGAP's implemention of the BulkFitnessFunction earlier. So then I decided to move on to FitnessFunction.

However FitnessFunction wasn't as flexible as BulkFitnessFunction and as a result of thinking how to access the entire population of life forms (given that I only had access to a single chromosome of the population), I had to delve into the source code once again. Turns out that the entire population is passed to the FitnessFunction for evaluation in IBreeder.updateChromosomes (since IBreeder is an interface, the class I was using which implements that was GABreeder). So my next idea was to create a subclass of GABreeder - called ConcurrentBreeder - to override the updateChromosomes method and simulate the population in parallel (the same method I would have used for the BulkFitnessFunction).

I initially got it worked in a separate thread (only one though), but it still ran much faster than it did when the simulation was on the same thread. So I began adapting the code for N threads. Below is the pseudocode for my initial single-threaded and multi-threaded approaches. Note that the ConcurrentFitnessFunction implemented Runnable and just simulated the population input to its constructor in the world input to its constructor.

updateChromosomes(Population p)
    Thread t = new Thread(new ConcurrentFitnessFunction(p, simulationWorld))
    t.start();
    t.join();

updateChromosomes(Population p, int numThreads)
    Thread[] t = new Thread[numThreads];
    int size = p.size()/numThreads;
    for (numThreads)
        t[i] = new Thread(new ConcurrentFitnessFunction(p.subset(i * size, (i + 1) * size), SerializationUtils.clone(simulationWorld));
    startThreads(t);
    joinThreads(t);

Note that I've used Apache SerializationUtils to clone the Simulation World, you can read about the dilemma I had with that here - note that I needed a deep copy, not a shallow copy because the latter is very easy.

What I found when multiple threads were being used was that the maximum fitness wouldn't either stay the same or increase, something would drop. Here are (some of) the thought processes I went through.

1) The world wasn't being cloned properly. Potentially if there wasn't a deep copy of the food on the map then the food being eaten in one world would affect the food in another world. This wasn't the case. +2 hours debugging

2) Not all the life forms were being simulated. This was very obviously to see (code-wise) that all the life forms were being simulated but I thought it could be some weird bug somewhere. +1 hour debugging

3) Threads were sharing variables. Looked into using ThreadLocal, didn't save the problem, made everything a mess, made the cloning messier (ThreadLocal doesn't implement Serializable, I tried custom Serialization using a custom ThreadLocal subclass and readObject and writeObject but that didn't work). +2 hours debugging

But this point I was stuck - just playing around with ideas I had tried (Einstein's definition of insanity). Eventually I used JGAP, chromosome.clone() method when I was placing the chromosomes into a new list. I have no clue why this has made things worked, but as far as I know it has. Still want to test more, as a few times I've gotten really exciting thinking I've fixed this - then it's like a kick to the balls when I'm watching the maximum fitness graph and suddenly the fitness just drops.

Advertisemen