digital evolution

[narayan]

testing darwin

If you want to find alien life-forms, hold off on booking that trip to the moons of Saturn. You may only need to catch a plane to East Lansing, Michigan.

The aliens of East Lansing are not made of carbon and water. They have no DNA. Billions of them are quietly colonizing a cluster of 200 computers in the basement of the Plant and Soil Sciences building at Michigan State University. To peer into their world, however, you have to walk a few blocks west on Wilson Road to the engineering department and visit the Digital Evolution Laboratory. Here you’ll find a crew of computer scientists, biologists, and even a philosopher or two gazing at computer monitors, watching the evolution of bizarre new life-forms.

These are digital organisms—strings of commands—akin to computer viruses. Each organism can produce tens of thousands of copies of itself within a matter of minutes. Unlike computer viruses, however, they are made up of digital bits that can mutate in much the same way DNA mutates. A software program called Avida allows researchers to track the birth, life, and death of generation after generation of the digital organisms by scanning columns of numbers that pour down a computer screen like waterfalls.

After more than a decade of development, Avida’s digital organisms are now getting close to fulfilling the definition of biological life. “More and more of the features that biologists have said were necessary for life we can check off,” says Robert Pennock, a philosopher at Michigan State and a member of the Avida team. “Does this, does that, does this. Metabolism? Maybe not quite yet, but getting pretty close.”

One thing the digital organisms do particularly well is evolve. “Avida is not a simulation of evolution; it is an instance of it,” Pennock says. “All the core parts of the Darwinian process are there. These things replicate, they mutate, they are competing with one another. The very process of natural selection is happening there. If that’s central to the definition of life, then these things count.”

It may seem strange to talk about a chunk of computer code in the same way you talk about a cherry tree or a dolphin. But the more biologists think about life, the more compelling the equation becomes. Computer programs and DNA are both sets of instructions. Computer programs tell a computer how to process information, while DNA instructs a cell how to assemble proteins.

The ultimate goal of the instructions in DNA is to make new organisms that contain the same genetic instructions. “You could consider a living organism as nothing more than an information channel, where it’s transmitting its genome to its offspring,” says Charles Ofria, director of the Digital Evolution Laboratory. “And the information stored in the channel is how to build a new channel.” So a computer program that contains instructions for making new copies of itself has taken a significant step toward life.

A cherry tree absorbs raw materials and turns them into useful things. In goes carbon dioxide, water, and nutrients. Out comes wood, cherries, and toxins to ward off insects. A computer program works the same way. Consider a program that adds two numbers. The numbers go in like carbon dioxide and water, and the sum comes out like a cherry tree.

In the late 1990s Ofria’s former adviser, physicist Chris Adami of Caltech, set out to create the conditions in which a computer program could evolve the ability to do addition. He created some primitive digital organisms and at regular intervals presented numbers to them. At first they could do nothing. But each time a digital organism replicated, there was a small chance that one of its command lines might mutate. On a rare occasion, these mutations allowed an organism to process one of the numbers in a simple way. An organism might acquire the ability simply to read a number, for example, and then produce an identical output.

Adami rewarded the digital organisms by speeding up the time it took them to reproduce. If an organism could read two numbers at once, he would speed up its reproduction even more. And if they could add the numbers, he would give them an even bigger reward.Within six months, Adami’s organisms were addition whizzes. “We were able to get them to evolve without fail,” he says. But when he stopped to look at exactly how the organisms were adding numbers, he was more surprised. “Some of the ways were obvious, but with others I’d say, ‘What the hell is happening?’ It seemed completely insane.”

On a trip to Michigan State, Adami met microbiologist Richard Lenski, who studies the evolution of bacteria. Adami later sent Lenski a copy of the Avida software so he could try it out for himself. On a Friday, Lenski loaded the program into his computer and began to create digital worlds. By Monday he was tempted to shut down his laboratory and dedicate himself to Avida. “It just had the smell of life,” says Lenski.

