Artificial Life Platforms

In 1990, Thomas Ray placed a single hand-written program of 80 machine instructions into a block of computer memory. The program did one thing: it found its own beginning and end, asked for a new block of memory, and copied itself into it. Copies were made with occasional errors. Nothing scored the copies, and no fitness function existed. Within a few million executed instructions the memory held programs that were too short to copy themselves and borrowed the copying code of their neighbors. Later came programs that resisted the borrowers, and programs that hijacked them (Ray, 1991).

The course description for CSC 742 lists, alongside genetic algorithms and their use in search and optimization, "artificial life and the use of evolutionary computation in robotics". This article covers the first half of that phrase: platforms in which digital organisms replicate, mutate and compete, so that evolution happens as a consequence of the system's rules rather than as an optimization loop run by the experimenter. The second half is the subject of evolutionary robotics.

Optimization and artificial life

An evolutionary algorithm used as an optimizer has an outer loop that the designer writes: evaluate every individual with a fitness function, select parents according to the scores, create offspring, and repeat (see what is evolutionary computation). The fitness function states what is wanted, and the run ends when a good enough solution appears.

Artificial life platforms remove that loop. Individuals copy themselves using their own code, and whatever copies itself faster or more reliably, given the other individuals present, becomes more common. Selection is still at work, but the measure of success is reproduction itself, and it depends on the rest of the population. Ray (1991) gave a working definition of life for this purpose: a system is living if it is self-replicating and capable of open-ended evolution, and synthetic life "should self-replicate, and evolve structures or processes that were not designed-in or preconceived by the creator". His stated aim was to synthesize life rather than to simulate it. The question these systems are built to answer is not how to find a good solution but what an evolutionary process produces when nobody has said what a good solution is.

Tierra

The virtual computer

Tierra runs its organisms on a virtual computer designed for evolution (Ray, 1991). Its machine language has 32 instructions and no numeric operands, so every instruction fits in five bits and a mutated instruction is still a valid instruction. Jumps and calls do not use numeric addresses. A JMP is followed by a short pattern of no-operation instructions of two kinds, NOP-0 and NOP-1, and the processor searches nearby memory for the complementary pattern and jumps there; Ray called this addressing by template, by analogy with how molecules bind to complementary shapes. A mutation that changes a template therefore changes where control goes, without breaking the instruction set.

The whole instruction set fits in a table. It is listed in Ray (1991, Appendix B) with a one-line comment for each instruction; the grouping here is ours:

The CPU has four registers (ax and bx for addresses, cx and dx for numbers), a ten-word stack and an instruction pointer (Ray, 1991, Appendix A). There are no constants: the only way to get the number 4 into a register is to build it, zero, or1, shl, shl, which is exactly how the ancestor begins.

The memory, called the soup, held 60,000 instructions in most of Ray's runs. Each organism has exclusive write access to its own block of memory and to one daughter block it allocates when it reproduces. Read and execute access are not protected: an organism can examine and run the code of its neighbors but cannot overwrite it. Ray called this a semi-permeable membrane.

Three operating-system services complete the world:

• The slicer gives each organism's virtual CPU a small slice of real CPU time in turn. The slice is proportional to the organism's size raised to a power; a power of one is size-neutral, and other powers select for larger or smaller organisms.
• The reaper kills organisms once memory fills to a set level, such as 80 percent. Newborns enter the bottom of a queue and the reaper kills from the top. An organism moves up the queue when one of its instructions causes an error, and moves down when it successfully executes certain instructions that are hard to execute without error, so flawed programs die sooner and the probability of death generally rises with age.
• Mutation comes from background bit flips anywhere in the soup (about one per 10,000 instructions executed), bit flips during copying (about one per 1,000 to 2,500 instructions copied), and instructions that occasionally give a result off by one.

The ancestor and its descendants

The ancestor is 80 instructions long, and 48 of them are no-ops used as templates: groups of four mark its beginning and end, its copy procedure and its loops. It finds its two end templates, subtracts their addresses to get its size, allocates a daughter block of that size, calls its copy procedure, and divides. Its first replication takes 839 instructions. The soup fills with about 375 copies after roughly 400,000 executed instructions, the reaper starts, and evolution begins (Ray, 1991).

The ancestor, traced

Ray (1991, Appendix C) lists the ancestor instruction by instruction, with its opcode and a comment. Typed into a small interpreter of our own (tools/experiments/evolution/tierra_ancestor.py), which implements the instructions as Ray's comments describe them, it copies itself exactly, and it takes 839 instructions to its first divide and 813 for each later replication, the counts Ray reports. The interpreter matches those counts only under one convention, that an instruction such as adrb does not skip the template written after it, which then runs as four no-ops; skipping the template gives 827 and 809. The ancestor's program, in its own address space of 0 to 79, runs as follows:

Nothing in the program refers to an absolute address. The beginning, the end, the copy procedure and both loops are found by searching for complementary templates, so the same code runs unchanged wherever in the soup a daughter happens to be placed. Of the 813 instructions in a later replication, 798 are spent in the copy loop (addresses 47 to 66), about ten per instruction copied; allocating, calling, dividing and jumping back cost the other 15.

The first parasite follows from this design with one bit flip. The copy procedure's template at 40–43 is 1 1 0 0. Flipping the low-order bit of instruction 42 makes it 1 1 1 0, the same pattern as the end template. Run in the interpreter, the mutant's adrf now stops at the first 1 1 1 0 it meets, at 40, and the mutant computes its size as 45, the number Ray gives. Its daughter, the first 45 instructions, has lost the copy procedure. Run alone, its call finds no 1 1 0 0 template anywhere and nothing is copied. Placed in memory right after an intact ancestor, its call finds the host's template 1 1 0 0, executes the host's copy procedure (host addresses 44 to 74) with its own registers, and produces an exact copy of itself, 489 instructions after it starts. That is the informational parasitism Ray describes: the parasite does not damage the host's code, it borrows it.

Ray traced, by genotype, a sequence of ecological relationships:

• Parasites. The one-bit mutant traced above measures itself as 45 instructions long, and its daughter, genotype 0045aaa, lacks the copy procedure and cannot replicate alone. Placed among intact organisms, it finds the copy template in a neighbor, within a search limit of a few hundred instructions, and executes the neighbor's copy code to copy itself. Ray calls these obligate parasites that harm their hosts only as competitors. They typically appear within the first few million instructions of a run.
• Immunity and its circumvention. Some 79-instruction genotypes resist the parasite: when 0045aaa is placed between two of them, it reproduces briefly and is then eliminated, whereas with the ancestor it coexists in a stable cycle. Soups dominated by these immune types were occasionally invaded by 51-instruction parasites that had evolved a way around the immunity.
• Hyper-parasites. Genotype 0080gai differs from the ancestor by 19 instructions and can replicate on its own. Two changes let it exploit parasites. Its copy procedure jumps back into its reproduction loop instead of returning, so a parasite that calls it never gets its instruction pointer back. And after each copy it re-examines itself, writing its own location and size into the CPU registers. A parasite's CPU that has passed through this code holds the hyper-parasite's location and size, and from then on copies the hyper-parasite's genome instead of its own. In Ray's runs hyper-parasites drove the parasites to extinction.
• Sociality and cheating. The resulting communities were relatively uniform genetically, and in them social hyper-parasites of 61 instructions evolved. They jump back to a template at the end of the preceding organism, so they replicate only when a similar organism sits just before them in memory. They are 24 percent smaller than the ancestor, partly because their templates shrank from four instructions to three. Their cooperation was then exploited by cheaters, hyper-hyper-parasites such as the 27-instruction 0027aab, which sit between social organisms and capture the instruction pointer as it is passed along.

Ray also reports a lineage that dropped its end template entirely: it located its beginning and a template in its middle, subtracted to get half its size, and doubled the result by a left shift. Over longer runs, selection for small size produced a proliferation of small parasites, and in one run with selection for large size, genomes grew past 23,000 instructions (Ray, 1991). Lehman and colleagues (2020), with Ray among the authors, add that he had expected to spend perhaps years tinkering before anything interesting happened, and that Tierra produced complex ecologies the first time it ran without crashing.

The sequence of parasite, immunity, circumvention and hyper-parasite is a coevolutionary arms race of the kind discussed in competitive coevolution and Red Queen dynamics, with the difference that no one designed the competition. Lehman and colleagues (2020) report that Ray called the process a bit-string race.

Avida

From Tierra to Avida

Avida began in 1993, when Charles Ofria and C. Titus Brown joined Chris Adami, who had been using Tierra to study adaptation. Adami wanted organisms to evolve to perform computations, and rewarded them with extra CPU time when they did (Ofria and Wilke, 2004). Avida's self-copying organisms run an assembly-like language inspired by Tierra's, with several changes:

• Each organism runs on its own virtual CPU, and the CPUs are executed effectively in parallel. An organism's merit sets how fast its CPU runs relative to others.
• Organisms live in the cells of a fixed-size world, often a two-dimensional grid in which a newborn replaces an organism in a neighboring cell. Space is the resource they compete for.
• In most Avida experiments organisms cannot read or write each other's genomes, so Tierra-style parasites cannot form, although an experimenter can enable them.
• The environment rewards organisms for performing tasks: computations on numbers read from the environment. A task increases merit, which buys more CPU time and therefore faster replication (Ofria and Wilke, 2004).

The reward for tasks looks like a fitness function, and in a sense it is one: the experimenter chooses what to reward. It differs from an optimizer's fitness function in where it acts. It changes the rate at which organisms run their own replication code, and reproduction still happens only through that code. Lehman and colleagues (2020) report two surprises from Avida: in one experiment organisms learned to recognize a test environment and stop replicating in it (described in the surprising creativity of digital evolution), and in another, a mutation that put a second copy instruction into an odd-length organism's copy loop let the loop run past the end of the genome and copy the whole genome again, doubling its length.

The evolutionary origin of complex features

The best-known Avida experiment asked how a complex feature can evolve when no single mutation can produce it (Lenski et al., 2003). Organisms could earn energy by performing nine one- and two-input bitwise logic functions on 32-bit numbers. The only logic instruction available was nand, so every function had to be built from nand instructions coordinated with input and output instructions. The reward for each function was $2^n$, where $n$ is the minimum number of nand operations needed to perform it, and the rewards for different functions multiplied. Symmetric variants, such as $A \lor \lnot B$ and $\lnot A \lor B$, counted as the same function:

EQU, which outputs 1 in every bit position where its two inputs agree, is the most complex. The script tools/experiments/evolution/nand_costs.py confirms the column of minimum costs by exhaustive search over straight-line NAND circuits of up to six gates: NOT and NAND need one gate, AND and OR_N two, OR and AND_N three, NOR and XOR four, and EQU five.

Each population started from 3,600 copies of a 50-instruction ancestor that could replicate but perform no logic function, and evolved for 100,000 updates, about 15,873 ancestral generations. Point mutations occurred at 0.0025 per instruction copied, and single-instruction insertions and deletions each at 0.05 per genome copied. The main results (Lenski et al., 2003):

• EQU evolved in 23 of 50 populations in the environment that rewarded all nine functions.
• It never evolved when only EQU was rewarded. None of 50 populations evolved it, even though those populations tested more genotypes on average (about $2.15 \times 10^7$ against $1.22 \times 10^7$), because their smaller genomes replicated faster. Simpler functions were needed as stepping stones, but no particular one was: in 36 environments that each removed the reward for one or two simpler functions, EQU still evolved in at least one population each, and in 124 of 360 populations overall.
• Many routes led to the same function. By a knockout analysis, the first EQU-performing genotypes needed between 17 and 43 instructions for it, with a median of 28, and the mutations that first produced EQU included point mutations, insertions, a small duplication and deletions.
• Some steps went downhill. In the case-study population, the mutation immediately before the origin of EQU knocked out the NAND function and cut fitness by more than half, yet reversing it in the first EQU-performing genotype destroyed EQU. Across the 23 populations, 5 of the mutations one step before the EQU-producing one were deleterious when they occurred, and reverting them eliminated EQU in 3 cases.

The authors conclude that complex functions can originate by random mutation and natural selection, building on simpler functions that are themselves favored. The result connects to fitness landscapes: the line of descent to EQU was not a steady climb, and crossing a valley was part of the route in some populations. Our reading of the result for optimization is the familiar argument for partial credit: a target with no intermediate rewards gave selection nothing to act on.

Lenia

Tierra and Avida evolve programs. A different branch of artificial life studies patterns in cellular automata, starting from Conway's Game of Life, whose discrete cells and simple local rule produce gliders and other moving structures. Lenia (Chan, 2019) makes every part of such a system continuous. The state $A_t(x)$ of each site is a real number in $[0, 1]$. Each site's neighborhood is weighted by a smooth kernel $K$, typically ring-shaped, giving a potential $U_t = K * A_t$ (a convolution). A growth function maps the potential to a value between $-1$ and $1$; in its exponential form,

$$G(u; \mu, \sigma) = 2 \exp\!\left(-\frac{(u - \mu)^2}{2\sigma^2}\right) - 1,$$

which is positive when the potential is near the growth center $\mu$ and negative elsewhere. Each step adds a small fraction $\Delta t$ of the growth and clips the result:

$$A_{t + \Delta t}(x) = \min\!\Big(\max\big(A_t(x) + \Delta t \, G(U_t(x)),\ 0\big),\ 1\Big).$$

