Evolution is no longer confined to the physical world. For billions of years, vastly different life forms have been cooperating and competing, conquering and struggling, and living and dying, all in relentless pursuit of increasing the survival of their species. Now, computer scientists are developing solutions to their hardest problems by recreating the process of evolution in computers using genetic algorithms (GAs).Researchers have used the principles of evolution to design everything from airplane wings, boat hulls, and satellite antennae to efficient bus routes, robot vision, and electronic circuits.
Before the technique, computer scientists often followed the great physicist Richard P. Feynman’s three-step algorithm: 1) Write down the problem. 2) Think really, really hard. 3) Write down the solution. Using genetic algorithms, computer scientists can solve hard problems not by sitting and scratching their heads, but instead by evolving solutions in a virtual world. The solutions produced are often unlike anything that human engineers can conceive, as they are sometimes hindered by preconceptions about how problems should be solved. Evolution has no such bias, and as a result can find solutions that are original and alien.
A genetic algorithm breeds solution. The algorithm can create solutions to diverse problems, such as the shape of a freighter’s hull, a jet fighter’s wings, or even an airport’s flight schedule. Like a horse breeder starts with a herd of wild horses, an algorithm starts with a group of possible solutions to a problem. And like a horse breeder wants to breed a fast horse, an algorithm wants to breed a good solution. The way to bred fast horses is to mate the fastest horses in the band. Similarly, the GA breeds good solutions to find even better ones.
But whereas a horse breeder starts with physically capable horses, a GA starts with solutions equivalent to mules. Its first answers are little more than guesses – horrible solutions to the problem. At this point, good and even satisfactory solutions are unknown.
The GA then finds the best of the group of bad solutions and virtually mates them together, producing a new generation of solutions a little better than before. The best of these virtual offspring are then chosen to pass on their traits to the next generation of solutions. Just like in real evolution, the offspring mutate every once in a while.
Even by the 100th generation, the solution is no stallion. But with each generation, the GA gets a bit closer to a good solution. In some cases, it takes hundreds of thousands to millions of generations to get a solution that lives up to the GA’s expectations. But eons of evolution can be simulated in hours, because the whole process takes place in an abstract virtual world deep inside a computer.
Yet there are drawbacks to the method. Although genetic algorithms have been applied with fantastic success in some cases, they fall short of being universal problem-solvers. And although evolutionary eons can be compressed into hours, finding the precise settings that will give a good solution can take months. How do you figure out which solutions are best? How often do you mutate the offspring? Computer scientists are reduced to trial-and-error knob-twiddling to get the right conditions.
Dr. Joelle Pineau, studying Artificial Intelligence (AI) at McGill University, feels that the beauty of the technique blinds people to these issues.
“They’re too cute. Genetic algorithms don’t get bonus credibility just because that’s what nature did,” she says.
Professor Doina Precup, also in AI at McGill University, mentioned some of their drawbacks.
“They are quite slow, and they require quite a bit of fiddling,” she said.
Considering that they were inspired by evolution, it’s not a shock that they’re slow. But if they are too slow, finding a good solution becomes impossible.
However, not all computer scientists are put off by the shortcomings of genetic algorithms. While he acknowledged their drawbacks, Professor Michel Toulouse of the Université de Montréal also emphasized that they caused a revolution in computer science.
“Genetic algorithms’ main contribution today are that they opened the door to biologically-inspired methods. The beauty and success of genetic algorithms motivated other computer scientists to look to biology for inspiration,” he said.
Genetic algorithms have opened researchers’ minds to nature’s techniques of solving problems, and today, some of the best problem solving strategies are inspired by biology.