Simulated evolution gets complex

By Kimberly Patch, 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 time.

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
Funding:   Government
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

Page One

Hydrogen storage eased

Flexible display slims down

Simulated evolution gets complex

Model explains market movements

News briefs:
Big qubits linked over distance
Software maps group work
Magnesium batteries show mettle
Nanotubes smash length record
DNA sensor changes color
Sensor serves up body slices


Research News Roundup
Research Watch blog

View from the High Ground Q&A
How It Works

RSS Feeds:
News  | Blog  | Books 

Ad links:
Buy an ad link


Ad links: Clear History

Buy an ad link

Home     Archive     Resources    Feeds     Offline Publications     Glossary
TRN Finder     Research Dir.    Events Dir.      Researchers     Bookshelf
   Contribute      Under Development     T-shirts etc.     Classifieds
Forum    Comments    Feedback     About TRN

© Copyright Technology Research News, LLC 2000-2006. All rights reserved.