TERA Introduction: Once upon a time a professor decided to try to simulate evolution on a

Master Index Current Directory Index Go to SkepticTank Go to Human Rights activist Keith Henson Go to Scientology cult

Skeptic Tank!

TERA Introduction: Once upon a time a professor decided to try to simulate evolution on a computer. He set up a block of memory and a language so that programs could copy themselves. He set things up so that the programs would "die" (be deleted) after a while, and they would "mutate" (bits would occasionally flip). He seeded to memory with an 80-line program that could copy itself, and let it run overnight. He thought it might be possible to "evolve" a 76-line reproducer, and he wanted to see how long it would take. The next morning, he had a *22-line* reproducer. He had parasites that stole time from other programs. He had "immune" hosts. He had groups of cooperating programs. He had, in a word, an "ecology," overnight. *Not* a science fiction story. The professor's name is Thomas Ray, and the experiment was conducted in 1990. (Note: My name is Ray Ingles. The professor under discussion is Thomas Ray. Obviously we are no relation, and to avoid confusion I can assure you that there is no reference to myself anywhere other than here. "Ray" = "Prof. Thomas Ray" in this post.) Try to read the whole thing; I promise, it's interesting. But you might want to skip to "Results" and come back to the technical discussion later. Outline: I. Artificial Life in General A. What is it? B. Why do it? II. The Tierra Simulator A. Language B. Soup C. Slicer D. Reaper E. Mutation III. Results A. Species B. Ecology IV. Future Goals I. Artificial Life in General A. What is it? Artificial life is, broadly speaking, the attempt to imitate or synthesize life based on either "natural" components of life (e.g. amino acids) or in different media (e.g. as computer programs). Ranging from the mathematical game LIFE (references, anyone?) to attempts like the Tierra simulator to attempts to make self-replicating chemical systems and eventually cells, this field has a relatively short but exciting (scientific) history. The Tierra simulator attempts to synthesize life in the form of self-replicating and evolving computer programs which, analogously to organic life which competes for energy and resources, compete for CPU time and memory space. Prof. Ray defines life, for his purposes, as something "self-replicating, and capable of open-ended evolution."[1] B. Why do it? The hope is that we can "learn by doing;" that is, we can learn essential properties of living systems by making our own. Computer- based systems are great for this, since we can study the system without disturbing it, we can make comparative runs, and we can vary parameters at will. Prof. Ray has som other ideas, as well, which will be discussed in "Future Goals." II. The Tierra Simulator The Tierra simulator attempts to imitate the conditions necessary for life and evolution. Programs are to be able to copy themselves, die off, and mutate. It is a "virtual computer"; that is, the program makes one computer "pretend" to be another. This way, the programs cannot escape and run wild; they will be seen as merely text-style data to any real computer. A. Language The problem with all computing languages to date, evolution-wise, is that they are "brittle"; that is, the ratio of functional programs to possible programs is virtually zero. As anyone who's programmed can tell you, even one change in one letter of a program will cause it to do something wrong, assuming it runs at all. To get around this, Ray designed the Tierran language to have a truly small instruction set of 32 operators, *operands included.* The emphasis is important; even RISC processors with few instructions take numeric operands, and thus the number of possible instructions is on the order of (assuming a 32-bit word size) 2^32. The second change from traditional languages is the idea of "address by template." When protein A is to interact with protien B, it doesn't have to know *where* B is; it presents a surface that interacts with B and lets B interface with it. Similarly, the programs are labeled with templates. The sequence "JUMP NOP_0 NOP_O NOP_0 NOP_1" will seek out another place in the program where the complement "NOP_1 NOP_1 NOP_1 NOP_0" appears, and execute from there. The rest of the instructions are fairly standard commands that move things from register to register, add registers, copy from one address to another, increment registers, etc. B. The "Soup" The programs "live" in a block of memory 60,000 instructions in size (each instruction is five bits long, so the total number of bits is 300,000), called the "soup." When a program "dies," the memory is deallocated to the program and any other program can acess the meory, but the actual code of the program is not erased. C. The Slicer Tierra imperfectly emulates a parallel computer of the MIMD (Multiple Instruction, Multiple Data) type. Each program is given a "virtual CPU" and is allowed a slice of real CPU time in turn. The slice is some constant amount of time, which can be adjusted by certain factors. If you make slice time proportional to program size, for example, so that bigger programs get more time, then larger programs will be selected for. D. The Reaper The reaper is a routine that starts deleting programs as soon as the soup is 80% full. When a new program is created, it is put on a linear queue. The reaper deallocates whatever is on the top of the queue. If a program has an error in execution, it moves up the queue, as long as whichever program is in front has fewer errors. If two particularly difficult instructions are executed without error, then the program moves down the queue. This way, fundamentally flawed programs tend to die off quickly, and successful programs stick around for a while. No program is immortal, however, so after a while only programs that copy themselves will be present. D. Mutations A routine simulates the effect of "cosmic rays" by randomly flipping bits in the soup. The factor works out to about 1 bit flipped per 10,000 instructions executed. Also, bits are flipped during the copying phase of reproduction, at a rate of about one bit flipped per 2,000 lines copied. Finally, the "virtual CPUs" are not perfect. Every so often they improperly execute an instruction. All of these effects proceed on a random basis to prevent periodic effects. Not all of this is necessary for "genetic" change. Some programs are sloppy reproducers and wind up incorporating other programs' code into their own copies, leading to new programs appearing. III. Results, or, "Fine, But What Does it all Do?" The Tierra simulator was fantastically successful, far beyond even its creator's expectations. Novel programs emerged, and in at least one case a type of algorithm emerged which Prof. Ray himself was not familiar with, i.e. new algorithms were invented that were not "programmed in" at the start. A. "Species" that have emerged: Several reproductive strategies have evolved during Tierra runs: 1. Copying As noted in the introduction, the original Tierran "ancestor" was 80 lines long. In the course of "evolution" a new program 22 lines long has emerged, far shorter than Ray thought possible. This is, counting in number of instructions executed per copy, a 5.75-fold improvement in efficiency. Of course, other programs of varying lengths (up to 23,000 in one instance) are represented. 2. Parasitism Some programs emerge which do not contain the copying loop in their code. To reproduce, they must locate and execute the code of another program which does contain this code. The advantage to this is that the parasites are shorter in length and hence can copy themselves faster. 3. Immunity A 57-line program (among others) has emerged which has proven immune to the simpler parasites. It is obviously not as efficient as the 22-line program, but it outcompetes the 22-liner when parasites are present. 4. Circumvention of Immunity As the title indicates, more complicated parasites are able to "get around" this immunity. 5. "Hyper-parasitism" Some programs essentially "trick" the parasite into copying their own code rather than the parasite's code. In this manner the hyper- parasite gets to copy more than once per code execution, since the parasite is helping them out. 6. Social Hyper-parasitism In some runs, hyper-parasites drive the parasites into extinction, and thus a large number of very-closely-related programs emerge, which according to standard theory is just right for producing social behavior. This is exactly what happens. The hyper-parasites work together, executing each other's code. This enables them to be somewhat shorter than the noncooperating variety. 7. Cheating Standard theory also predicts cheating, and in fact "cheaters" emerge which trick the social h.p.'s into copying the cheater's code. 8. "Unrolling the Loop" After a particularly long run of 15 billion instructions, a program was identified that used the programming optimization technique of "unrolling the loop." Whenever a loop is executed, you have the code which does something useful and the overhead which keeps track of the loop and jumps to the beginning to repeat. By making multiple copies of the useful code inside the loop, you can reduce the overhead of jumping around. The price is longer code, but an equilibrium point can be reached. Interestingly, Ray himself when he programmed Tierra was not familiar with this technique. Also, it's one of those features that seem to require a lot of simultaneous mutations to occur, but there it is. (Creationists take note!) As Ray writes, "...the code includes a classic mix of apparent intelligent design, and the chaotic hand of evolution. The optimization technique is a very clever one invented by humans, yet it is implemented in a mixed-up but functional style that no human would use (unless perhaps very intoxicated)." [1] The organism is 36 lines long, and packs a much more complicated algorithm in less than half the space of the 80-line ancestor. B. "Ecology" 1. "Predator/prey cycles" When the soup is seeded with various organisms, obvious cycles closely analogous to biological predator/prey cycles emerge. As in nature, these can be chaotic, periodic, or can spiral or rapidly approach an equilibrium. 2. "Keystone" effect In ecology, the "keystone predator" effect is where a new predator introduced to an ecology leads to increased diversiy of life in that ecology. This has been observed in Tierra; however the mechanism seems different from the postulated one in ecology. In ecology it is thought (but difficult to measure) the the new predator tends to attack the previous dominant species prefentially, but the increase in diversity occurs in Tierra though the "predator" hunts indiscriminately. 3. "Punctuated equilibrium" In many runs, the evolution seems to proceed in terms of periods of stasis puntuated by abrupt change. Generally, periods last from 178 million to 1.44 billion instructions executed, then, in the space of 1 or 2 million instructions, the past equlibrium changes, and new "organisms" emerge and old patterns of reproduction change. IV. Future Goals A. Diploidy and Sex Prof. Ray is attempting to set Tierra up for diploid (two sets of "genes") organisms and hopefully sexual reproduction. B. Multicellular Models of Parallel Programming It is hoped that Tierran-style systems with "multicellularity" where programs cooperate on a common goal could lead to new ideas in parallel programming. C. A "Cambrian Explosion" Prof. Ray is attemting to set things up so as to imitate the "Cambrian Explosion" where single-celled life seemed to burst into multicellular life in the fossil record. D. Commercial Prospect: "Genetic Engineering?" "What if we set up artfificial selection for some program function?" Ray asks. Then we could hope that the competition and optimization already seen could lead to new, efficient algorithms for applications. This might be enhanced by "inserting" application code into "wild" programs first. [1] Amazing, huh? The complete Tierra source code in portable C is available by anonymous FTP at: tierra.slhs.udel.edu or: life.slhs.udel.edu [1] Also available there is an operator's manual for Tierra and the draft of a paper from which I took all my quotes and most of my data, in the files "tierra1.tex" and "tierra2.tex." Other references are in that paper, or, for a non-technical exploration of Tierra: Science News, vol. 140 #6 or vol 160 #4. (Sorry, it's not here and I can't remeber for sure.) Sincerely, Ray Ingles || The above opinions are probably || not those of the University of ingles@caen.engin.umich.edu || Michigan. Yet.


E-Mail Fredric L. Rice / The Skeptic Tank