Evolution in a 3D Fitness Landscape

Introduction


It's the classic Evolutionary Computation example: attempting to find the values of two variables, x and y, which maximise some function f(x, y). The great thing about it is that it can be visualised in 3D, which always looks great. What looks even better is the population as it moves through the fitness landscape. We can adjust our evolutionary algorithm to change the population's behaviour and watch the results.

Microsoft's Windows Presentation Foundation (WPF) gives us an amazingly simple API for developing in 3D, with a pethora of features and full hardware acceleration. So not only will this be a chance to show a classic EA problem, it'll be a great opportunity to play with WPF 3D.

The Fitness Landscape


One of the strengths of evolutionary techniqiues is their ability to negotiate fitness landscapes which contain local maxima - areas which appear to be the best solution, but actually aren't. To demonstrate this, we need to create a landscape with one point which is higher than all others (Mt Everest) and a number of smaller peaks (the Himalayas) which are nevertheless quite high.
The initial population, randomly distributed throughout the problem space
Figure 1: The initial population, randomly distributed throughout the problem space


The landscape is created by a function f(x, y) which takes x and y values and returns a height. The best functions for making smooth lumps are Sine and Cosine. A number of sine/cosine waves of different frequencies and amplitudes can be added together to make a very interesting landscape. The figures in this article show the result of the following code when presented with x and y values from 0 to 100.

public static double Function(int sizeX_, int sizeY_, double freq_, double amplitude_, double x_, double y_)
{
    double d = 0;

    // Medium lumps


    double mediumFreq = freq_ * 0.2;
    d += (amplitude_ * 1) * Math.Cos((x_ + (sizeX_ * 2)) * mediumFreq);
    d += (amplitude_ * 1) * Math.Cos((y_ + (sizeY_ * 2)) * mediumFreq);

    // Small high frequency lumps


    d += amplitude_ * Math.Sin(x_ * freq_);
    d += amplitude_ * Math.Sin(y_ * freq_);

    d /= 2;

    // Big lump in the centre


    d += (amplitude_ * -1) * Math.Cos((x_ + (sizeX_ / 8)) * 0.05);
    d += (amplitude_ * -1) * Math.Cos((y_ + (sizeY_ / 8)) * 0.05);

    return d;
}

Hill Climbing


As humans, we can look at the 3D landscape in the figures and easily find the highest point. There are a number of reasons for this, the most obvious one being that we've drawn a visual representation of the problem and the human brain is amazingly good at understanding 3D shapes.

From a computer's point of view, the problem is a bit like this: You've been parachuted into the Himalayas, blindfolded, with a mission to find the highest point (the top of Everest). You can't take the blindfold off, so you can't look around you. The only tool you have to aid you in your mission is a talking GPS receiver, which reads out your current hight above sea level.

The obvious strategy which comes to mind is to take a step in a random direction and work out the change in height. If you've moved up, that's great, you can take another step from here. Otherwise, you need to step back to your starting point and try another random direction. You can repeat this procedure until eventually you'll get to the top of a mountain.

Of course, once you're at the top of a mountain, every step you take will lower your altitude. You're stuck! There's no way of knowing whether you've reached the summit of Everest, so you're mission has probably been a failure!

The key here is that the computer doesn't have a map, or a way of visualising the landscape like we do. So the problem is very hard for a computer to solve.

The Evolutionary Algorithm

At risk of stretching the Himalaya analogy to the point of insanity, the population in an evolutionary algorithm are more like trees: Imagine a breed of tree which grows better at higher altitudes and doesn't care about snow, ice, cliffs or abominable snowmen. It's seeds are spread by the wind - they can be blown anywhere in the world, but chances are they'll land somewhere near their parent. Obviously, the trees don't move.

So, to start with, the trees are randomly spread across the mountain range. When new trees grow, there's a chance they'll grow higher up a mountain than their parents. Trees which are higher up are more likely to live longer (because our trees love altitude) and so they get more chance to have offspring. Because offspring are likely to grow near their parents, there's a good chance that the third generation will grow higher than the second and the fourth might grow higher still. After a few generations, there will be trees at the top of the nearest mountain.

