Turducken, Part 2
Here’s another draft of my paper from last quarter. Still not finished, but hopefully will be done tomorrow. Just need to edit, smooth things out, add some lit review (including Von Neuman, Holland) and explain the last little bit about how the “DNA” gets copied.
Apologies to everyone to whom none of this makes sense. The blog is just a nice public place to keep this.
Update 4/14: This is complete now. It’s not a great paper, but at least it represents my idea.
The goal of this project is to design an ALife system that has a good chance of supporting open-ended evolution and to do so as simply as possible. This will hopefully lead to better understanding of what open-ended evolution is and how it happens. This paper presents a detailed specification of a system which was designed in order to support tighly coupled multi-scale evolutionary activity and encourage its emergence.
Background
Previous work, presented in my seminar paper Increasing Complexity in Artificial Life Systems, explored several definitions of complexity and ALife research that made some claims about complexity. It also made four guesses about ways to create ALife systems that would increase in complexity over time:
- Use intrinsic fitness and replication functions
- Create an artificial physics with forces of different strengths
- Choose the scale of the world in the replication carefully. Replication should happen on a super-atomic scale (>= 1 order of magnitude larger than atoms) and the world should be at least 3 (?) orders of magnitude larger than the scale of replication.
- Creatures should be built of component systems
The current work, then, tries to put some of these into practice. As it turns out, it’s very difficult to define complexity and to work with it experimentally, so I’m focusing on a less abstract goal: an create an ALife system that supports tightly coupled evolutionary activity at multiple scales, where large scale structures are built out of the smaller scale structures. An example of this in biology is cells and organisms. Cells are evolving within organisms, and organisms are evolving their composition of cells. The holy grail of this project would be to see larger scale activity emerge from small: organisms evolving out of a population of cells.
The method being employed is to specify a candidate model in pictures and words, and then engage in thought experiments about how it would play out, how much computational power would be required, and its potential for meeting the goal of multi-scale evolution. This has led to a design specification for an ALife system which can now be built and experimented with.
Choice points in the design process
Just as important as the specification itself are the motivations behind its properties. Almost all properties of the model present a tradeoffs between richness and simplicity. I constantly fought a desire to make the model more and more like the physical substrate of the biological world: molecules with complex interactions emerging from their structure. But the goal is not to replicate the natural world, but to replicate its properties of complexity and evolutionary activity across scales, and so made great effort to get the model down to the bear bones that would meet my goal.
There were four major insights that came out of the design process.
Physics with multi-scale forces is not important
While it does seem true that some of the complexity that happens at a small scale (cellular and below) seems to arise from the fact that the physics at that scale is so varied, the fact that there is such complexity above the cellular level, and indeed much complexity in structures built entirely of cells, it seems like it would be reasonable to start with something like cells as the bottom of the pyramid.
That is as deep as the analogy gets “something like”. The point is not to duplicate their behavior, but rather to create objects that might play a vaguely similar role in larger-scale structures.
Intrinsicness is a continuum
Another one of the major insights that arose from considering a wide range of possible designs is that intrinsicness of fitness and replication is not a binary property. A purely extrinsic replication, for example, would simply pull organisms out of a world, copy them, and place them back in the world, based on an external clock. A slightly more intrinsic replication scenario would be to put a button in the world that organisms could push that would replicate them. Then, the “hand of god” would come and create a copy. More intrinsic still would be if body parts could be duplicated with a supernatural machine, but that organisms needed to use their own power to assemble them. This continuum continues all the way to the point where the entire replication process takes place in the world, and is subject to all the same selective pressures that the organisms themselves are.
This insight led me to place several “buttons” in the environment that allow fairly limited replication to occur for free. In Turducken, this is basically manifested in the COPY actuator, which nodes can use to copy a range of classifiers from their memories into other nodes. This means you can get a simple node that self-replicates “for free”. But larger structures require a more complex process which is the subject of most of the rest of the paper.
The nice thing about having a largely intrinsic replication process like this is that fitness and replication functions can be entirely done away with. Whether an organism survives and propagates depends only on whether the organism survives and propagates. With typical classifier systems, replication and fitness are handled extrinsicly by functions crafted by the developer.
Why is this important? Because intrinsic fitness and replication are an absolute requirement for organisms to emerge into fitness and replication niches created by other populations of organisms, and this is a key requirement for multi-scale organisms. In the real world, a cell’s fitness is determined by the structure of the organism, and an organism’s fitness is determined by the structure of the cell, both of which are constantly evolving. Intrinsic fitness and replication give us a fighting chance at replicating this phenomena.
Information is impetus for growth
A third major insight came from looking at Holland’s classifier system’s (Booker, Goldberg, Holland, 1989). Classifier systems are collections of input-output rules. They are presented encoded information from an external source, and the information is matched against the entire body of rules. If the information matches any rule’s input pattern, that rule either activates some kind of actuator, or puts out another message for the other classifiers to consume. The classifiers that get the most work are selected for by an external fitness function and are allowed to remain in the system, and are also used to create mutated copies. Classifier systems are a fertile medium, in that they seem to be able to “implement” almost anything. Long chains of classifiers can emerge, with classifiers deeper in the chains consuming more and more refined information. This suggests a kind of open-ended complexity, with more and more abstract information being used.
Indeed, this might be a good incentive for organisms growing large in the real world. In order to be able to process information on larger and larger scales, organisms would need to grow larger and more complex. It is because of this insight that drove me to base Turducken’s information processing capabilities on classifier systems.
Departure from classifier systems
Early work on this project focused on creating an artificial physics that could support multi-scale evolution. However in the light of my personal discovery of classifier systems, I was faced with a choice: do I abandon the artificial physics and start working entirely in classifier systems? Or should I integrate some of the key properties of classifier systems into my artificial physics? I ended up choosing the latter mostly for one particular reason:
Classifier systems have a distinct, independent inside and outside. The inside is controlled by a genetic algorithm, and the outside is controlled by a third party, although it might be influenced by the behavior of the classifier system, as mitigated by the classifier system’s body, which is off in the black box of the environment. In contrast, what I wanted for Turducken was a situation in which life processes provided the environments for each other and apply selective pressures to each other. This kind of happens in classifier systems, but in the end the fitness depends on an external process. In essence, by embodying classifiers in the way I do, I allow them to mutually define their own fitness landscapes.
The Model
This model is named “Turducken”, after the kitchy practice of stuffing a turkey with a chicken and then jamming the entire thing into a duck and roasting it. It is hoped that the model outlined here will yield a similarly satisfying nesting of organisms, albeit a nesting of a very different kind.
Turducken is a virtual world populated primarily with “nodes” (Figure 1), atomic particles which float around in a soup. Nodes have no real boundaries or substance, in that two nodes can occupy the same location and can easily pass through one another.
Figure 1: A single node
One strategy employed in Turducken to provide an incentive for organisms to exploit niches at multiple scales is to create an information-rich environment which is made up of organisms themselves. It oes this by embodying properties similar to one of the simplest-possible information environments that has been proven to support evolutionary activity: John Holland’s “classifier system”. (FIXME: Citation)
In a typical classifier system, information comes from the outside in the form of character strings representing sensory input. These strings are then “broadcast” to a set of classifiers, which have two parts: a pattern that may or may not match some sensory input, and an actuator that emits some output signal or broadcasts another message back to the classifier set.
For example, a light detector might generate a string: 11111 that represents a bright light. A classifier with the pattern 1???? would match that string, and emit an output signal for the organism to close its eyes. Another classifier that matches strings that look like 1?1?1 might broadcast another message “10001″ back to the classifier set, which would, also activate the first classifier, causing the eye close actuator to be activated again.
Turducken creates a similar situation, with some small but important modifications. First, messages come not from the outside world, but from the nodes themselves. This allows life to truly provide a foundation for life, and ensure that nodes responding to messages from other life forms intrinsic to the world are selected for, instead of nodes that respond well to some extrinsic input. The simplest form of broadcasting is simply for a node to emit a string (Figure 2) that reaches all nodes in its local area, with a probability inversely proportional to distance.
Figure 2: Message source
These simple nodes then provide a backdrop for bootstrapping more complex behaviors. Nodes with movement classifiers (Figure 3) listen for messages of a certain form, and then move in response to matches. A node could have several classifiers all pertaining to different directions of movement (up, down, left right).
Figure 3: Message-driven movement rule
Classifier systems can yield complicated structures of dependency, with chains of classifiers feeding into each other, but in order to have tightly-coupled classifiers, each classifier needs to encode information about the other classifiers to which it is coupled. This makes it harder to have tight-coupling across scales, because both the large and small scale must be “aware” of each other.
This is why Turducken includes a concept of space, motion and several other constraints that are hard-coded outside of the classifiers. These constraints create an environment in which classifiers can be coupled, even in exclusively ways, without having to encode this coupling in their input/output patterns. As described, nodes have position and motion, but a third property of these classifier “bodies” is bonds. (Figure 4)
Figure 4: Three bonded nodes
Nodes can bond with other nodes by using the BOND actuator. This actuator essentially “offers” a bond conditionally on matching a certain message pattern. So a node which offers a ???? bond will match any other bond-offering node, whereas a node offering a 1011 bond will only match generalizations of that string.
The bonding process is shown in Figure 5. Any two nodes in close proximity with matching bonds offered automatically bond together. Both nodes can then break the bond with a corresponding BREAK actuator.
Figure 5: The mechanism for node bonding (steps 1-4) and bond breaking (step 5).
Once nodes have been bonded together, they can move as a group with a “rubber-band” effect. One node can move, and the others will be dragged behind it. (Figure 6) In addition, bonded nodes can send private messages to one another via a MESSAGE actuator. (Figure 7)
Figure 6: Movement of bonded nodes.
Figure 7: Private communication between bonded nodes.
Detailed specifications for the different actuators and their diagramatic representations follow:
MOVE(x, y)
Causes the node to try to move x steps horizontally and y steps vertically. The node may or may not actually move, depending on the stress on its bonds.
The only new actuator used here is the COPY actuator, which erases all of the classifiers in a bonded node and then copies a subset of the current node’s classifiers over it.
The next step is to describe how the behavior of the + node might be implemented in a turducken structure. Ideally, the structure would have some generic set of machinery and then a string of nodes that contained the actual instructions carried out by +.
BOND(bond_id, pattern, message)
Where bond_id is a number to use as a label for the bond, pattern is the pattern that needs to be matched by the other node which is offering a bond, and message is the message to broadcast when the bond is formed. If the bond_id is left blank, a bond will be formed with no ID, and if the message is left blank, no message will be broadcasted
BCAST(message)
Broadcasts messages to “nearby” nodes. The message “strength” would fall-off at longer distances, meaning the probability of reception would decrease. Therefore a large array of nodes could reliably hear “fainter” messages.
MSG(bond_id, message)
Sends a message to the single node that is connected on bond_id.
COPY(first_classifier, last_classifier, bond_id)
Copies the invoking node’s classifiers to the node connected on bond_id. Only in the numerical range provided are copied.
BREAK(bond_id)
Breaks the bond with the given bond_id.
Intrinsic Fitness and Replication
There are many ways to self-replicate, and parasites often exploit highly creative reproductive niches, but a good starting point for self-replication is to break the process down into three tasks: describing the activity of building an organism, describing the mechanism by which a blueprint is decoded into that activity, and describing the mechanism by which the blueprint gets copied.
Let’s start by examining a mechanism by which structures in Turducken might be built.
Self-Replication
A simple self-replicating structure in Turducken is complicated enough that it needs to be looked at in parts. To do this, we will assume temporarily that we already have a nettwork of nodes (represented by the + node) which can carry out a sequence of actions. Later on we’ll describe how the + node could be implemented. Figure 8 details the steps that would be required to build the simplest multi-node structure.
Figure 8: Structure building with a “god” node (the +).
Despite the fact that the target structure is relatively simple (A-B), quite a few steps are required, and a good bit of overhead. It turns out, it would be relatively simple to write up a set of classifiers for a node that would do what + does. It would be a lot of classifiers, but it would be doable. However, we couldn’t simply work those out and be done, because it that approach wouldn’t really work for large-scale objects. You’d have to have millions of classifiers in one node, and nodes are meant to be simple, largely atomic information processors. In order to have a large-scale replication process we need to be able to store the blueprints in a chain of nodes.
The next step is therefore to describe how the behavior of the + node might be implemented with a structure that “reads” a chain of nodes.
First + Implementation
My first crack at this was to a string of command nodes (A,B,C…) and then a sort of “playhead” node (~) which would tell a command node to write an instruction to the + node and then send a message to + to tell it to carry out the command. The ~ and the command node would then work together to move the + and the ~ on to the next command node.
This entire process is depicted in figure 9. The system depicted will wait for a message to come from nearby, because this is sometimes required by the specification for +. Advancing to the next step without waiting for a message simply requires adding the actions from ~’s [P] classifier to its [START] classifier.
Figure 9: Initial implementation of + node with genetic chain
The classifiers required for this behavior are shown below:
A and B:
1. “M” -> COPY(6,7,2)
MSG(2,”N”)
2. “Q” -> MSG(2,”T”)
MSG(0,”S”)
3. “S” -> BOND(1,”R”,”V”)
-> BOND(2,”U”,”W”)
4. “V” -> BREAK(1)
5. “W” -> BREAK(2)
6. “N” -> [do something*]
BCAST(”P”) [or let the structure being built broadcast "P"]
7. “T” -> BOND( ,”U”)
~:
1. “START” -> MSG(0,”M”)
2. “P” -> BOND(1,”R”)
MSG(0,”Q”)
3. “W” -> MSG(1,”M”)
Note that classifier 6 in the command node could be anything. It’s simply whatever action + is supposed to carry out at that moment. This classifier is the only one that varies from node A to B to C, and is really the “blueprint” information.
There are a few known bugs with this implemention. Classifier 3 in ~ waits for the “W” message, signifying one of the bonds in step 7 being made, but really it should wait for the “V” message too. This could be done trivially with an extra classifier and a way to store state. State storage is described in section FIXME below.
In addition, ~’s bond to node A is bond 0, but when it bonds to node B it has to use a new bond: bond 1. That means the classifiers that worked with A will no longer work. This could probably be fixed by breaking the bond with A before forming the bond with B.
This still has no mechanism for copying the A-B-C chain, which would need to be automated somehow. A mechanism for this is described in the “Copying the blueprint” section below. The real problem, though, is that this setup is awfully complicated, and it requires a LOT of procedural information to be duplicated and stored in the A-B-C chain. Ideally that chain would contain only the raw instructions to be carried out by +. A structure that is much closer to this level is described in the following section.
Second + Implementation
Figure 10: Second + implementation
After thinking through the initial implementation of +, it seemed like the same behavior could be accomplished much more simply. My second strategy was to have the A-B-C nodes just send an encoded command to the + node and have the + node decode it and carry it out. This process, depicted in figure 10 required fewer nodes, however it requires + to have a large number of classifiers for decoding the commands. Below are the classifiers required for processing the A-B-C sequence, along with a sample of a few of the decoding classifiers:
A,B,C, etc:
1. “P” -> MSG(0,[encoded command])
MSG(1,”N”)
BREAK(0)
2. “N” -> BOND(0,”M”,”P”)
+:
1. “Q” -> BOND( ,”M”)
“MOVE?,?” -> MOVE(\1,\2)
“BOND?,?,?” -> BOND(\1,\2,\3)
“BCAST?” -> BCAST(\1)
etc…
Note that I’ve introduced a new feature here in the classifiers, which is the actual content of blocks of ?’s can be referenced in the actuator part of the classifier with an escaped number.
More ?’s would likely have to be used to be able to use longer messages. Or perhaps a * operator should be introduced so that ?* would match a string of any length.
State
In order to have the + node wait for a certain message before proceeding, we need some way to store state. This is pretty trivial, but it requires two nodes. (Figure 11) The first node contains both states of the second node, and the second node essentially asks the first node to rewrite it in order to change state.
Waiting for messages with the second implementation
Our original implementation of + described how the + could have an instruction that would wait for a message before it executed. This doesn’t automatically work in the new system, because we need a way to prevent the message from having an effect until that piece of the genetic code is “activated”. This is why we needed a way to store state, and the mechanism described for storing state provides us with our solution.
Figure 12: Second + implementation, with waiting
Figure 12 depicts a node tuple (S and B) which has an ON state and an OFF state, and only responds to a message when in the ON state. The ON state responds to a message, and the OFF state doesn’t. The mechanism pictured is basically the same as the one in figure 10, except with a few extra classifiers for changing state.
This situation still has a few bugs. Likely, the mechanism should change the state back to OFF after advancing to the next node (C, not pictured). However, it can change the state to off in just the same way it changed it to ON, by S copying B’s new state onto it. There is no need to belabor the process.
Copying the blueprint
The last big unexplained component of a self-reproducing Turducken structure is the replication of the genetic code, in this case, the A-B-C-… chain of nodes. Figure 13 depicts a piece of a rather buggy replication process, but it’s a starting point. The X node grabs a free floating node and programs it to try to bond to A. X then tells A to bond to the free floating node (now programmed as Y) and A does so. A then copies its code onto Y, turning it into a clone, while X releases A and swings around to bind to B. A essentially tells B that X is ready for it and B offers a bond to X.
Figure 13: Copying the blueprint
There are several bugs in this process. First, it fails to copy the S (state) nodes, used for waiting in during the construction process, which are described above. This is a tricky issue, but perhaps it could be solved by having the state nodes be part of the chain, rather than offshoots of it. The second major bug in this copying process is that it doesn’t really describe how the copied nodes come to be bonded to each other. Obviously in the next few (unpictured) steps X would have to tell the new Y node and the A’ node to bond to each other.
The trouble with all of that is that it just puts a lot of complexity into the A-B-C nodes. And that just seems less than ideal from the perspective of a computer scientist. But if it works, and it’s enough to get the process of adaptation started, maybe it’s fine.
Conclusion
The same major criticisms of this project remain from the beginning of the quarter. It’s based on intuition. There’s no data to prove anything. There’s not even really a very good argument about why it ought to work. In fact, I myself have little confidence that it will work. But it is a much more detailed picture of my intentions than I had three and a half months ago. And most usefully it allows me to see flaws in my thinking I couldn’t really see before.
And it provides a platform on which to actually test some of my hypotheses. So that’s progress. Still, bugs remain in the self-replication process described here. And it’s not clear that any kind of evolutionary activity would happen in a population of these, especially given that there’s no energy being transacted, only information, which doesn’t leave a lot of incentive to evolve.
Still, parasites could easily be introduced that would attack these larger structures, and that might provide enough selective pressure to evolve competetive mechanisms that would then provide a medium for further competition. I’d certainly like to give it a try.
References
LB Booker, DE Goldberg, JH Holland (1989) Classifier systems and genetic algorithms. Artificial intelligence [0004-3702] Booker yr:1989 vol:40 iss:1-3 pg:235
