announce.30

地球模拟器

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:

Boston University, Computational Sciences Center, December 3, 1991
MIT Nanotechnology Study Group, December 3, 1991
Bolt Beranek and Newman Inc. (BBN), December 5, 1991
University of Massachusetts Boston, Biology, December 5, 1991
Yale University, Biology, December 6, 1991
Apple Computer, California, February 27, 1992
University of Arizona, Ecology & Evolutionary Biology, March 10, 1992
Santa Fe Institute, Workshop on Adaptive Computation, March 10-15, 1992
Cornell University, Mathematical Sciences Institute, CA Workshop, May 1992
General Motors, Sigma Xi, Warren, MI, May 1992
Summer School on Environmental Dynamics, Istituto Veneto Di Scienze, Lettere
     Ed Arti, Venice, Italy, June 1-7, 1992
Gordon Conference on Theoretical Biology, New Hampshire, June 9-12, 1992

6) 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
                        [e-mail]
                         302-451-2281 (FAX)
                            302-451-2753