Once there are trees at the top of a mountain, you might expect that they'd be stuck, just like the blind climber in the previous analogy. That's where the random effects of the wind start to take effect. Seeds are likely to fall near their parent, but it's not certain. A gust of wind might blow a seed to another mountain, where it might survive long enough to reproduce and its offspring will start to climb.

Evolutionary algorithms work in just this way. All we have to do to guide them to the global optimum is find a fitness measure which rewards better solutions.
After a few generations the population starts to group together
Figure 2: After a few generations the population starts to group together

You can read more about the specifics of evolutionary computation here and about the architecture I use to implement them here.

A Hill Climbing Evolutionary Algorithm


EAs revolve around two things - a data structure which represents a potential solution to the problem (the "Individual") and a measure of fitness for individuals.

In this case, it couldn't be simpler, the individual is just a point on the map at a given X,Y coordinate (or in the case of the 3D display an X,Z coordinate, since Y is height!).

The fitness measure is simply the function we use to generate the map (f(x, y)). We pass in the individual's coordinates and the function will return its height. Individuals with greater height are fitter than those with lower height.

Crossover is very simple too, we select two parents for children and take one coordinate from each.
Child.X = Mother.X
Child.Y = Father.Y

Mutation is simply a case of adding a random number to the X and Y coordinates. We use an exponentially distributed random, centred on zero to make large mutations less probable than small ones.

And that's it. It really couldn't be any simpler! The figures in this article show a population as it moves through the fitness landscape. Starting at random locations, the population converges on a local maximum before finally reaching the global maximum.

Maintaining Diversity


One of the most important considerations, when using an evolutionary algorithm to solve any problem, is population diversity. The algorithm favours fitter individuals and punishes those which are less fit, but if it is too elitist we can easily end up in a situation where all the solutions are identical and less than optimal.

Figure 3 is a good example of this, The population has converged on a local maximum and new individuals which are born further away from the core population tend to be less fit - they're lower down the hill - so the algorithm favours solutions which are pretty close together. This will continue to be the case until a new individual appears on a bigger hill.
Reaching a local maximum
Figure 3: Reaching a local maximum

There are several strategies for maximising population diversity, but the basic rule is that lower evolutionary pressure leads to higher diversity. With no evolutionary pressure (using a random fitness function for example) the population would be randomly distributed through the problem space. On the other hand, if we killed all the worst individuals and left only the fittest, we'd get a very tight grouping.

One way to lower elitism is to change the "Killer" strategy. I started off using a "WorstNKiler" which kills the worst few population members...
public override void Kill(Population population_)
{
    int i = 0;
    while(i++ < KillCount && population_.Count > 0)
    {
        population_.RemoveAt(population_.Count - 1);
    }
}

But found that a Killer which holds a series of fitness tournaments gave better diversity...
private int SelectByTournament(Population population_)
{
    // Select a random member of the population   


    int i1 = _random.Next(population_.Count);

    // Select another (different) population member


    int i2;

    do
    {
        i2 = _random.Next(population_.Count);
    } while (i1 == i2);

    // Fight!  Fittest wins, weakest is returned.


    if (population_[i1].Fitness < population_[i2].Fitness)
    {
        return i1;
    }
    else
    {
        return i2;
    }
}

public override void Kill(Population population_)
{
    // Kill n population members, selected by tournament


    int i = 0;
    while (i++ < KillCount && population_.Count > 0)
    {
        int index = SelectByTournament(population_);
        population_.RemoveAt(index);
    }
}

Conclusion


So, in this article I've spoken briefly about the theory of evolutionary computation and how it relates to the traversal of a 3D problem space. The problems of elitism, premature convergance on a suboptimal solution and population diversity are relevant not only in this problem domain, but in all problem domains. The values which represent any problem map to an n-dimensional fitness landscape which, though we can't visualise it, the evolutionary algorithm must traverse in the same way.
Found the solution!
Figure 4: Found the solution!

This article has also managed to show that WPF 3D is fantastic! I haven't dwelt on how I displayed the population or the fitness landscape, but I can promise you it was very simple. I'l write an article on WPF 3D soon!