Teaser video:
“Neuroevolution,” which literally means “Evolving brains,” sounds like a tired sci-fi plot: Scientists create a super-smart computer that gets out of control and goes on a wild rampage, stopped only seconds from starting a nuclear holocaust (or not, in the case of the Terminator movies).
Yet, far from fiction, neuroevolution is what I do on a daily basis: Evolving artificial brains in a computer is the foundation of my Ph.D. research. It’s not something I came up with, and is not a brand new idea — neuroevolution is an approach to artificial intelligence that has been around for 15 years. It’s inspired by how biological brains evolved through natural evolution.
“Oh, um. You evolve…brains? In a computer?”
Whenever you meet someone new, the question, “What do you do?” inevitably percolates into conversation. To avoid the glazed-over eyes that tend to result from my explanations, my vague canned response is that I am a graduate student in computer science. Although what I do is not insanely complicated, it is far-enough removed from typical day-to-day experience that explaining it in a sound-bite is damn near impossible.
The more abstract a concept is, the craftier one must be to describe it both intelligably and succinctly. For example, it’s fairly easy to explain what Sushi is to someone who doesn’t know because Sushi is “concrete” — it’s touchable, edible and related to “fish,” a universal concept.
You could say, “carefully-prepared raw fish,” and not be too far off the mark. But it is harder to explain to the uninitiated what electric current is, because it is not something “physical” nor directly visible. But although electric current is abstract, we can quickly begin to understand it by relating it to something familiar and “real” like a river current. Electricity “flows” in a similar way to water.
So, while someone’s eyes might glaze over when you talk about electrons, relating electricity to a river is more intuitive. So it turns out that only I am to blame for the glazed-over eyes of my acquaintances because I have not been clever enough to explain clearly and simply what I do. And so I hope to atone for past blank stares of nonrecognition with this post: Neuroevolution is simple and interesting, and I want to tell you why in an easy way.
Dancing Bees
Have you ever been to a zoo? Or an aquarium? The seemingly limitless variety of living creatures, and the amazing things they can do, is fascinating. An archer fish shoots a powerful, carefully-aimed stream of water from its mouth to knock insects into the water, then quickly swallows the stunned critters. A bumblebee dances in two separate ways, depending on how far away it is from food, to show its comrades where to forage. Crows fashion tools and even learn to bait-fish with bread crumbs. The diversity and complexity of nature is awe-inspring.
The source of this diversity and complexity is natural evolution. Although it is hard at first to accept that an unguided process could produce such magnificent artifacts (like your face, you handsome reader), evolution is nearly universally accepted by scientists because of an overwhelming amount of evidence, such as fossils and vestigial organs.
“Nothing in Biology makes sense except in the light of evolution,” said a famous evolutionary Biologist, Theodosious Dobzhansky. If you believe in evolution, then you also must believe that evolution shaped our brains; our impressive intelligence is somehow the result of billions of years of trial and error experiments.
The point is that, without intelligence, evolution created a ton of really cool things, including our own intelligence. This mind-blowing possibility hints at the potential of neuroevolution: Perhaps we can harness the general process of evolution within a computer to evolve intelligent computer-brains! Trippy, right? But, before we are ready for a more complete description, I want to briefly digress and talk about artificial intelligence in general, the field of research that seeks to make smarter machines.
And what country is Toronto in, Watson?
Perhaps most of us are most familiar with Artificial Intelligence from movies such as 2001: A Space Oddessey, AI, Stealth, the Terminator, etc. In these movies scientists create an intelligent computer, and then it goes crazy and kills everybody. One part of this is based in reality: There are researchers that try to create more intelligent computers. In fact, I am one of those researchers.
To put your minds at rest, current research in AI is far from creating true human level intelligence. I’d guess that it will at least be a few decades yet before we reach that ambitious goal. A question people often ask is “Why?”: Why would we want intelligent computer programs? There are many different answers. One might side-step the “why” and appeal to curiosity; I for one, am curious about what intelligence is, and how we can better understand it. I think we might truly understand intelligence only when we can recreate it.
But there are also practical reasons we might want intelligent programs, too. For example, it wouldn’t be practical for Amazon to hire a massive team to create a personalized list of products one might like to buy for everyone who ever purchased things on Amazon. However, with AI techniques, a computer can find correlations like: people who bought product X also tended to buy product Y, and from these correlations automatically make personalized lists. More and more tasks that once had to be done painfully by hand, like arithmetic or checking spelling, can now be automated by computer programs with a small spark of what might be called intelligence.
There have been many interesting successes of AI. I’ll highlight two of the most famous here.
The first is when the best chess player in the world, Gary Kasparov, lost to Deep Blue, a supercomputer made by IBM. We once thought that chess was something that required true intelligence to master, because the game is deep, has many complicated strategies, and is difficult for humans to master. However, it is clear that chess does not require true intelligence to master, because deep blue, although it is very good at chess, can not do anything else at all. It won only by considering many many moves, using brute force calculation impossible for humans.
A second very famous success of AI is Watson, the Jeopardy-playing AI. It beat Ken Jennings, arguably the best jeopardy player of all time. This at first seems incredibly impressive, and it is! Who would think that a computer could be competitive with humans in a task like general question and answer? It is especially impressive because the questions in jeopardy tend to be playful and tricky.
However, Watson, like Deep Blue, is far from any “true AI” in that it is not “creative.” It won by clever human-designed algorithms coupled with four terabytes of human-curated data (Wikipedia and more). Also informative was its embarassing failure to recognize that “Toronto” is not a US city. Watson, like Deep Blue, does not have ‘general intelligence’ — it can only answer questions, and does not ‘reason’ in the traditional sense but again relies on cleverly designed tricks, raw brute force, and an enormous database of curated facts to perform well. Wouldn’t you be pretty good at jeopardy too if you could browse all of Wikipedia in a fraction of a second?
These Watson and Deep Blue approaches, although impressive and practical, seem to have almost no relation to general intelligence, which is what I am curious about. Why is that a toddler can still do things that a supercomputer can’t?
We only have one working example of general intelligence: Humans. And humans are the result of natural evolution; so, in order to create artificial intelligence, isn’t the most obvious approach to follow that one working example and examine evolving brains through artificial evolution? Of course, it’s not the only approach, but it has precedent on its side.
Evolution: Natural and Artificial
Before explaining the strange concept of artificial evolution within a computer, it’d be good to first understand how natural evolution works. How does it create organisms that are well-adapted to their environments like archer fishes or bumblebees? While we might all remember some vague ideas from science class involving “survival of the fittest” and “natural selection,”here are the three simple, concrete principles that underlie evolution:
1) Selection
In nature, animals typically have more children than can survive in the world. There’s not enough food for all the rabbits, and in addition wolves will eat those that are too slow. Natural selection is just that a lot of animals die before they reproduce. It is like a filter that generally only allows better-adapted animals to pass through.
Animals better at surviving and reproducing will tend to have more offspring, which spreads their genes and physical traits onwards. Animals worse at surviving and reproducing have less chance of spreading their genes. So, a gene that makes a rabbit faster might spread, while a gene that makes a rabbit slower would probably die out, because wolves might catch most slow rabbits before they had a chance to make rabbit babies.
While in nature animals are ‘selected’ naturally if they survive long enough to reproduce, selection can also be artificial. That is, humans can do the selecting instead of nature: Plant breeders might choose to mate the prettiest flowers together, or dog breeders might choose dogs that are smaller or friendlier or cuter, hoping that the children of that dog will also share those traits. We breed race horses for speed, breed cows to give more milk, and so on.
Selection, whether artificial or natural, tends to give evolution some direction, whether towards cuter dogs or faster rabbits better able to evade wolves.
2) Variation
The first principle was selection, that some animals would spread their genes, and others wouldn’t, and that evolution is given some sort of direction by what we select for. Nature selects for the ability to survive and reproduce, but human breeders may select dogs for cuteness instead.
The second principle is variation. That is, every dog is not exactly the same; dogs vary. Some racehorses might run faster or slower, some flowers might be prettier or uglier, and some archer fish might be more or less accurate at drilling insects with its built-in squirt gun. Variation enables selection to push evolution in some particular direction.
If all dogs were exactly the same (no variation), selection would have no distinctions to make among those dogs; you would find no cuter dogs because they would all be of the same cuteness.
Variation in itself doesn’t provide a direction, because it may create uglier dogs more often than it creates cuter dogs. But, selection among a variation on animals can push evolution in a direction, because it might filter out those uncute dogs; a human breeder would breed together the cute ones and not the uncute ones. What variation does is give that breeder choices.
3) Heritability
The third principle is heritability. Evolution requires that variation is generally passed on to its children.
People might say you resemble your mother, or that you have your father’s eyes: You resemble your parents. The reason for this is that your DNA, all of your genes, is a combination of your parents’ genes.
Heritability is the property that a child resembles their parent. If this wasn’t the case then there would be no continuity — if a bumblebee gave birth to a chipmunk, then all would be chaos. In that crazy world, you would never be able to find a really cool bumblebee if that is what you were were looking for, because a bumblebee’s children could be anything.
Another way of looking at this is by thinking about the game “telephone.” There is a line of kids, and the first kid thinks of a clever phrase. He then whispers it to the second kid, who whispers it to the third, and so on. By the end, the message is horribly garbled. In this situation there is little heritability, because the message has changed so much.
On the other hand, if one simply forwards an email without making any changes, the message will stay the same despite how many times it is forwarded. In this situation, there is high heritability. Of course, if heritability is perfect then there will be no variation; but if heritability is too flawed, then selection will have trouble producing anything cool because things will get too garbled too quickly.
It seems like the best idea is to have almost perfect copying, but allow for small mistakes to sometimes seep in, to provide for modest variation. This is what natural evolution does; each of us has tiny mutations in our DNA that make us unique.
Evolution, in nature, in a nutshell:
1) Selection – is natural selection, that creatures better at surviving will pass on their genes, meaning that in general the ability to survive tends to improve over time.
2) Variation – happens through animals having unique DNA, which occurs through infrequent errors when copying DNA and also through mating, which makes a mix of two existing DNAs from different parents.
3) Heritability – happens because copying errors are infrequent in DNA, so the game of telephone between parent’s DNA and child’s DNA is accurate. There may be some small changes, but if these changes are too severe — for example, a frog born with an additional leg, that frog is unlikely to survive to pass on its genes.
Evolution of Hip Hop
What is cool about evolution is that it is *general*, it isn’t just confined togenes and DNA. For example, ideas also evolve. Leeches are no longer best practice for treating disease and fanny-packs and pogs are no longer cool. Right now, paranormal romance (read twilight, etc.) is particularly popular, but twenty years from now, some other genre will be in vogue.
Music evolves too! A branch of blues music evolved into funk, and a branch of funk led to hip-hop. We tend to support those artists with addictive, cool-sounding new songs, and variations of those songs fill the air-waves. Musical ideas are ‘selected’ by listeners who buy albums or call into radio stations to request songs. These musical ideas vary over time: Artists inspired by a cool song will make new songs with similar sounds or traits, and other artists might be inspired by this new song. The evolution of cultural ideas like fads or music is called memetics, which is an intriguing topic in its own right.
However, right now, I want to discuss artificial evolution within a computer, which is but a hop, skip, and a jump away from finally understanding neuroevolution!
Evolving bits
When you were in middle school, your teacher gave you annoying algebra problems to solve. She’d say, “Hey, Joel, find the value of x for this equation: 2x-10=3.” Listen, lady, I’d sure love to but there’s a Buffy marathon on TV. Wouldn’t it be cool if we could let evolution solve this math problem for us while we eat ham sandwiches instead?
The answer, is yes, of course! We all love ham sandwiches and despise intellectual labor. The question, though, is how we can set up those three factors that cause evolution (selection, variation, and heredity) to do our homework for us?
Let’s start with heredity.
1) Computerized Heredity
In nature, DNA is what is changed by evolution. For evolution in a computer, we can make our own DNA up. Whatever we want. Muahahaha. It can be as simple as a list of numbers. For simplicity’s sake, it can even be just a single number.
Okay. So now we have our artificial DNA that is of just one number. Let’s call this one number x, because that is what we are trying to find to solve this lame algebra problem. So, our ideal piece of artificial DNA, which is just a number, will contain the correct value of x, the one that makes the equation true.
We can make copies of this artificial DNA, this one number, by simply writing down this number in a different place. These copies of that number are little chidldren DNAs of the original artififical DNA. Because these copies of the DNA resemble each other (well, they are the same), we’ve achieved heredity! Boom.
2) Computerized Variation
Okay, well, how can we make variations of this artificial DNA, this one number? How about when we copy a parent DNA number to a child DNA number, we make a slight random change to it. We just add a little bit or subtract a little bit. This way, the child number will resemble the parent number, but it won’t be exactly the same. So, the parent number might be 2.31, and the child might be 2.35 or 2.25. In this way, the children will vary. Boom.
3) Computerized Selection
The last element of this computerized evolution game is selection. We need to come up with a way of selecting those pieces of artificial DNA that are closer to solving our algebra problem than others.
One way of doing this is just plugging the artificial DNA x into the equation, and seeing how close it is to making the equation true. For example, if we set x to be 1 in our equation of 2x-10=3, we get 2-10=3 or -8=3. The left side is 11 different from the right side. We can say that we want to select those x’s that make the difference between the left side and right side of the equation smaller. If we set x to be 2, we get 4-10=3 or -6=3. In this case, the left side is 9 different from the right side, which is a smaller error than when x was 1. So, given a choice between artificial DNA with x=1 and x=2, we’d select x=2.
Our automatic selection mechanism plugs in the artificial DNA x into the equation and calculates how big the error is. We choose the DNAs that make this error the smallest.
It’s magic
We can now make a recipe for solving our little math problem. This is called an evolutionary algorithm, because it employs evolution in a methodical way that can be computerized.
Step 1: Put ten Artifical DNAs in a list (aka pick ten random numbers)
Step 2: Assign a score to each artificial DNA based on its error when we plug it into the equation 2x-10=3 (the higher the error, the worse the artificial DNA is). If the error is really small quit, otherwise go to step 3.
Step 3: Make a new list by taking the five best artificial DNAs from the last list and writing them down twice; when writing down a number, add or subtract a small number from it first to generate some variation.
Step 4: Go to step 2
Magic in practice
So I went ahead and translated our little recipe into Python, an actual computer language. You can look at the code here if you are curious. Each time through the loop described in steps 2 and 3, the program prints out the error of the best artificial dna and its x value. Next we’ll look at a print-out from a run, and then a graph. You can see that it quickly finds the solution to our equation 2x-10=3, which turns out is 6.5.
Loop # 1 Lowest error: 2.48 Best DNA: 5.26
Loop # 2 Lowest error: 2.35 Best DNA: 5.32
Loop # 3 Lowest error: 2.24 Best DNA: 5.38
Loop # 4 Lowest error: 2.15 Best DNA: 5.42
Loop # 5 Lowest error: 2.07 Best DNA: 5.46
Loop # 6 Lowest error: 2.03 Best DNA: 5.49
Loop # 7 Lowest error: 1.88 Best DNA: 5.56
Loop # 8 Lowest error: 1.79 Best DNA: 5.60
Loop # 9 Lowest error: 1.72 Best DNA: 5.64
Loop # 10 Lowest error: 1.68 Best DNA: 5.66
Loop # 11 Lowest error: 1.57 Best DNA: 5.72
Loop # 12 Lowest error: 1.43 Best DNA: 5.79
Loop # 13 Lowest error: 1.47 Best DNA: 5.77
Loop # 14 Lowest error: 1.30 Best DNA: 5.85
Loop # 15 Lowest error: 1.14 Best DNA: 5.93
Loop # 16 Lowest error: 1.04 Best DNA: 5.98
Loop # 17 Lowest error: 0.95 Best DNA: 6.03
Loop # 18 Lowest error: 0.76 Best DNA: 6.12
Loop # 19 Lowest error: 0.77 Best DNA: 6.11
Loop # 20 Lowest error: 0.72 Best DNA: 6.14
Loop # 21 Lowest error: 0.61 Best DNA: 6.20
Loop # 22 Lowest error: 0.49 Best DNA: 6.25
Loop # 23 Lowest error: 0.30 Best DNA: 6.35
Loop # 24 Lowest error: 0.44 Best DNA: 6.28
Loop # 25 Lowest error: 0.28 Best DNA: 6.36
Loop # 26 Lowest error: 0.25 Best DNA: 6.37
Loop # 27 Lowest error: 0.13 Best DNA: 6.43
Loop # 28 Lowest error: 0.01 Best DNA: 6.50
And here is a little graph showing how error decreases to around zero over time:
So what we’ve shown here is that it is possible to harness evolution to solve problems within a computer. We could have it solve other equations by changing the error function. One cool aspect of evolving solutions to problems is that we just specify what we are looking for, and evolution will try and find it.
While our artificial DNA here was just a single number, the artificial can be more complicated. For example, we could evolve x and y for a more complicated equation. But more interesting than this trivial addition is neuroevolution, where the artificial DNA does not represent a sequence of numbers but an artificial brain that can control robots. Through neuroevolution we can get robots to do cool things while we eat ham sandwiches.
Darwin meets Frankenstein
What’s in a brain, anyways? Basically our brain is a collection of neurons that are wired together in various ways, like an incredibly complicated circuit. Neurons are cells that do basic computation. They can get signals from the real world (like from our eyes or ears) or control our muscles. Neurons are what enable us to sense the world and do things. A bunch of neurons centralized in our brain is what give us instincts and thoughts.
Now, if we want to make an artificial brain for a robot, we can think of a brain as a collection of neurons and wires that connect them together. In the context of a robot, these wires may connect neurons to the robot’s motors or to its sensors (like a video camera), so that the robot can move in response to how it sees the world. The wires may also just connect neurons to each other.
Intermediate neurons that sit between the sensors and the motors can compute functions of sensory inputs to enable more sophisticated robot behaviors. For example, running away when you smell a predator is a simple behavior that can be accomplished by directly connecting the nose sensor to the motors. However, predicting the trajectory of a moving baseball might require doing some basic calculations that require lots of neurons connected in complicated ways.
But beyond understanding how a robot could have an artificial brain and what such a brain might be built from, what we would really like to do is to have evolution design these artificial brains for us, which is the essence of neuroevolution. A simple way to do this is to construct an artificial DNA that acts as a wiring diagram for an artificial brain. You can imagine that such diagrams could be twiddled slightly, by changing the strength of a connection between two neurons, or adding in new neurons, or by adding or removing connections entirely. This is how evolution can mutate an artificial robot brain.
And so you can implant these robot brains in a robot, turn the robot on, and see what its brain induces it to do. Different brains can cause different behaviors because they will enact differing policies. One brain’s policy might be to purposefully ram into walls, another might spin aimlessly in circles. The question remaining is how can we use evolution now to get a brain that does something we want?
Like we did in the case of evolving the solution to the equation, we need a measure of goodness. This measure can aide us to select good robot brains and to throw away the bad ones. Perhaps you want to evolve a robot that can navigate a corridor. One measure of goodness for evolving such a policy is to look at where the robot ends up, and see how far it is from where we would like it to be. That is, imagine we always start a robot at the beginning of a corridor, and let it roam for awhile. After a fair amount of time has passed, we look at its position. If it is near the end of the corridor, we deem it as good.
With the ability to represent a brain as a wiring diagram, to slightly mutate these diagrams, and a way of evaluating how good these diagrams are, we are ready to craft our first neuroevolution experiment!
Magic part two: Evolving Robot Brains
We can now make a recipe for solving our corridor navigation problem with another evolutionary algorithm.
Step 1: Put one hundred Aritifical Brain DNAs in a list (aka make one hundred random wiring diagrams)
Step 2: Assign a score to each artificial DNA based on how far a robot gets through the corridor when we plug in the brain the artificial brain describes. The farther the robot is from the end of the corridor than the worse the artificial DNA is. If the robot gets very close to the end then we are successful and we can stop, otherwise go to step 3.
Step 3: Make a new list by taking the fifty best artificial DNAs from the last list and writing them down twice. Then slightly change the wiring diagrams of all of these DNAs to induce some new variation.
Step 4: Go to step 2
Frankenstein in the Corridor
I went ahead and codified this experiment as well, the source code is written in Python and is available through github. Here is a picture of the corridor:
This is a screenshot from the corridor simulator, viewing the corridor from a top-down perspective. The blue X’s are the walls of the corridor, the grey + is the robot’s intended destination, and the red line is the robot. The green stars projecting from the robot are a visualization of its wall sensors, which are also visualized at the bottom of the screen.
After 200 generations, usually the evolutionary algorithm has evolved a brain that can navigate the corridor. Now, for the fun part, a few videos showing a few examples of evolved artificial brains. The first video is from an intermediate solution, one that does not completely make it through the corridor.
The next video is from a solution:
What is really cool here is that evolution has discovered a (albeit simple) brain that can drive a simulated robot through a corridor. We didn’t have to program it to accomplish the task, we trained it. Our measure of how close a robot got to the end of the corridor was used to guide evolution towards a good brain.
It isn’t always easy to train artificial brains (and in fact these difficulties are what my research is centered on), but I can remember how excited I was when I discovered that evolution could be used within a computer to automatically learn things. Hopefully I’ve propagated some of that excitement to you.