ECAL session notes: Digital Evolution
As before, what follow is a very slightly cleaned up version of the notes I took during the second ISAL summer school session at ECAL 2017. Also as before, note that this is very rough, made while I was reviewing them tonight. Apologies for any typos or other mistakes.
Charles Ofria, Michigan State University
Before the talk started there was a bit of discussion about the previous talk, on historical and philosophical perspectives on artificial life - specifically on the conclusions reached about Tierra in the last talk, with which this speaker somewhat disagreed. In the previous session it was concluded that Tierra does not go on to confirm the arrow of complexity hypothesis because plenty of programs in that simulation became smaller rather than growing. However, Charles Ofria points out that apparently if you add more “good” factors than just speed of reproduction, the programs do grow. But, as I also wondered in the last talk, does a larger program size really indicate a greater “complexity”?
Anyway, to move on to the actual talk:
The more the speaker learned about AI the more he realized “true” AI was 10-20 years away…like it has always been and is now.
Evolution is hard to study. Living organisms:
- Reproduce slowly - you have to wait real time for generations to go by, but the dynamics you’re looking for can take tens of thousands of generations
- Can be easily influenced - eg what if the organism notices you? Does that change anything?
- Are fragile. Observing something can kill it.
- Interact at many levels. Eg leafcutter ants have different roles - guards, medics, gatherers. These can be difficult to pick apart.
- Can be too unwieldy for statistically powerful replication. If something happens once, you have an existence proof, but you can’t necessarily repro it.
What can we do to overcome these challenges? If we could study this in a computer, the above problems all become more manageable (but not necessarily completely avoidable)
What are digital organisms?
Digital Organisms are computer programs that self-replicate and can evolve to thrive in a noisy computational environment. Some properties/benefits:
- rapid generations
- completely observable
- easy to scale up experiments
- potential for open-ended evolution?
If we want to learn about evolution as a process we need an open-ended evolving system where organisms can interact and alter their environments.
The notion of “digital organisms” came from PC game “Core War”. Players are programmers who write code and put it in memory of a PC (nowadays virtual). Programs try to shut each other off. The last program standing wins.
One of the really consistent approaches to Core War was to write a program that made a copy of itself first, and then did whatever else it was going to do. This way if you get shut off you have copies to continue the fight. It was sort of reminiscent of living organisms, but an issue with Core War was that there was no source of variation in the system. You do not observe any kind of evolution.
In 1990, Steen Rasmussen built VENUS. With VENUS, aka Core Worlds, he was able to see stable, cooperative code structures arise, but no proper self-replication. Core Worlds was similar to Core War, but added mutations into the system. Self replicators would break down because of the mutations. A broken organism would start writing all over the place in memory and killing everything around it.
In 1991, Tom Ray designed Tierra. It based on Core War but with mutations as a source of variation. He made digital organisms write protected so they couldn’t just write over each other. So you could no longer trivially kill each other as in Core World.
- Alphabet size of 32
- Ancestor with length of 80
- Ancestor looks for a specific pattern in its own beginning (eg NOT 0, NOT 1). Thus it now knows where in memory it started.
- It then finds a pattern at the end, so now it knows how long it is
- It can allocate space to build an offspring.
- Once space is allocated it enters copy loop, copies first line into allocated space, checks if it is done. If not it moves on to the next line.
- When the copy is done it issues a divide command and the copy gets its own process, starting to run on its own.
Evolution in Tierra progressed in two different directions:
One pressure was for programs to shrink. Since the shorter the program is, the less it has to copy the faster it can copy itself.
Second pressure: parasites would appear. This was very puzzling at first. Parasites were much shorter programs that started taking over the population, but failed to completely do so and died out, but then started taking over again, displaying an oscillation in parasite vs non parasite population. Parasite programs were almost identical to fully functional program structure - they would go as far as allocating space but instead of having a copy loop it would find another program nearby to use its copy loop. But when parasites started taking over the population there were too few programs with proper copy loops and the parasite population would shrink once more.
Eventually full programs started writing traps for the copy loop - instead of letting a parasite copy it, it would copy the host program. In this way a slightly longer program could be successful as it had a clever “hyper-parasite” strategy. For the most part though the programs ended up getting shorter.
Avida is inspired by Tierra
- Avida puts digital organisms on a grid - they replicate into neighboring grid positions
- Avida organisms possess virtual CPUs: registers to hold numbers they’ll be manipulating; stacks for numbers for longer term storage; input and output buffers. Instruction pointer to a position in the genome, and genome itself.
- Organisms are tasked/tested with performing certain logical operations. Logical equals is found to be the most complicated task for the organisms to perform.
- After an instruction is executed (eg INPUT) it moves on to next instruction (eg POP, which will pull something from stack)
- You don’t look at anything the genome is doing, you look at the environment. Example: you mark an organism as “capable of addition” if you see it is taking two numbers and outputting the sum, regardless of how it is doing this.
- In Avida, CPU cycles are treated as a resource. They are the units of “energy” for one of these digital organisms. what is in the environment is the resource available to metabolize. CPU speed of an individual is its “metabolic rate”
- There is one organism per grid cell. Some experiments have multi-cellular organisms which have cells work together, but still one genome per cell.
Avida vs Tierra
- Avida depicts genomes as circular as they exist in their own grid cell; in Tierra these are depicted linearly.
- In Tierra mutations rain down continuously (and randomly?); in Avida most common mutations are copy mutations - when an instruction is being copied you set a probability that instead of what you are meant to copy, a random instruction is copied instead.
Comparisons to Experimental Evolution
Example: a pair of competition experiments.
- In Env A, yellow organisms evolved in a low mutation rate environment. They can do complicated and delicate tasks as they do not mutate as much.
- In Env B, blue organisms evolved in high mutation environment; they can’t do as many tasks but are very robust.
Yellow organisms from Env A are put into Env B with blue organisms and vice versa. Usually organisms which evolved in particular environment do better in that environment than the newly introduced organism; in about 25% the newly introduced organism ended up winning, because during these experiments further evolution can be occurring that can swap favor.
Tracking evolution in a digital world:
With digital organisms we can look at any aspect of the population over time.
Avida digital organisms are set up in such a way that we can do the sorts of experiments biologists will often perform, but in a much more automated and simple fashion. Eg: knockout experiment (knocking out a gene to see what happens to a trait/operation) came from biology.
Unlike in Tierra, parasites do not evolve spontaneously in Avida. Parasites in Avida are more like “cheaters” - they replicate faster but do not hurt the host (they do hurt everyone around them). A parasite is a piece of code that just steals CPU cycles from a host vs directly harming the host.
A parasite commonly injects itself by targeting a particular task the host is doing to infect the organism that is doing that task. Even if all tasks are made equally valuable, hosts evolve to do more and more complex tasks requiring more code because if it’s more complex for the host it is also more complex for the parasite - the presence of parasites drives up the complexity of the host.
Comparisons to behaviour studies
We can examine behaviours evolved by digital organisms, such as foraging startegies.
- Digital organisms have ability to move to the next cell.
- They can only replicate in a black circle (single black circle in the 2D space)
- White circles are finite resources (multiple white circles in the space)
- An organism must have resources to replicate so they go to the black circle, then go back to a white resource circle, eat it, return to black circle.
- Organisms cannot see the black circle unless they are standing on it.
- They ended up tracking where resources are going and forming a large loop as they know where the resources are in relation to the black circle even if they cannot see the black circle.
- This same behaviour was then reproduced in physical robots.
The experiments shown in this presentation all had the organisms reproducing asexually. A question was asked about whether anything had been done with sexual reproduction. And in a limited way, yes; so far the observations have been:
- If you turn on sexual replicaiton and force organisms to be obligately sexual, they evolve faster;
- If you give them a choice between sexual and asexual reproduction, they will always choose asexual.
- Haven’t been able to get them to consistently evolve spontaneous sexual reproduction.
- Fundamentally, sexual recombination means your genome will be mixed with someone else’s and it works out to have a traumatic effect on the organisms as if we’ve substantially raised mutation rates.