Digital Darwin

An anonymous reader writes "Using genetic algorithms to breed strings of computer code graphically, this week's Nature magazine describes results from Caltech and Michigan State. Their program is Avida. While they mainly mimic mutation, not genetic cross-over [or inheritance (thus wiping away much memory of initial conditions)], their simulations show how a short-term backward step in survival strategies can generate innovative advances. It is not unlike running a maze which necessarily involves testing alot of dead-ends, and thus shares the graphical look of Conway's classic Game of Life." Here's a National Geographic story about this as well, or see their press release.

Comments

I've used genetic algorithms

[sstory]

And I wish everyone could see them at work. It's really kind of breathtaking how stumbling around in the parameter space, and filtering the bad missteps, can mimic the results of engineering. I think the minor problem of the small number of noisy anti-evolutionists would become even more minor. I mean, it's kind of hard to say that an algorithm doesn't work when you can compile a few thousand lines of c and then watch it work.

Re:I've used genetic algorithms

[jdevers77]

That makes the assumption that the anti-evolutionists are logical people. I would say that the many thousands of undisputable cases of evolution around us every day would also make them shut up, but it doesn't. Maybe when they are infected with antibiotic resistant Staph they will think about it from a different perspective...

Re: I've used genetic algorithms

[Black Parrot]

> I think the minor problem of the small number of noisy anti-evolutionists would become even more minor. I mean, it's kind of hard to say that an algorithm doesn't work when you can compile a few thousand lines of c and then watch it work.

Yeah, as soon as I saw the article I thought, "How many evolution deniers will we dredge up this time?".

It would be nice if someone had an on-line hub linking to all the GAs that are free and source-available, so that people could download one and try it themselves, look at the code if they suspected the answer was cheated in, and maybe tweak some parameters to see that both mutation and selection are actually needed for such systems to work. (The evolution deniers on talk.origins are fond of attacking mutation and selection independently, as if one or the other should be sufficient according to the theory of evolution.)

Of course, some puppies would deny peeing on the floor even as you rubbed their nose in it, but we might as well inform those who are informable on matters of science.

Re: I've used genetic algorithms

[aborchers]

I enter the fray reluctantly.

The first thought I had when I saw the article (presented on Space.com as "Darwin Proved Right ...") was that simulating something in a computer does not necessarily prove anything about the physical world. We can synthesize all sorts of things that have no analogy in nature. EA, AI, are fascinating fields inspired by evolutionary theory, but I fail to see how executing a computer program that assumes evolution in its infrastructure proves anything but that modelling evolution in software works.

For the record, I am not anti-evolution, though I may occassionally be noisy...

Re:I've used genetic algorithms

[drooling-dog]

Indeed. Given the way that genetic inheritance works -- e.g., with mutation, crossover recombination, etc. -- you could argue that evolution is a matter of mathematical necessity. But faith always trumps reason with the creationists, and so it's usually an exercise in exasperation to debate the issue, no matter how solid your arguments are. They will refuse to comprehend them as a point of principle.

I've done some GA work myself, and it is quite fascinating. E.g., too high a mutation rate and the system destabilizes, but too low a rate and it never (or very slowly) finds its optimum fitness. Throw in some genetic recombination (simulating sexual reproduction) and evolution to higher mean levels of fitness accelerates considerably as useful "genes" are conserved while others quickly disappear. It's very cool.

Modern creationists are in the same place that official Christiandom was in the time of Galileo, I think. If you're religious, nothing in modern biology (which largely is evolution) really denies a role for a deity in kickstarting the whole shebang. Setting up the system to run itself unattended, in fact, would have been the smart way to do it. Those who insist that God would create a system far inferior to this -- i.e., that requires endless hand-tweaking of every minute detail -- are really delivering Him a kind of insult, aren't they?

Re:I've used genetic algorithms

[greg_barton]

That makes the assumption that the anti-evolutionists are logical people.

