Copy Link
Add to Bookmark
Report
Alife Digest Number 066
Alife Digest, Number 066
Tuesday, November 5th 1991
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~ Artificial Life Distribution List ~
~ ~
~ All submissions for distribution to: alife@cognet.ucla.edu ~
~ All list subscriber additions, deletions, or administrative details to: ~
~ alife-request@cognet.ucla.edu ~
~ All software, tech reports to Alife depository through ~
~ anonymous ftp at polaris.cognet.ucla.edu in ~ftp/pub/alife ~
~ ~
~ List maintainers: Liane Gabora and Rob Collins ~
~ Artificial Life Research Group, UCLA ~
~ ~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Today's Topics:
Calendar of Alife-related Events
AI/AL Techniques Applied to Economics
Tierra Update
Answer on Rosen's paradox
----------------------------------------------------------------------
Date: Tue, 5 Nov 91 18:47:30 -0800
From: liane@cs.ucla.edu (Liane Gabora)
Subject: Calendar of Alife-related Events
**********************************************************************
CALENDAR OF ALIFE-RELATED ACTIVITIES:
First European Conference on Artificial Life Dec 11-13, 1991
Canadian AI Conference, Vancouver May 11-15, 1992
Artificial Life III, Santa Fe June 15-19, 1992
10th National Conference on AI, San Jose Jul 12-17, 1992
ECAI 92, 10th European Conference on AI Aug 3-7, 1992
Parallel Problem Solving from Nature, Brussels Sep 28-30, 1992
(Send announcements of other activities to alife@cognet.ucla.edu)
**********************************************************************
------------------------------
Date: Wed, 16 Oct 1991 08:52:31 -0400 (EDT)
From: Leslie Burkholder <lb0q+@andrew.cmu.edu>
Subject: AI/AL Techniques Applied to Economics
>I am interested in references and names for work broadly in the
>area of AI techniques applied to economics. To narrow this down, I am
>interested in AI as a tool for developing alternative models of economic
>behaviour than the traditional view of man as a perfectly informed calculating
>machine!
You might be interested in software we are working on. It allows you to
author a proxy agent that will choose on your behalf against other proxy
agents in games such as iterated PDs. The proxy agents are finite state
machines. This already limits their computational abilities. But what is
more important is that you can now ask, in a fairly obvious way, what
happens when you impose limits of various kinds on the allowable proxy
agents. For example: Suppose the proxy agents can have no more than 2
states, what then is the most successful agent for a 2-player iterated
chicken game?
The program also includes a GA for evolving new agents from those you
and other people have authored. These new agents can be limited in their
computational abilities as well.
Leslie Burkholder
Carnegie Mellon University
------------------------------
Date: Mon, 28 Oct 91 23:28:11 EST
From: Super-User <root@life.slhs.udel.edu>
Subject: Tierra Update
TIERRA UPDATE:
(Source release, abstract, publications, lectures, new results)
This message contains:
1) Announcement of release of Tierra source code
2) Abstract describing Tierra
3) List of related publications and upcoming lectures
4) Some interesting new and unpublished results
1) Announcement of release of Tierra source code
We are releasing the source now, although it is under rapid development
and major improvements are only days away. If you use the software, be sure
to pick up new versions soon from the ftp site. The source in the ftp site
will be replace on a roughly weekly basis.
The complete source code for the Tierra simulator is
available by anonymous ftp at:
tierra.slhs.udel.edu [128.175.41.34] and
life.slhs.udel.edu [128.175.41.33]
in the directory /tierra.
to get it, ftp to tierra or life, log in as user "anonymous" and give your
real name (eg. tom@udel.edu) as a password.
then give the command `cd tierra', to get a list of files type `dir'.
you will see the following files:
README.T1 A detailed description of tierra and how to use it.
README.T2 in two parts
Part01 the source code in shar format
... in seven parts
Part07
announce this announcement
tierra1.tex Parts 1 & 2 of a manuscript describing Tierra,
tierra2.tex in LaTeX format.
The shar files contain the README files, so if you want the source code,
you don't need to copy README separately. To unpack the shar files, use
`unshar', or `sh'.
The version released includes significant contributions from
Tom Uffner, Dan Pirone and Marc Cygnus. The software remains copyrighted
("all rights reserved"), and is not being placed in the public domain.
However, it will be made available free of charge and may be freely
distributed. The intent is that it not be used for profit making activities
unless some royalty arrangement is entered into with the authors.
A DOS version of the Tierra software with a decent frontend will be ready
for sale ($70) by November.
2) Abstract describing Tierra
**** BEGIN ABSTRACT ****
Synthetic organisms have been created based on a computer metaphor of
organic life in which CPU time is the ``energy'' resource and memory is
the ``material'' resource. Memory is organized into informational
patterns that exploit CPU time for self-replication. Mutation generates
new forms, and evolution proceeds by natural selection as different
genotypes compete for CPU time and memory space.
Observation of nature shows that evolution by natural selection is
capable of both optimization and creativity. Artificial models of evolution
have demonstrated the optimizing ability of evolution, as exemplified by
the field of genetic algorithms. The creative aspects of evolution have been
more elusive to model. The difficulty derives in part from a tendency of
models to specify the meaning of the ``genome'' of the evolving entities,
precluding new meanings from emerging. I will present a natural model of
evolution demonstrating both optimization and creativity, in which the
genome consists of sequences of executable machine code.
>From a single rudimentary ancestral ``creature'',
very quickly there evolve parasites, which are not able to replicate in
isolation because they lack a large portion of the genome. However, these
parasites search for the missing information, and if they locate it in a
nearby creature, parasitize the information from the neighboring genome,
thereby effecting their own replication.
In some runs, hosts evolve immunity to attack by parasites.
When immune hosts appear, they often increase in frequency, devastating the
parasite populations. In some runs where the community comes to be
dominated by immune hosts, parasites evolve that are resistant to immunity.
Hosts sometimes evolve a response to parasites that goes beyond immunity,
to actual (facultative) hyper-parasitism. The hyper-parasite deceives the
parasite causing the parasite to devote its energetic resources to replication
of the hyper-parastie genome. This drives the parasites to extinction.
Evolving in the absence of parasites, hyper-parasites completely dominate
the community, resulting in a relatively uniform community characterize by
a high degree of relationship between individuals. Under these circumstances,
sociality evolves, in the form of creatures which can only replicate in
aggregations.
The cooperative behavior of the social hyper-parasites makes them vulnerable
to a new class of parasites. These cheaters, hyper-hyper-parasites, insert
themselves between cooperating social individuals, deceiving the social
creatures, causing them to replicate the genomes of the cheaters.
The only genetic change imposed on the simulator is
random bit flips in the machine code of the creatures. However, it turns
out that parasites are very sloppy replicators. They cause significant
recombination and rearrangement of the genomes. This spontaneous sexuality
is a powerful force for evolutionary change in the system.
One of the most interesting aspects of this instance of life is
that the bulk of the evolution is based on adaptation to the biotic
environment rather than the physical environment. It is co-evolution
that drives the system.
**** END ABSTRACT ****
3) List of related publications and upcoming lectures
The recent publicity about my work (Technology Review, April 1991;
Science News, August 10, 1991; New York Times, August 27, 1991; Computerworld
September 30, 1991) has generated a lot of interest. I wanted to list the
relevant publications, and also the upcoming seminars.
Ray, T. S. 1991. ``Is it alive, or is it GA?''
Proceedings of the 1991 International Conference on Genetic Algorithms,
Eds. Belew, R. K., and L. B. Booker, San Mateo, CA: Morgan Kaufmann, 527--534.
Ray, T. S. 1991. ``An approach to the synthesis of life.''
Artificial Life II, Santa Fe Institute Studies in the Sciences of
Complexity, vol. XI, Eds. C. Langton, C. Taylor, J. D. Farmer, & S. Rasmussen,
Redwood City, CA: Addison-Wesley, 371--408.
Ray, T. S. 1991. ``Population dynamics of digital organisms.''
Artificial Life II Video Proceedings, Ed. C. G. Langton,
Redwood City, CA: Addison Wesley.
Ray, T. S. 1991. ``Evolution and optimization of digital organisms.''
Scientific Excellence in Supercomputing: The IBM 1990 Contest Prize Papers,
Eds. Keith R. Billingsley, Ed Derohanes, Hilton Brown, III.
Athens, GA, 30602, The Baldwin Press, The University of Georgia.
Publication date: December 1991.
I will be at the Santa Fe Institute Feb. 1 thru Aug. 31, 1992.
This work will also be presented in the following upcoming seminars:
University of Maryland, Zoology, October 29, 1991
University of Kentucky, Lexington, Biology, October 31, 1991
University of Delaware, Entomology, November 5, 1991
Stony Brook, Department of Ecology and Evolution, November 6, 1991
Drexel University, Electrical Engineering, November 8, 1991
The University of the Arts, Philadelphia, Design in Cyberspace lectures,
November 12, 1991
IBM, T. J. Watson Research Center, Yorktown Heights, NY, November 13, 1991
Thinking Machines Corp., Cambridge, November 14, 1991
Digital Equipment Corp., Hudson, MA, November 15, 1991
American Society of Information Science, New Jersey, November 19, 1991
Texas Instruments, Dallas, November 21, 1991
Harvard University, Biology (Lewontin's lab), December 2, 1991
Boston University, Computational Sciences Center, December 3, 1991
MIT Nanotechnology Study Group, December 3, 1991
University of Massachusetts Boston, Biology, December 5, 1991
Yale University, Biology, December 6, 1991
University of Arizona, Ecology & Evolutionary Biology, March 10, 1992
Cornell University, Mathematical Sciences Institute, CA Workshop, May 1992
Gordon Conference on Theoretical Biology, New Hampshire, June 8--12, 1992
4) Some interesting new and unpublished results
Below is a report of an interesting result that is not described in
any of the publications listed above:
A COMPLEX ADAPTATION
The adaptation described below is a classic example of intricate design in
evolution. One wonders how it could have arisen through random bit flips,
as every component of the code must be in place in order for the algorithm
to function. Yet 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).
The arms race described in the manuscripts took place over a period of
a billion instructions executed by the system. Another run was allowed to
continue for fifteen billion instructions, but was not examined in detail.
A creature present at the end of the run was examined and found to have
evolved an intricate adaptation. The adaptation is an optimization technique
known as ``unrolling the loop''.
The central loop of the copy procedure performs the following operations:
1) copies an instruction from the mother to the daughter, 2) decrements the
cx register which initially contains the size of the parent genome, 3) tests
to see if cx is equal to zero, if so it exits the loop, if not it remains
in the loop, 4) increments the ax register which contains the address in the
daughter where the next instruction will be copied to, 5) increments the
bx register which contains the address in the mother where the next instruction
will be copied from, 6) jumps back to the top of the loop.
The work of the loop is contained in steps 1, 2, 4 and 5. Steps 3 and 6 are
overhead. The efficiency of the loop can be increased by duplicating the
work steps within the loop, thereby saving on overhead. The creature from
the end of the long run had repeated the work steps three times within the
loop, as illustrated below.
The unrolled loop is an example of the ability of evolution to produce an
increase in complexity, gradually over a long period of time. The interesting
thing about the loop unrolling optimization technique is that it requires more
complex code. The resulting creature has a genome size of 36, compared to its
ancestor of size 80, yet it has packed a much more complex algorithm into less
than half the space.
Below I include the assembler code for the central copy loop of the ancestor
(80aaa) and decendant after fifteen billion instructions (72etq). Within
the loop, the ancestor does each of the following operations once: copy
instruction (51), decrement cx (52), increment ax (59) and increment bx (60).
The decendant performs each of the following operations three times within
the loop: copy instruction (15, 22, 26), increment ax (20, 24, 31) and
increment bx (21, 25, 32). The decrement cx operation occurs five times
within the loop (16, 17, 19, 23, 27). Instruction 28 flips the low order
bit of the cx register. Whenever this latter instruction is reached, the
value of the low order bit is one, so this amounts to a sixth instance of
decrement cx. This means that there are two decrements for every increment.
The reason for this is related to another adaptation of this creature. When
it calculates its size, it shifts left (12) before allocating space for the
daughter (13). This has the effect of allocating twice as much space as
is actually needed to accomodate the genome. The genome of the creature
is 36 instructions long, but it allocates a space of 72 instructions.
This occurred in an environment where the slice size was set equal to the
size of the cell. In this way the creatures were able to garner twice as
much energy. However, they had to compliment this change by doubling the
number of decrements in the loop.
nop_1 ; 01 47 copy loop template COPY LOOP OF 80AAA
nop_0 ; 00 48 copy loop template
nop_1 ; 01 49 copy loop template
nop_0 ; 00 50 copy loop template
mov_iab ; 1a 51 move contents of [bx] to [ax] (copy instruction)
dec_c ; 0a 52 decrement cx
if_cz ; 05 53 if cx = 0 perform next instruction, otherwise skip it
jmp ; 14 54 jump to template below (copy procedure exit)
nop_0 ; 00 55 copy procedure exit compliment
nop_1 ; 01 56 copy procedure exit compliment
nop_0 ; 00 57 copy procedure exit compliment
nop_0 ; 00 58 copy procedure exit compliment
inc_a ; 08 59 increment ax (point to next instruction of daughter)
inc_b ; 09 60 increment bx (point to next instruction of mother)
jmp ; 14 61 jump to template below (copy loop)
nop_0 ; 00 62 copy loop compliment
nop_1 ; 01 63 copy loop compliment
nop_0 ; 00 64 copy loop compliment
nop_1 ; 01 65 copy loop compliment (10 instructions executed per loop)
shl ; 000 03 12 shift left cx COPY LOOP OF 72ETQ
mal ; 000 1e 13 allocate daughter cell
nop_0 ; 000 00 14 top of loop
mov_iab ; 000 1a 15 copy instruction
dec_c ; 000 0a 16 decrement cx
dec_c ; 000 0a 17 decrement cx
jmpb ; 000 15 18 junk
dec_c ; 000 0a 19 decrement cx
inc_a ; 000 08 20 increment ax
inc_b ; 000 09 21 increment bx
mov_iab ; 000 1a 22 copy instruction
dec_c ; 000 0a 23 decrement cx
inc_a ; 000 08 24 increment ax
inc_b ; 000 09 25 increment bx
mov_iab ; 000 1a 26 copy instruction
dec_c ; 000 0a 27 decrement cx
or1 ; 000 02 28 flip low order bit of cx
if_cz ; 000 05 29 if cx == 0 do next instruction
ret ; 000 17 30 exit loop
inc_a ; 000 08 31 increment ax
inc_b ; 000 09 32 increment bx
jmpb ; 000 15 33 go to top of loop (6 instructions per copy)
nop_1 ; 000 01 34 bottom of loop (18 instructions executed per loop)
Tom Ray
University of Delaware
School of Life & Health Sciences
Newark, Delaware 19716
ray@tierra.slhs.udel.edu
ray@life.slhs.udel.edu
ray@brahms.udel.edu
302-451-2281 (FAX)
302-451-2753
------------------------------
Date: Thu, 24 Oct 91 17:07:06 +0100
From: ctika01@mailserv.zdv.uni-tuebingen.de (G. Kampis)
Subject: Answer on Rosen's paradox
On Sun, Oct 13 Barry Mc Mullin asked about Rosen's paradox.
Rosen is right, of course. In my recent book
"Self-Modifying Systems in Biology and Cognitive Science", Pergamon,
Oxford 1991, pp 543, I have a whole chapter on SR machines. It gives you
the detailed argument and an explanation of why it is correct (my
explanation, that is). You get an *almost* complete list of references
too.
Also of interest are two papers by Lars Lofgren:
Lfgren, L. 1968: An Axiomatic Explanation of Complete Self-
Reproduction, Bull.Math.Biophys. 30, 415-425.
Lfgren, L. 1977: Complexity of Decriptions of Systems: A Foundational
Study, Int.J.General Systems 3, 197-214.
He says Rosen is right but axiomatic complete self-reproduction is
nevertheless possible by an EXTENSION of set theory. In ther words,
complete SR cannot be incorporated in ordinary mathematics but is
consistent with it. He point out ordinary math has to be supplanted with
an atomic self referential element. Incidentally, as is well known, this
latter is exactly what Varela has achieved in his
Varela, F.J. 1974: A Calculus for Self-Reference, Int.J.General Systems
2, 5-24.
without being concerned with SR at all! Hence, we have a relationship
between complete SR and "autonomy" as conceived in autopoiesis, a
connection for which I have to refer, again, to my book.
If you don't want to buy the book, check out these:
Kampis, G. and Cs nyi, V. 1987a: Replication in Abstract and Natural
Systems, BioSystems 20, 143-152.
Kampis, G. and Cs nyi, V. 1991: Life, Replication and Information:
Beyond the Machine Metaphor, J.Theor.Biol. 148, 17-32.
Viel Spass.
George Kampis kampis@mailserv.zdv.uni-tuebingen.de
h1201kam@ella.hu
------------------------------
End of ALife Digest
*******************