It also mirrored Lenski’s own research, launched in 1988, which is now the longest continuously running experiment in evolution. He began with a single bacterium—Escherichia coli—and used its offspring to found 12 separate colonies of bacteria that he nurtured on a meager diet of glucose, which creates a strong incentive for the evolution of new ways to survive. Over the past 17 years, the colonies have passed through 35,000 generations. In the process, they’ve become one of the clearest demonstrations that natural selection is real. All 12 colonies have evolved to the point at which the bacteria can replicate almost twice as fast as their ancestors. At the same time, the bacterial cells have gotten twice as big. Surprisingly, these changes didn’t unfold in a smooth, linear process. Instead, each colony evolved in sudden jerks, followed by hundreds of generations of little change, followed by more jerks.

Similar patterns occur in the evolution of digital organisms in Avida. So Lenski set up digital versions of his bacterial colonies and has been studying them ever since. He still marvels at the flexibility and speed of Avida, which not only allow him to alter experimental conditions with a few keystrokes but also to automatically record every mutation in every organism. “In an hour I can gather more information than we had been able to gather in years of working on bacteria,” Lenski says. “Avida just spits data at you.”

With this newfound power, the Avida team is putting Darwin to the test in a way that was previously unimaginable. Modern evolutionary biologists have a wealth of fossils to study, and they can compare the biochemistry and genes of living species. But they can’t look at every single generation and every single gene that separates a bird, for example, from its two-legged dinosaur ancestors. By contrast, Avida makes it possible to watch the random mutation and natural selection of digital organisms unfold over millions of generations. In the process, it is beginning to shed light on some of the biggest questions of evolution.

QUESTION #1: WHAT GOOD IS HALF AN EYE?

If life today is the result of evolution by natural selection, Darwin realized, then even the most complex systems in biology must have emerged gradually from simple precursors, like someone crossing a river using stepping-stones. But consider the human eye, which is made of many different parts—lens, iris, jelly, retina, optic nerve—and will not work if even one part is missing. If the eye evolved in a piecemeal fashion, how was it of any use to our ancestors? Darwin argued that even a simpler version of today’s eyes could have helped animals survive. Early eyes might have been nothing more than a patch of photosensitive cells that could tell an animal if it was in light or shadow. If that patch then evolved into a pit, it might also have been able to detect the direction of the light. Gradually, the eye could have taken on new functions, until at last it could produce full-blown images. Even today, you can find these sorts of proto-eyes in flatworms and other animals. Darwin declared that the belief that natural selection cannot produce a complex organ “can hardly be considered real.”

Digital organisms don’t have complex organs such as eyes, but they can process information in complex ways. In order to add two numbers together, for example, a digital organism needs to carry out a lot of simpler operations, such as reading the numbers and holding pieces of those numbers in its memory. Knock out the commands that let a digital organism do one of these simple operations and it may not be able to add. The Avida team realized that by watching a complex organism evolve, they might learn some lessons about how complexity evolves in general.

The researchers set up an experiment to document how one particularly complex operation evolved. The operation, known as equals, consists of comparing pairs of binary numbers, bit by bit, and recording whether each pair of digits is the same. It’s a standard operation found in software, but it’s not a simple one. The shortest equals program Ofria could write is 19 lines long. The chances that random mutations alone could produce it are about one in a thousand trillion trillion.

To test Darwin’s idea that complex systems evolve from simpler precursors, the Avida team set up rewards for simpler operations and bigger rewards for more complex ones. The researchers set up an experiment in which organisms replicate for 16,000 generations. They then repeated the experiment 50 times.

Avida beat the odds. In 23 of the 50 trials, evolution produced organisms that could carry out the equals operation. And when the researchers took away rewards for simpler operations, the organisms never evolved an equals program. “When we looked at the 23 tests, they were all done in completely different ways,” adds Ofria. He was reminded of how Darwin pointed out that many evolutionary paths can produce the same complex organ. A fly and an octopus can both produce an image with their eyes, but their eyes are dramatically different from ours. “Darwin was right on that—there are many different ways of evolving the same function,” says Ofria.

The Avida team then traced the genealogy leading from the first organism to each one that had evolved the equals routine. “The beauty of digital life is that you can watch it happen step by step,” says Adami. “In every step you would ordinarily never see there is a goal you’re going toward.” Indeed, the ancestors of the successful organisms sometimes suffered harmful mutations that made them reproduce at a slower rate. But mutations a few generations later sped them up again.