Very true. And, in the case of using genetic algorithms as a point of evidence in an argument, this assumption works against you. For many people computers are a black box. If you say, "I have a computer program that models mysterious process X" it's just replacing something mysterious with something incomprehensible.

And, before you do that, you have to assume that arguing is a productive activity in the first place. With many evolution deniers, it is not. But since they've wandered into my cave (the realm of logical, rational thought) I find it's my duty to eat them alive. :)

Re: I've used genetic algorithms

[Dr. Wonz]

I was looking at GAs for a solution in a n parameter system in chemistry.

Here's a nice collection of links and source codes I found back then: The Genetic Algorithm Archive

Re:I've used genetic algorithms

[gillbates]

Modern creationists are in the same place that official Christiandom was in the time of Galileo, I think. If you're religious, nothing in modern biology (which largely is evolution) really denies a role for a deity in kickstarting the whole shebang. Setting up the system to run itself unattended, in fact, would have been the smart way to do it. Those who insist that God would create a system far inferior to this -- i.e., that requires endless hand-tweaking of every minute detail -- are really delivering Him a kind of insult, aren't they?

A point seemingly lost on a lot of right-wing fundamentalists. When you study religion, you notice certain trends, and one of these trends is that the oldest and most well established religions don't ask their believers to deny their intellectual capacities. The problem with "creation scientists" is the same problem with "evolutionary biologists" - each firmly believes in their position regardless of the weakness of the position or evidence to the contrary.

Weak minds often have a hard time with the intelligent design arguments of creation. While we don't specifically deny evolution, we posit that there was a Creator who started the process, and has and does attend to his creation. When one looks at the complexity of living things compared to that of inanimate objects, one can't help but be struck by the difference in complexity between what merely exists and those things that grow.

Interestingly, while this study can show the merits of evolution, it does more to bolster the intelligent design theory than to destroy it. While the experiment was very interesting, we must remember that the digital organisms did have an intelligent designer - it's not like the programs sprang to life on their own!

Re: I've used genetic algorithms

[Black Parrot]

> The problem with "creation scientists" is the same problem with "evolutionary biologists" - each firmly believes in their position regardless of the weakness of the position or evidence to the contrary.

Could I trouble you to summarize the weakness of the position of evolutionary biologists and the contrary evidence? Presumably you have something beyond the same old tripe that has been refuted hundreds of times, or you wouldn't be saying that.

> Weak minds often have a hard time with the intelligent design arguments of creation. While we don't specifically deny evolution, we posit that there was a Creator who started the process, and has and does attend to his creation.

And that position is completely worthless as a way of understanding the universe, because it is compatible with any observation whatsoever.

> When one looks at the complexity of living things compared to that of inanimate objects, one can't help but be struck by the difference in complexity between what merely exists and those things that grow.

What measure of complexity are you using? I'd like to see your calculations showing the complexity of a squirrel and the complexity of the Nile delta.

But maybe before we get into that too deeply... What has complexity got to do with anything? Are you making an underlying claim that complexity can only come about as a result of intelligent design? Is the Nile delta the result of intelligent design? Are intelligent designers the result of intelligent design? (Where did the first intelligent designer come from?)

> Interestingly, while this study can show the merits of evolution, it does more to bolster the intelligent design theory than to destroy it. While the experiment was very interesting, we must remember that the digital organisms did have an intelligent designer - it's not like the programs sprang to life on their own!

Yes, and our simulations of continental drift are written by humans too. Are we to conclude that humans are pushing the continents around?

Study up on the concept of "non sequitur" when you have a little spare time.

Re:I've used genetic algorithms

[NialScorva]

"We discover a new virus all the time, but one thing remains the same, it's still a virus."

Except this is a purely linguistic definition, not corresponding to anything in nature, and explicitely shows the flaw in the majority of creationist thinking: The name *is* the thing. "Kind" is a completely useless word. I've seen it equated to "species", and then I've seen a creatist backed so far into a corner that there was a "bacteria kind", "plant kind", and "fungus kind". The only common definition for "kind" is that humans must occupy an excusive niche, it seems.

