I’m giving one of the Advanced Object-Oriented Programming lectures to Imperial’s first-year Computing students next week. Definitely looking forward to it, and I hope they enjoy the talk I’ve got in store. I also thought I’d digest it and post it up here, as it neatly does something I’ve been wanting to do for a while on the blog – discuss the basics of evolution that underpin ANGELINA.
The way I like to describe computational evolution is through a decidedly non-computational problem: how do you bake a cake if you don’t know the recipe? Let’s use evolution to find a recipe and solve this problem!
To use computational evolution (CE) to solve a problem, you need to know three things. Let’s step through them in turn, using our cake example. First up on the list: You need to know what a solution to your problem looks like. For us, our cake recipes are going to have three things – flour, water and eggs. That’s what a (very simple) solution looks like for us. Note that we don’t need to know how much of each ingredient we need, because that’s what evolution is here to do for us.
So now you know what goes into a recipe, what you do is you go and bake a load of cakes. And I mean a lot. How much time do you have? Because we’re going to need about ten thousand cakes. Off you go.
For each cake, you just use a random amount of each ingredient. So one recipe might have three kilograms of flour and one egg, while another recipe might have three hundred eggs and one gram of flour. Crazy, but we don’t care – we just randomise a load of recipes and bake them up.
Done that? Great. Now we’re onto the second thing you need for evolution: you need a way of scoring a solution. For cakes, we have quite a convenient way of scoring: we can taste each cake (yes, even the one with three hundred eggs in it) and give it a score out of ten, where ten is tasty and one is vomit-inducing. Ten-thousand taste tests later, we have an ordered list of our recipes, from tastiest to tasteless. Great work, we’re nearly there.
Now what you do is you take a portion of the ten thousand cakes. Just the best ones – maybe the top 1% of recipes, or the top 100. You take these recipes, and pair them off. At this point you bring in step three of evolution: you have to know how to take two solutions and make new solutions by combining them. Or, to put it another way, if we call each pair of good recipes the ‘parents’, you need to know what their ‘children’ should look like. This is where all the evolutionary stuff comes in.
To give you an example of what I mean here, let’s say we have two recipes:
- 100ml water, 3 eggs, 500g flour
- 300ml water, 1 egg, 250g flour
One possible child recipe might have 200ml water (because we decided to average out the parent values), 1 egg (we just decided to take a random parent’s egg value, unchanged) and 450g flour (we took an average of the flour, but we biased it towards the first parent). That’s one possible recipe. Another one might use different methods, or bias their averages towards other parents. In doing so, we can create lots of children from the same parents, and – just like in real life – while each child looks different from their parent recipe, they have some characteristics in common with each other.
So that’s your three steps. Step 1: guess a lot of random solutions to your problem (which means knowing what the ingredients are). Step 2: evaluate these solutions somehow (by baking and tasting the cakes). Step 3: take the best solutions and make new ones by combining their traits. If you repeat steps 2 and 3 over and over again, evaluating children and making grandchildren, then great-grandchildren and so on – if you do this thousands of times, what you’re left with is a recipe for a cake that tastes… well, pretty delicious. In theory.
Why? Because at each stage you’re picking out the tastiest recipes, and letting them produce a new generation of recipes. In a sense, their ingredients represent their genes, and your selection method is picking out the fittest cake recipes and letting them reproduce (we even use the terminology ‘fittest’ when discussing CE). Tiny improvements at each generation have a cumulative effect, resulting in delicious cake.
Of course, this is just a rough guide. There are lots of things to think about here (for instance: if I’m the only one tasting the cakes, will you like the recipe that comes out?) but this is a good idea about what evolution really involves. ANGELINA uses a heavily modified version of this technique, but the core is still there.
Anyway, I hope that was interesting. If you’re coming to the lecture next week – fret not! There’s plenty of other stuff besides this that I’ll be talking about. If you aren’t coming to the lecture but want to ask me something/point out a mistake, please comment or email me: mike @gamesbyangelina.org
Thanks for reading!
That was absolutely interesting for me, I love the way you think. Thanks for sharing!
I would really like to use this principle sometime for a game – I can imagine how this can give fun results!