When the Avida team published their first results on the evolution of complexity in 2003, they were inundated with e-mails from creationists. Their work hit a nerve in the antievolution movement and hit it hard. A popular claim of creationists is that life shows signs of intelligent design, especially in its complexity. They argue that complex things could have never evolved, because they don’t work unless all their parts are in place. But as Adami points out, if creationists were right, then Avida wouldn’t be able to produce complex digital organisms. A digital organism may use 19 or more simple routines in order to carry out the equals operation. If you delete any of the routines, it can’t do the job. “What we show is that there are irreducibly complex things and they can evolve,” says Adami.

The Avida team makes their software freely available on the Internet, and creationists have downloaded it over and over again in hopes of finding a fatal flaw. While they’ve uncovered a few minor glitches, Ofria says they have yet to find anything serious. “We literally have an army of thousands of unpaid bug testers,” he says. “What more could you want?”

QUESTION #2: WHY DOES A FOREST HAVE MORE THAN ONE KIND OF PLANT?

When you walk into a forest, the first thing you see is diversity. Trees tower high overhead, ferns lurk down below, vines wander here and there like tangled snakes. Yet these trees, ferns, and vines are all plants, and as such, they all make a living in the same way, by catching sunlight. If one species was better than all the rest at catching sunlight, then you might expect it to outcompete the other plants and take over the forest. But it’s clear that evolution has taken a different course.

Figuring out why is a full-time job for a small army of biologists. A number of them seek enlightenment by comparing places that are rich and poor in species and trying to figure out the other things that make them different. One intriguing pattern has to do with food. Ecologists have found that the more energy a habitat can provide organisms, the more species it can support. But a habitat can get too productive. Then it supports fewer species. This pattern has emerged time and again in studies on ecosystems ranging from grasslands to Arctic tundra.

Until recently, a typical Avida experiment would end up with a single dominant organism. The Avida researchers suspected that was the result of providing an endless supply of food—in this case, numbers. Perhaps, they reasoned, if they put their digital organisms on a diet, they might evolve into different forms—just as it happens in nature. So the Avida team retooled their software to limit the supply of numbers flowing into their digital worlds. Then they made the numbers even more scarce by splitting them up into smaller supplies, each of which could be used only for a particular operation, such as adding two numbers. As the organisms used the numbers at a faster rate, they got a smaller benefit. And if too many organisms gorged themselves on one supply of numbers, they would stop replicating altogether.

The Avida team subsequently flooded some digital worlds with numbers and limited others to a scant supply, and the same pattern of diversity found in global ecosystems emerged. When the number supply was low, only one type of organism could survive. At intermediate levels, three or four different types emerged and coexisted. Each type evolved into a specialist at one or a few kinds of operations. But when the number supply got too abundant, diversity dropped to a single species again.

Bringing diversity into Avida has brought more bad news for those who think complexity cannot evolve. Ofria decided to run the complexity experiment over again, this time with a limit on the supply of numbers. “It just floored me,” he says. “I went back and checked this so many ways.” In the original experiment, the organisms evolved the equals routine in 23 out of 50 trials. But when the experiment was run with a limited supply of numbers, all the trials produced organisms that could carry out the equals routine. What’s more, they needed only a fifth of the time to do it.

Ofria suspects that the difference comes from the fact that several species are now evolving in the experiment rather than just one. More species mean more opportunities for success.

Question #3: Why Be Nice?

Human society depends on countless acts of cooperation and personal sacrifice. But that doesn’t make us unique. Consider Myxococcus xanthus, a species of bacteria that Lenski and his colleagues study. Myxococcus travels in giant swarms 100,000 strong, hunting down E. coli and other bacteria like wolves chasing moose. They kill their prey by spitting out antibiotics; then they spit out digestive enzymes that make the E. coli burst open. The swarm then feasts together on the remains. If the Myxococcus swarm senses that they’ve run out of prey to hunt, they gather together to form a stalk. The bacteria at the very top of the stalk turn into spores, which can be carried away by wind or water to another spot where they can start a new pack. Meanwhile, the individuals that formed the stalk die.

