From: ingles@engin.umich.edu (Ray Ingles)
Subject: Yes, Virginia, Mutation is Enough (long!)
Date: Sat, 26 Sep 92 13:28:23 EDT
Organization: University of Michigan Engineering, Ann Arbor
Summary: Here's another line of evidence that mutation + net. sel. can
Keywords: artificial life, Tierra


Tag: Richard Harter

 This is a repost of something I put up a while back. Since the notion
has come up again that mutation and natural selection 'just are'
insufficient to account for the complexity we see around us, I thought
it might be worth it.

------------------Begin Repost---------------------------------------
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.

 (Note: I describe below where it is possible to get portable-C code
 for Tierra via anonymous ftp. It's worth it, trust me.)

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 some 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_0 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
access 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 possible 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 (over 23,000 lines 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 punctuated 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 file "tierra.tex" (it's 48 pages, but *very* informative). 

 Other references are in that paper, or, for a non-technical exploration
of Tierra:

 Science News, vol. 140 #6.

Sincerely,

Ray Ingles                  || The above opinions are probably
                            || not those of the University of
ingles@engin.umich.edu      || Michigan. Yet.


Newsgroups: talk.origins