There is more diversity in viruses than there is between a human and any other mammal, yet they're all the same "kind" to because it's convenient and removed from daily experience.

Re:I've used genetic algorithms

[kirkjobsluder]

Micro-evolution doesn't produce new organs, make a reptile into a mammal or a fish into an amphibian. It doesn't mean that one day a reptile happen to be born with feathers so it was a bird. It's a small variation of what's already there. A change in color or size perhaps, or for example in turtles, the shape of a water turtles' feet are good for swimming while a land turtle's feet are good for walking.

I don't know why I bother because this is too easy. One of the facts that best support evolution is that there are no truely new organs. A brain is just overgrown ganglia. A scale is just a slightly modified form of skin. A feather and hair are just slightly modified scales. mammary glands are slightly modified sweat glands. In fact, the development of a truely different, truely new organ with no developmental ties to other previously existing organ systems would be clear evidence of design. So far, all the evidence is that if there is a designer, it works in ways that produce effects identical to evolution.

But what is amazing is that we have examples of such transformations forwards and backwards. We have arthropods that became land animals and later, insects that recolonized the water. We have amphibians that came to shore and reptiles, mammals and birds that went back to sea.

What Macro-evolution doesn't explain is species that can not advance without certain features, for example the giraffe. The giraffe has a very long neck, which is designed not only to reach tall trees, but also so that the giraffe can bend down and drink without his brain being gorged with blood and exploding. The giraffe has a very powerful heart for getting blood up its long neck, but when he bends down to drink blood is going very powerfully downhill with the added force of gravity. There is a spongy tissue around his brain that holds blood until he is done drinking, and, valvues in his blood vessles to keep more blood from coming into his head. If these things were not in place in the first species of giraffe at the dawn of time, the first species of giraffe would have died as a result of too much blood going to his head and there would simply be no more giraffes. Yet according to Macro-evolution it took a long amount of time for these complex things to develope. Were there ever short neck giraffes? Could be, but, would they be designed in such a way? These things are specifically designed for an animal with a very long neck. The powerful heart would kill a short neck giraffe. He'd die of high blood preasure, yet if the first long necked giraffe was born without a strong heart, it would have died from not having enough blood to its brain. So how did this complex animal come to be? There are many different species such as this that defy the theory of Macro-evolution, species with features that have to be in place in their full form for the species to simply exist and advance because without them they will simply die.

Of course, knowing a bit about what you are talking about would help quite a bit. The question to be thrown back is why can't these features develop in tandem through gradual incremental changes? Like most people who don't know a lick about evolution, you assume that one characteristic must have appeared first suddenly, leaving the other characteristics to radically catch up. This view is perhaps the fault of biology educators who over-emphasize the role of mutation in evolution and under-emphasize the role of diversity within populations. For a start while the problem of blood pressure regulation is more accute for giraffes, it is not unique to giraffes. Most of the features cited as essential to girafes are present to some degree in all mammals (the basic creationist problem of no original organs again). And in fact, we have short-necked giraffes (Okapi) in the present day that, amazingly enough show many of the adaptations cited as unique for giraffes.

But there are many other features of giraffes that make them bad candidates for design. For example, giraf

Tierra, Avida, MS - a short story

[freality]

Tierra was by Tom Ray, a pioneer in the AL field. It was a great idea, but failed to turn around with interesting biodiversity. You'd create creatures, they'd optimize themselves, some variants and parasites would evolve, but then things would simmer down within a few hours and you'd be in a steady state for ever.

Network Tierra was Ray's response to this. It was supposed to allow a "Cambrian explosion" of biodiversity, by providing tons of (networked computer) space for the little creatures to explode into, and then specialize, in. This led to interesting migration behavior, and one of my all-time favorite web-pages, but it too failed to spark that je ne sais quois, that spark of life.

