Simulated evolution gets complex
Technology Research News
It has taken more than five decades, but
the electronic computer is now powerful enough to simulate evolution.
Researchers from Michigan State University have used software to prove Charles Darwin's postulation that small, seemingly inconsequential changes over thousands of generations can result in the evolution of complex functions.
They also uncovered a twist on conventional evolutionary thinking -- it seems that some mutations that are harmful in the short run may boost long-term potential.
A better understanding of evolution promises to improve software and provide new ways to address engineering challenges.
The researchers' simulation involves bits of software that self-replicate,
but not perfectly. When the digital organisms make copies of themselves
they sometimes make random errors, just as DNA is subject to mutations
when it replicates. Many of the mutations are neutral or harmful. "But
occasionally a variant comes along that replicates faster or even performs
some logic operation," said Richard Lenski, a professor of microbial ecology
at Michigan State University.
The organisms compete to get the energy -- in the form of computer
time -- required to replicate. The organisms perform any of nine logic
operations, and if they perform them efficiently enough, they gain computer
time. "Digital organisms that solve a problem get an extra boost in their
reproductive rates," said Lenski.
The researchers studied 50 different populations, or genomes, of 3,600 individuals. Each individual began with 50 lines of code and no ability to perform logic operations. Those that evolved the ability to perform logic operations were rewarded, and the rewards were larger for operations that were more complex.
After 15,873 generations, 23 of the genomes yielded descendants
capable of carrying out the most complex logic operation: taking two inputs
and determining if they are equivalent. The lines of code that made up
these individuals ranged from 49 to 356 instructions long. The ultimately
dominant type of individual contained 83 instructions and the ability
to perform all nine logic functions that allowed it to gain more computer
In principle, 16 mutations coupled with three instructions that were present in the original digital ancestor could have combined to produce an organism that was able to perform the complex equivalence operation.
What actually happened was more complicated. The equivalence operation appeared anywhere from 51 to 721 steps along the evolutionary tree, and the organisms used anywhere from 17 to 43 instructions to carry it out.
The most efficient of the evolved equivalence functions was just 17 lines of code -- two fewer than the most efficient code the researchers had come up with beforehand. Evolving even as few as 17 lines involved a lot of incremental changes.
Because the population evolved in software, the researchers were able to trace the exact genealogy from an ancestor that was able only to replicate to progeny able to perform multiple logic functions requiring the coordinated execution of many instructions.
In order to follow the exact genealogy, the researchers developed a pair of software tools. The first tool continuously purged genotypes that lacked living descendants. This reduced the number of genotypes the researchers had to study more carefully from many millions to just a few hundred.
The second tool mapped out which of the lines of code that made up a particular organism were needed to perform any particular function. The tool shows the effect on all of the organism's performance capabilities by eliminating -- one at a time -- each instruction, said Lenski.
The simulation proved that digital organisms could, over many generations, acquire the many separate steps ultimately needed to perform a complex logic operation.
In one case, 27 of the 35 instructions that an organism used to perform the logic operation were derived through mutations, and all but one of them had appeared in the line of descent before the complex function was performed.
The results broadly supported the hypothesis that biologists since Darwin have held, said Lenski. "Complex features arise by building on simpler features. The functions use bits and pieces of older functions, then tweak them here and there to get the new function," he said.
When digital organisms were rewarded for solving simple puzzles
with more CPU time -- and thus an increased ability to send their genes
forward to future generations -- they eventually evolved a way to solve
even the most complex problem they were challenged with, said Lenski.
The researchers' results also show that this is the only way organisms can evolve, said Lenski. "Calculations imply [that] the probability of the digital organisms getting that complex all at once is astronomically small," he said.
The birds-eye view on evolution also showed a twist, said Lenski. "Biologists usually assumed that the evolution of new mutations is an uphill climb -- one in which the winners are descended from the most fit organisms in earlier generations, rather like a mountaineer that is always moving up -- or at least sideways," he said.
The researchers found that among the ancestors of the eventual winner, some had mutations that were harmful in the short run. Taking two steps back sometimes provided a better route. "Some of these harmful mutations worked well in combination with other mutations that came later," said Lenski. So while most deleterious mutations were eliminated, some were passed on, turning a short-term handicap into a long-term advantage as the subsequent evolution unfolded, he said.
The researchers' model involved 103 single mutations, six double mutations, and a pair of triple mutations; in the short-term 45 of those were good, 48 neutral, and 18 detrimental.
Thirteen of the 45 beneficial steps gave rise to logic functions
not expressed by the immediate parent. Fifteen of the 18 detrimental mutations
made the offspring slightly less fit, or likely to propagate, than the
parent. Two of the detrimental mutations cut in half the offspring's fitness.
One of these very detrimental mutations, however, did produce offspring
that one step later produced a mutation that in turn gave rise to the
complex logic operation.
The researchers are using the software to explore further evolutionary biology questions, said Lenski. "We're planning to examine the role of various factors that promote or impede the evolution of complex features," he said. The digital organisms currently self-replicate. Most of life propagates through sexual recombination between two organisms; mixing the genes of two organisms to produce a third provides a way to try out more combinations of genes more rapidly than mutation alone. "We have reasons to think [sexual recombination] may be more complicated than the simple answer that sex will speed up the evolutionary process," said Lenski.
Another possibility is adding the ability for digital organisms to sense their environments and modify their behavior accordingly, he said. Adding natural influences would allow the program to weigh in on the nature, or outside influences, versus nurture, or internal code, debate, he said.
"Ultimately we're aiming for having available for study a digital world that includes what we see as the most fundamental biological processes," he said.
The software is already being used to study biology. It has potential in the next decade to affect technology more directly, however, said Lenski. "Mixing approaches from biology and computer science has tremendous technological ramifications that... will continue to transform both fields in coming decades," he said.
Both computer science and engineering are beginning to benefit from genetic concepts and evolutionary processes borrowed from biology, including mutations, or random variation, recombination, or mixing of partial solutions, and selection, which involves keeping better solutions and discarding poorer ones, Lenski said. "To take full advantage of the possibilities will require more communication between biologists, computer scientists and all kinds of engineers," he said.
Lenski's research colleagues were Charles Ofria, Robert T. Pennock and Christophe Adami. The work appeared in the May 8, 2003 issue of Nature. The research was funded by the National Science Foundation.
Timeline: Now, 10-20 years
TRN Categories: Artificial Life and Evolutionary Computing; Applied Technology
Story Type: News
Related Elements: Technical paper, "The Evolutionary Origin of Complex Features," Nature, May 8, 2003.
May 21/28, 2003
Hydrogen storage eased
Flexible display slims
Model explains market
Big qubits linked over
Software maps group
Nanotubes smash length
DNA sensor changes
Sensor serves up
Research News Roundup
Research Watch blog
View from the High Ground Q&A
How It Works
News | Blog
Buy an ad link