This sort of cooperation poses a major puzzle because it could be undermined by the evolution of cheaters. Some bacteria might feast on the prey killed by their swarm mates and avoid wasting their own energy making antibiotics or enzymes. Others might evolve ways of ensuring that they always end up becoming spores and never get left behind in the dead stalk. Such cheaters are not theoretical: Lenski and his colleagues have evolved them in their lab.

The Avida team is now trying to address the mystery of cooperation by creating new commands that will let organisms exchange packages of information. “Once we get them to communicate, can we get them to work together to solve a problem?” asks Ofria. “You can set up an information economy, where one organism can pay another one to do a computation for it.”

If digital organisms cooperate, Ofria thinks it may be possible to get them working together to solve real-world computing problems in the same way Myxococcus swarms attack their prey. “I think we’ll be able to solve much more complex problems, because we won’t have to know how to break them down. The organisms will have to figure it out for themselves,” says Ofria. “We could really change the face of a lot of computing.”

Question #4: Why Sex?

Birds do it, bees do it, and even fleas do it—but why they all do it is another matter. Reproduction is possible without sex. Bacteria and protozoa simply split in two. Some trees send shoots into the ground that sprout up as new trees. There are even lizard species that are all female. Their eggs don’t need sperm to start developing into healthy baby female lizards.

“One of the biggest questions in evolution is, why aren’t all organisms asexual?” says Adami. Given the obvious inefficiency of sex, evolutionary biologists suspect that it must confer some powerful advantage that makes it so common. But they have yet to come to a consensus about what that advantage is.

So Dusan Misevic, a biologist at Michigan State, has spent the past couple of years introducing sex into Avida. While digital sex may lack romance, it features the most important element from an evolutionary point of view: the genetic material from two parents gets mixed together in a child. When a digital organism makes a copy of itself, the copy doesn’t immediately take its own place in Avida and start reproducing. Instead, chunks of its code are swapped with the copy of another new organism. Only after this exchange do the two creatures start to reproduce.

In 1964 the German biologist H. J. Muller proposed that sex allows organisms to mix their genomes together in combinations that can overcome the effects of harmful mutations. Asexual organisms, on the other hand, are stuck with all the mutations their ancestors pass down to them. Over time, Muller argued, they can’t reproduce as quickly as their sexual competitors. Misevic designed an experiment to put Muller’s hypothesis to the test. “It’s a classic explanation, so it seemed like a good place to start,” he says.

Misevic created two kinds of worlds: one full of sexual digital organisms and the other full of asexuals. After they had evolved for tens of thousands of generations, he measured how fast they could replicate. “The overall conclusion we got was that, yes, there are some situations where sex is beneficial,” says Misevic. But there were surprises. Sex is good mainly as a way to escape annihilation from lethal mutations. But in Avida, sexual organisms had to pay a price for that insurance—they carried more nonlethal yet harmful mutations than the asexual organisms.

“We must look to other explanations to help explain sex in general,” says Misevic.

Question #5: What Does Life on Other Planets Look Like?

Life on Earth is based on DNA. But we can’t exclude the possibility that life could evolve from a completely different system of molecules. And that raises some worrying questions about the work going on these days to find signs of extraterrestrial life. NASA is funding a wide range of life-detecting instruments, from rovers that prowl across Mars to telescopes that will gaze at distant solar systems. They are looking for the signs of life that are produced on Earth. Some are looking for high levels of oxygen in the atmospheres of other planets. Others are looking for bits of DNA or fragments of cell walls. But if there’s non-DNA-based life out there, we might overlook it because it doesn’t fit our preconceptions.

“We can look at how known life-forms leave marks on their environment,” says Evan Dorn, a member of Chris Adami’s lab at Caltech, “but we can never make universal statements about them because we have only one example.”

Dorn says Avida is example number two. By finding patterns that are shared by life on Earth and life in Avida, he thinks he will be able to offer some ideas about how to look for life that the universe might be harboring.

