Melanie Mitchell is a research computer scientist at the Santa Fe Institute, a New Mexico think tank specialising in emerging science. Her research interests include Intelligent systems and machine learning, complex systems, evolutionary computation and artificial life.

Melanie Mitchell says computer scientists and biologists can learn a lot from each other. She's studying how natural systems perform computation, and she's using her findings to develop new kinds of computational methods. Mitchell recently told Computerworld's Gary H Anthes how we can solve some complex problems by letting systems evolve solutions through a process of natural selection.

Is evolutionary computing beginning to move out of the academic realm? This whole field has really exploded recently. More and more people are using evolutionary methods to do real-world applications. Examples are factory job scheduling, supply chain optimisation and automatic design of things like circuits.

What's driving this? People have learned how to exploit these methods better, and more and more people are getting interested in biologically inspired methods in computer science. And we have the kind of computer power to really use these algorithms on a much larger scale. They are very computationally intensive, and a lot of people are now looking at genetic algorithms implemented on a parallel computer or some large network of computers.

Is anything holding back even wider use of evolutionary computing? People don't understand very well what characterises problems that evolutionary methods work well on. That's an open problem. There's some intuition, but no real formal analysis.

Nevertheless, what can you say about why this method is sometimes so effective? More and more people in the field of artificial intelligence are finding that if you want to create very complex computing systems that act intelligently or in lifelike ways, that's very difficult to engineer by hand. You have to let systems learn on their own. Evolutionary computing is one kind of machine learning; neural networks is another.

You're doing research in co-evolutionary computing. How does that differ from evolutionary computing? In machine learning, the traditional way you get a system to do what you want is you come up with a fixed set of training examples -- examples of the problem it's going to be faced with. Then you try the system out on the training examples, and if it gets the right answer, it gets credit, and if it gets the wrong answer, it gets punished. But in co-evolution, you actually evolve the training examples, and they evolve to be increasingly challenging. So you try to evolve test cases; you are generating them dynamically. Manufacturing systems could lend themselves to this, because you might try to evolve situations that would break them because you are trying to make them as robust as possible.

Will computer scientists continue to learn lessons from biologists? Yes. Learning how biological systems process information will eventually lead to new kinds of computing systems. One of the problems in computer science right now is that the standard design for computing is very unlifelike. Living systems have many relatively simple components, and each component does some simple thing, but collectively, the whole network of components computes very complicated things. That has a lot of advantages, such as it can be much faster and more robust.

Can you give an example of such a system? Scientists are understanding more and more about how the immune system is really an information, and in some ways a cognitive, system. So in computer security, you might do immune-system-like computation.

Can biologists learn from computer scientists as well? Absolutely. It cuts both ways. Computer scientists are thinking about information-processing in machines, and sometimes that gives rise to new ideas in biology. Computer science and biology are intimately connected.

Evolution via genetic algorithms

Imagine a very complex problem - supply chain optimisation, for example - in which a computer generates millions of trial solutions completely at random and then picks the one with the lowest cost. Such a trial-and-error approach isn't practical with big problems because there are just too many combinations of variables to try even a small fraction of them.

However, that's essentially what evolutionary computing does -- but with one major difference. It converges on an answer by breeding better and better solutions from the most promising parents in each generation of trials. Here's Melanie Mitchell's explanation:

"Evolutionary algorithms start out with a randomly generated population of from 50 to 500 candidate solutions. At each time step, or generation, all the individuals are evaluated and assigned a number, called fitness. It's a measure of how good a solution it is. Then some percentage, usually between 20 per cent and 80 per cent, of the highest-fitness individuals get to reproduce.

"They reproduce two ways: by crossover, where you take one part of one individual and some part of another individual and combine them, and by mutation, where you randomly change parts of an individual. The offspring are put into the next generation, and the whole process starts again."