Anyways, it did spark Avida and the Digital Life Lab at Cal Tech. Avida is essentially a deeper look at the fundamentals behind AL. In Tierra, I think the design philosophy was something like "make it look a lot like a living ecological system and the life-force will appear out of the ether", and actually, Tierra was a great leap forward beyond more mundane genetic programming a la John Koza.

Avida, on the other hand, is much more systematic in exploring the parameter space (which is large and sensitive) for setting up an AL system. This turned out to be fruitful, as Adami found that only when certain, very narrow, environmental conditions were met would the little creatures start outsmarting that Creationist boogeyman, the Second Law of Thermodynamics.

Turns out that Tierra didn't have spatiality (needed to be more restrictive on who could sleep with who) and mutation rates (some power law math that's way over my head) set right.

But the real punch-line to this whole story is that the direct beneficiary of these insights in Microsoft! Hah!

Microsoft was funding Adami's work because Windoze crashed too much. They were searching for a way of programming - in this case using closed instruction sets like Avida's (another deep topic) - that would be inherently robust to problems like seg faults and illegal instructions.... e.g. Adami's instruction set was engineered so that little programs (creatures) couldn't crash the Avida VM when they mutated into new, unknown programs.. or in Windoze's case, when a coder did something stoopid. It's funny that MS was researching this, since releatively low-tech solutions such as protected memory and QA take care of this. (not to mention Java ;)

Interesting but sort of scary

[PotatoHead]

technique that has always made me think.

I read a magazine article about this a while back. (probably Sci Am.)

One researcher setup a problem to be solved with an analog circut. The problem was to distinguish between the words yes and no.

Nobody can explain how the circut that evolved actually works. Like us, there were parts of the circut that seemed redundant or unnecessary. Sort of like the appendix.

This whole thing makes me wonder just what we don't know that we think we do.

Good Intro Resources on ALife/Complexity

[sbot5000]

1) Thomas S. Ray is a great starting point

Especially: Evolution, Ecology and Optimization of Digital Organisms and Zen and the Art of Creating Life

2)The Santa Fe Institute

3)Kevin Kelly's Out of Control: The New Biology of Machines, Social Systems and the Economic World

Computer Evolution

[jefu]

I've worked with various kinds of things related to genetic algorithms and its a wonderful field and very interesting to work in.

Its wonderful how these things can find odd and interesting solutions to problems in some cases and completely miss them in others.

One of the things that anyone learns who has tried this kind of method is that you can't hurry things to a result - that you often need to actively intervene to slow the evolutionary march, or even back it up (as in the article) or the system can easily get stuck exploring an area with a local optimimum extensively and miss a better one thats just a ways away.

Wonderfully fun stuff though and well worth investigating.

Brain vs genetic alogrithms

[ProfitElijah]

their simulations show how a short-term backward step in survival strategies can generate innovative advances.

This isn't really a challenging assertion, and is well discusssed in evolutionary psychological circles. Consider any given genetic setback. In order for the organism suffering this set back not to be disadvantaged, it must develop a mechanism which compensates for the setback at least as much as the organism is disadvantaged. Simple statistics will show that any solution which is at least as good as another solution is probably better. Because unless it is exactly as good, it is better, and the range of better solutions is much wider than the range of exactly as good solutions. So you don't need this study to show you that, you just need your highly genetically evolved brain.

forget the anti-evolution argument

[gol]

having just successfully completed an undergraduate project in which i have used genetic algorithms to achieve full adaptive image compression, i have learnt rather a lot about these curious beasts that is seldom mentioned in modern text. the use of genetic algorithms in a computer does in no way prove or disprove any evloution/anti-evolution argument. these algorithms do not magically evolve new creatures, or new solutions. they just search the solution space in a highly parallel manner, and they surprise people because they come up with solutions they did not consider. the solution is there waiting in solution space - but you can't find it because your brain is not capapble, you don't spend enough time on it... whatever. this is not new, its not intelligent, its not the creation of a new species. think of genetic algorithms as exploiting adaptive characteristics, simple as that, i.e. skin colour changing due to intensity of sunlight. of course... there are fields of research that involve using one class of genetic algorithms to derive the schemata (structure) of another class, but the research has come up with nothing to date.