Some researchers have suggested the best way to look for signs of life is to look for weird chemistry. Take the building blocks of proteins—amino acids—which are found on meteorites and can also be created in the lab simply by running an electric current through ammonia and other compounds. In a lifeless setting, the most common amino acid that results is the simplest: glycine. Some slightly less simple amino acids are also common, but all the larger ones make up only a trace or are missing altogether. That’s because it takes a lot of energy to make those big amino acids. “There’s a limited repertoire of chemistry in the absence of life,” says Dorn.

If you analyze a scoop of soil or pond water, however, you’ll find a completely different profile of amino acids. Life has evolved ways of building certain big amino acids, and when organisms die, those big amino acids float around in the environment.

What if life on another planet made compounds that were radically different from amino acids? Would it alter its planet’s chemistry in some similar way?

To test this idea, Dorn created a world devoid of life. Instead of containing a self-replicating program, each cell contained a random assortment of commands. All of the commands in the Avida language were present at equal levels. Here was the signature of a lifeless planet.

Then Dorn began dropping organisms into this world, like spores falling to Earth. At the beginning of the experiment, he set the mutation rate so high that no spore could replicate very long on the planet. (Think of Mars, where ultraviolet rays pelt the surface.) Gradually, he lowered the mutation rate until life could survive. “As soon as the environment was habitable, the organism took over and dominated the environment,” Dorn says.

As the digital organisms evolved to adapt to the world, Dorn found that some commands became rare and others became far more common. This distinctive signature stayed stable as long as life could survive on the planet. And no matter how many times Dorn repeated the experiment, the same signature of life appeared. Whether manipulating amino acids or computer commands, life does seem to leave the same mark. “It gives us a pretty strong indication that this process is universal,” says Dorn.

If Dorn is right, discovery of non-DNA life would become a little less spectacular because it would mean that we have already stumbled across it here on Earth—in East Lansing, Michigan.

Question #6: What Will Life on Earth Look Like In The Future?

One of the hallmarks of life is its ability to evolve around our best efforts to control it. Antibiotics, for example, were once considered a magic bullet that would eradicate infectious diseases. In just a few decades, bacteria have evolved an arsenal of defenses that make many antibiotics useless.

Ofria has been finding that digital organisms have a way of outwitting him as well. Not long ago, he decided to see what would happen if he stopped digital organisms from adapting. Whenever an organism mutated, he would run it through a special test to see whether the mutation was beneficial. If it was, he killed the organism off. “You’d think that would turn off any further adaptation,” he says. Instead, the digital organisms kept evolving. They learned to process information in new ways and were able to replicate faster. It took a while for Ofria to realize that they had tricked him. They had evolved a way to tell when Ofria was testing them by looking at the numbers he fed them. As soon as they recognized they were being tested, they stopped processing numbers. “If it was a test environment, they said, ‘Let’s play dead,’ ” says Ofria. “There’s this thing coming to kill them, and so they avoid it and go on with their lives.”

When Ofria describes these evolutionary surprises, admiration and ruefulness mix in his voice. “Here I am touting Avida as a wonderful system where you have full knowledge of everything and can control anything you want—except I can’t get them to stop adapting. Life will always find a way.”

Thinking about such adaptable creatures lurking on the Michigan State campus, furiously feeding on data, can be unsettling. Should the Avida team be working in quarantine? Lenski argues that Avida itself acts as a quarantine, because its organisms can exist only in its computer language. “They’re living in an alien world,” Lenski says. “They may be nasty predators from Mars, but they’d drop dead here.”

Still, Ofria acknowledges that harmful computer viruses may eventually evolve like his caged digital organisms. “Some day it’s going to happen, and it’s going to be scary,” Ofria says. “Better to study them now so we know how to deal with them.”

:cool:

[Hagakure]

i have always thought that evolution could be very cool on computers.

seen ghost in the shell? there is a bug in a covert computer virus which makes the program into a "living organism".

if these viruses of the future get very complex what will it take to make them self aware and what will they do when they are :D

[narayan]

IMHO using these digital organisms to train artificial neural networks is where the future of computing lies.

I find it it pretty cool how information is to these organisms as energy is to us.

[spacetrucker]