With suitable $\mu$ and $\sigma$ (for example $\mu = 0.15$, $\sigma = 0.016$ for the glider-like pattern Chan named Orbium), the system supports smooth, self-organizing patterns that move and recover from perturbation. Chan (2019) reports more than 400 such "species" in 18 families, cataloged with a biological-style taxonomy.

Lenia's relation to evolutionary computation runs the other way from Tierra's. Its patterns do not reproduce, and the 2019 paper lists self-replication as not yet discovered. The species were found largely by interactive evolutionary computation: a person mutates parameters or patterns and selects promising results by eye, because, as Chan notes, recognizing a new lifeform is hard to automate. The human is the fitness function, as in Picbreeder (see CPPNs and HyperNEAT).

Open-endedness as a research problem

Tierra's early runs produced a burst of novelty, and both Tierra and Avida remain productive research tools. Whether any artificial system can keep producing novelty the way the biosphere does is an open question. Stanley, Lehman and Soros (2017) call open-endedness, a single process that keeps inventing new and more complex things indefinitely, the last grand challenge most people have never heard of, and say that no existing algorithm suggests "even a hint" of natural evolution's endless creative potential. They point to algorithms that drop or weaken the objective, such as novelty search and minimal criterion coevolution, as steps toward it; novelty search and its relatives are covered in MAP-Elites and novelty search.

Part of the difficulty is saying precisely what open-endedness is. Packard and colleagues (2019), introducing two special issues of Artificial Life on the subject, start from a list produced at an earlier workshop at York that distinguished the ongoing generation of new adaptations, new kinds of entities, major transitions and the evolution of evolvability from ongoing growth in the complexity of entities and of their interactions. They note that these categories overlap, and propose a simpler working list of four kinds of ongoing generation: interesting new kinds of entities and interactions, evolution of evolvability, major transitions, and semantic evolution. They describe the list as provisional, say the authors reached no consensus on the best categorization, and point out that the word "interesting" makes the first category vague and subjective. One contribution they discuss illustrates why: a very simple system generates new entities forever, but the new entities are statistically the same as the old ones, a diversity the editors call trivial. They also report that indefinitely scalable complexity, a capacity for complexity that grows with the size and duration of the world, has come to be treated as a necessary condition.

In our view these questions apply directly to evolutionary computation used as optimization. A run with a fixed fitness function is designed to converge, and every mechanism for maintaining diversity, from niching to speciation to quality-diversity archives, is a partial answer to the problem that open-endedness research poses in its general form.

Artificial life and robotics

The two halves of the course description meet in evolved bodies. Sims evolved the morphology and control of virtual creatures together in a physics simulation, and creatures evolved for competition are discussed in competitive coevolution. The same lineage leads to soft robots and to the course's final project, coevolving soft robots with NEAT. Evolutionary robotics has a chapter of its own in the course textbook (Eiben and Smith, 2015, ch. 17), and the artificial life platforms explain much of what makes it difficult: an evolved controller exploits the simulator it is evaluated in, much as Avida organisms exploited their test environment, and the surprising creativity of digital evolution collects many such cases.

References

• Chan, B. W.-C. (2019). Lenia: biology of artificial life. Complex Systems, 28(3), 251–286.
• Eiben, A. E., and Smith, J. E. (2015). Introduction to Evolutionary Computing, 2nd ed., chapter 17. Springer.
• Lehman, J., Clune, J., Misevic, D., Adami, C., Altenberg, L., et al. (2020). The surprising creativity of digital evolution: a collection of anecdotes from the evolutionary computation and artificial life research communities. Artificial Life, 26(2), 274–306.
• Lenski, R. E., Ofria, C., Pennock, R. T., and Adami, C. (2003). The evolutionary origin of complex features. Nature, 423(6936), 139–144.
• Ofria, C., and Wilke, C. O. (2004). Avida: a software platform for research in computational evolutionary biology. Artificial Life, 10(2), 191–229.
• Packard, N., Bedau, M. A., Channon, A., Ikegami, T., Rasmussen, S., Stanley, K. O., and Taylor, T. (2019). An overview of open-ended evolution: editorial introduction to the Open-Ended Evolution II special issue. Artificial Life, 25(2), 93–103.
• Ray, T. S. (1991). An approach to the synthesis of life. In C. G. Langton, C. Taylor, J. D. Farmer, and S. Rasmussen (eds.), Artificial Life II, Santa Fe Institute Studies in the Sciences of Complexity X, 371–408. Addison-Wesley.
• Stanley, K. O., Lehman, J., and Soros, L. (2017). Open-endedness: the last grand challenge you've never heard of. O'Reilly Radar, 19 December 2017.