Frank and Stein

[Tablizer]

It's alive, IT'S ALIVE!.....damn, it chewed up my paycheck.

evolution is dumb

[Anonymous Coward]

There is really nothing particularly amazing about evolutionary or genetic algorithms. They just try a bunch of stuff until they find something that works. In general, they are terribly inefficient algorithms.

The only reason evolution has been able to come up with amazing results like human life is the immense computing capability of the natural world. One gram of hydrogen has 6.02 x 10^23 atoms. Even if you could represent each of those atoms with one bit of information, we are nowhere near being able to track all of those atoms on a computer. Even a Terabyte of memory is less than 10^13 bits. This doesn't even begin to consider the 36 x 10^46 pairwise forces between the atoms. The computing power of the earth is immensely more than anything that we will ever attain in von neumann style computers.

When you start to consider the astronomical number of chemical reactions that occur continously on the earth, it makes sense that even a dumb algorithm like evolution could come up with some pretty amazing stuff. Add to this the multitude of other planets in the universe and intelligent life almost seems inevitable. Assume the universe is infinite, and intelligent life _is_ inevitable (every configuration of matter occurs with probability 1).

Re:Darwin t-shirts

[ikewillis]

Oh wow, that's certain to offend any Christians in the audience...

Genetic Images: Evolvo; Sims SIGGRAPH 10 years ago

[JacobKreutzfeld]

Evolvo is a cool program which does genetic images: http://sourceforge.net/projects/evolvo/

It's based on Karl Sims work, which I saw presented about 10 years ago at SIGGRAPH. His page is at http://www.genarts.com/karl/

I tried implementing something in LISP then C based on Sims' work way back but got stuck; I'm glad evolvo has emerged so I can actually play with it.

Where to get Avida

[IdahoEv]

For the record, I'm one of Dr. Adami's grad students in (The Digital Life Lab) at Caltech. Most of the programming is done at our sister lab in Michigan.

We recently released Avida version 2.0, with a new GUI and complete with god mode where you can inspect and edit the genome of any organism at any point.

We encourage you to play with Avida yourself. You can get information and a Mac OS X binary at:

Avida's Hompeage. Older versions for linux and windows are available there as well.

The intrepid can build the current version for OS X or Linux from source, please see Avida's Sourceforge Project. If you want the nice GUI, you'll need QT.

Other information about Avida, our lab's research, and artificial life in general can be found at:

The Digital Life Lab Homepage

Our sister lab at MSU, run by Professors Charles Ofria and Richard Lenski.

The Int'l Society For Artificial Life

Re:Where to get Avida

[mercere99]

To add one more comment to this (from the Michigan lab mentioned above) we'll have a Windows version of the software out "real soon now". Just this past week we've gotten everything compiled under Visual C++, and are hammering out the last few major bugs. We'll put up a beta as soon as its reasonably solid.

Re:The article fails at validating evolution...

[mercere99]

Actually, this is incorrect. We started with simple digital organisms that were only capable of self-replication, and put them in an environment where they would get more CPU time (basically have their priority increased) if they performed certain mathematical computations, in this case bitwise boolean logic operations.

The organisms were only given a nand instruction to work with, and combinations of nands (linked together carefully with proper juggling of data) could be used to create any of the others. The equals operation (returns 1 where bits in the two sequences are the same, 0 where they differ) seems to require at least 19 instructions to perform. Its important to note that we did not reward partials solutions -- they either got the correct answer of they didn't.

For those interested, we also have a lot of our data related to the paper on our servers, http://myxo.css.msu.edu/papers/nature2003

Charles Ofria (Second author of the paper, and primary author of the software)

a practical application - antenna design

[drwho]

A couple of years ago, Richard Formato (WW1RF) released Yagi Genetic Optimizer, the third edition of his software for using genetic algorithms for antenna design. This stuff does really work, and is useful. It's freeware, but for ms-dos, here