Hagakure What will it take to make a computer program self aware? Good question. How come we are aware? :confused: Unless we can discover how it is that consciousness rises from matter, we would still have no way to determine if it is aware, or if it just seems to be. I doubt any program running on any computer we know of could be aware. There is nothing which says computation has to take place in silicon. Forinstance say someone comes up with some amazing sophisticated proggy which seems to be aware. Then we go OK now lets run it on a computer made of wooden cogs, or pneumatic tubes with ping pong balls. This would be really slow obviously, but in principle there is no reason why you couldnt. So would it make sense to say the wooden cog computer is now aware?

I think it is the 'Hard AI' school of thought which says if u make a computer software complex enough it could become aware, and that mind is software running on the hardware which is the brain. John Searles' Chinese Room is a pretty convincing argument against this.

Its enough to make a scientist turn to god :D

[spacetrucker]

Narayan have u read any Rudy Rucker? He writes sci-fi about all sorts of AI and machine evolution. The ones I have read are called 'Wetware' and 'Software' and they are highly recommended if u are into this sort of thing. Also he writes alife software that u can download and run on your PC.

Rudy Ruckers Home Page

Greg Egan is good too (aussie writer I think)

Also there is tons of alife java applets u can find on the net, just search for alife java applet

[Hagakure]

i have another spooky one - also mentioned in a japanese cartoon (they cover a lot of nice philosophy).This is mentioned in S.E. Lain but is the work of some dude whose name i have forgotton but will check later.

bascically neurons are just billions of on and off messages acting in response to various stimuli triggering different pathways (dali lama mentioned possibility of these just being antenna picking up our thought but that may tie in later)

the number of humans on earth is reaching close to the number of neurons in a brain and our connectivity is constantly being upgraded via internet, TV, globalisation etc.

what if we are all single neurons in one big brain - a collective consciousness. scientists sometimes make exact same discoverys at opposite sides of earth due to similar stimuli.

so perhaps we are all making a big brain. but then again what if its just the big brain making us. our interactivity makes us follow a destined path. our actions are ttriggered by past actions and change future actions. if we somehow have freethought bearing this in mind we can try to make the world a better place. you do good things, the future will be better - your reincarnations are from the actions you chose. bad stuff happening to you now is due to the good and bad choices of others in the past.

the sooner we realise that we are all in this together, do good, and be happy the better.

or perhaps its late at night and my gnome is still feeling the wacky tobaccy :D

i will read this tomorrow and see.

as to whether computers will be self aware how self aware are we? our self awareness has arisen through natural selection and is the by-product of being more intelligent and able to out compete other life forms. surely this will be do-able on a powerfull enough computer.

[Braitok]

Did this experiment myself. Be warned. Digital life can exist. I proved it.

Anyone that wants the code, PM me.

[ 07. February 2005, 19:33: Message edited by: Puck ]

[spacetrucker]

A few years ago when I lived in a dark room with a computer I was quite into this and I wrote a bit of code which displays life like behaviour. These cellular automata systems I was tinkering with didn't try and model life as such (genetics etc), but rather provide a generic system where local rules interact to produce an emergent complex behaviour.

Conways life algorithm is the classic cellular automata example, and it is quite amazing the diversity of 'life forms' ( examples )which emerge from a simple system.

One proggy I made allows the user to explore the space of all possible 2 state 9 neighbour CA universes (2^512 rules) using a sort of genetic algorithm. You would start with a random rule which would determine how the system would evolve. Then you could flip a random bit in the rule and see how it affected the system. If the mutated rule produced less interesting behaviour than the previous rule then you could 'undo' the mutation and try a different one (the mutated one didnt survive). Otherwise just mutate again. After iterating through this process a bit, you could create some weird systems, like stuff which looks like fire spreading through a forest, or bacteria in a petri dish

Also it can be fun to hook these systems up to a softsynth to make music (noise)

Nowadays I prefer the real thing

Oh yeah if anyone wants the code they can PM me too, its CBuilder C++ code (or I just send a win32 exe if u just want to play .

[Braitok]

I like the 'universal noise' idea - you've just given me an idea for another project I've been considering.

[devance]

http://www.io.com/life/

A fun visual computer life program.