The evolution solution revolution

Good scientific theories are predictive. They don't just describe the way the world is as we know it but suggest experiments or other investigation that we don't know the answer to. If the theory is correct then the predictions should turn out to be true. The theory should also be able to explain future observations. That's why Darwin's theory of evolution by natural selection is accepted by scientists. It's sometimes argued that evolutionary theory can't be good science because you can't do experiments about the past. There's more to scientific investigation than test tube science though. There have been vastly many correct predictions based on the theory of natural selection (see "Evolutionary Predictions" for a couple of recent ones). The most profound is that it predicted the need for a biological way for passing information between generations. That ultimately led to the discovery of the DNA molecule and within half a century the mapping of the human genome as well as that of other animals.

Computer science naturally

Where does computer science come in? Well it works both ways. Computer simulations can be used to explore whether things might be possible. For example, some people find it hard to believe that complex biological features like an eyeball could possibly come about step by step as predicted by natural selection. Computer simulations have shown that such things are feasible: for example an early such computer experiment showed it is possible to construct sequences of partial eyeballs from single light detecting cells to complete eyeballs that each work in a way that would help a creature survive. This compares well in fact with the range of similar "eyes" found in real creatures.

Evolving answers

In the other direction the ideas of evolution have given computer scientists ideas for new ways to program - the notion of genetic algorithms. Computer science is about coming up with solutions to problems and that is exactly what nature does over time - adapt animal species via natural selection to allow them to survive better in their changing environments. The idea is that to solve a problem you turn it into "digital DNA" and evolve a solution.

Instructive DNA

DNA is the biological molecule that codes the instructions for creating all living things on earth. It's a sequence of instructions, data, that cells use to build new cells, and it's also the key to evolution. When species mate, part of the mother's and part of the father's DNA combine to give the new instructions for the child. That's why you look a bit like your mum and dad. Parts of their data were used to build you. That DNA has been crossed over. When a species is under environmental threat often only particular types of offspring survive: those that can run fastest, or climb highest or blend into the background best. Inspired by Darwin, this is what english philosopher Herbert Spencer pithily called "survival of the fittest": the new set of instructions in an offspring, combined from parents, can give that offspring a survival advantage. Survival means this creature can go on to breed itself and will pass those useful instructions to its offspring and so on. Very occasionally due to the effects of cosmic rays or other factors the DNA can be changed, the chemical sequences are mutated. Normally this causes death. The instructions are corrupted and the offspring dies, but from time to time a non-lethal mutation occurs, and this can lead to offspring with a new survival trick. If it's advantageous it will let the offspring and its descendants thrive. In effect the process of evolution keeps the species and the environment matched to one another. You could say the species solves the problem of survival in the environment.

Visiting with a Genetic Algorithm

So computer scientists can now take a problem, code it up as a sort of digital DNA and use the evolutionary model, crossover between parents to create offspring and mutation, to find a good solution. A classic example is the Travelling Salesperson problem. In this problem you have to visit say twenty towns, and do the least travelling (you need to keep the travelling expenses down). We start by randomly creating a population of 'creatures' whose digital DNA is simply a list of the twenty towns (say numbered 1-20) initially in random order. We then test how fit each of these 'creatures' is by calculating the amount of travel expenses each of them requires (how expensive that route would be to follow). From our initial population of possible solutions we choose the best solutions, those with the lowest travel expenses, and let these bred together: making a new route with parts from each parent. Those solutions with high costs don't survive in this low cost financial environment, and are simply killed off, removed from the program. The next generation, made by swapping (crossover) the digital DNA of the original best solutions, are then tested, again the best solutions survive and we breed them to create a new generation and so on. Many thousands of generations later we have really good solutions, which have survived because they are a good solution to the problem.

Mutate and explore

We always have a small random mutation rate in the background, as this parent offspring breeding can often result in you only exploring a good solution, they are breeding in only one isolated part of all the possible good solutions, and possibly missing the best solution, which may require something very different. After running a genetic algorithm on your problem you simply turn the digital DNA back into, in this case the list of towns in order, and you're done. Problem solved.

Genetic Programming - growing the solution

A variation of this is called genetic programming. Here the digital DNA are bits of program code that if executed solve the problem. They are linked together through something called a tree structure. One part of the program (the root) calls another bit of code in the program (the leaf). This leaf can then be a root for another couple of leaves, and so on. The whole program, if you wrote it out, looks like a tree, with the links between code as branches. To breed a genetic program you swap branches of this tree around. Most of the programs don't work of course, but some will and if you chop and change (and do the occasional mutate where you remove bits completely for example), and keep working on the best over many generations you can create computer programs that actually work, and work very well.

Better or best?

You can use a genetic algorithm, as long as you can take your problem and turn it into digital DNA: a list of elements called a representation (numbers in DNA = towns in the example, or trees of bits of code in Genetic Programming), and define a way to calculate your creature's 'fitness' (for example the travelling expenses needed to go round the towns in the order given). There are many different variants on the basic genetic algorithm which try to ensure that they find the best solution possible rather than just a good solution. This ability to find the very best, or global solution, cannot yet be guaranteed mathematically - nature doesn't guarantee perfection either. However Genetic Algorithms are useful and powerful and have been used to solve problems in water distribution and computer networks, robotic learning, school timetabling and even back into biology and chemistry to calculate the shapes of folded proteins or atomic forces.

Evolution works

So computer science gives yet another way of exploring predictions about the details of how evolution works and can even help suggest things to look for in nature. On the other hand, by understanding how nature through DNA and evolution leads to good solutions to ensure survival in often incredibly harsh environments, scientists have created a powerful new form of computing in the genetic algorithm.

Genetic algorithms are the basis of the human versus machine olympics: Sodarace. Go try it out for yourself - join a sodarace (www.sodarace.net) and see how powerful genetic algorithms can tune a virtual beast to its current environment!