Wolfram Computation Meets Knowledge

Wolfram Summer School

Alumni

Alyssa Adams

Summer School

Class of 2014

Bio

Originally from Southern California, I moved to Tennessee upon acceptance into the honors program at East Tennessee State University. There I completed a BS in physics, magna cum laude, along with a thesis, which investigated the atmospheric properties of three Mira-type stars using a rich yet underutilized data archive at the University of Wisconsin’s HPOL. Now back in the west, I just finished my first year in Arizona State University’s Physics PhD program. I’ve been using 1D elementary cellular automata as a means to study self-reference in context of how biological systems use state-dependent feedback loops for evolutionary development. This may be closely related to the evolution of symbolic utility since self-reference has been recognized as a vital component when introducing a word to a lexicon. For the rest of my PhD work, several models will be explored to gain insight into the mechanisms that drive these processes.

Science outreach is the other important aspect in my education and I always enjoy participating in any opportunity that arises. I’ve been involved with ASU’s Sundial program, which is the embodiment of a support structure for students in science. Currently, most of my free time is spent playing online competitive team games with my husband. We manipulate our team’s dynamic network in a self-beneficial way to maximize “noob pwnge” on the enemy dynamic network. I’ve also played the piano for 13 years and am looking forward to continuing my musical studies when academics offer more breathing room. Finally, I enjoy painting and drawing cartoons.

Also, life is not complete without a cat.

Project: Genetic Programs Subject to Their Environment, Modeled by Cellular Automata

Context of my PhD work

In biology, it is understood that self-reference is central to emergent symbolic processes on a variety of scales (Kataoka, 1999, Zenil, 2012, and Danchin, 2009). However, the role of self-reference in evolutionary dynamics is unclear, let alone how biology came to use self-reference in the first place. On a quest to understand and formalize self-reference in biological models, we partition these questions into testable models that will provide insight into the dynamics of the mechanical components of self-reference. One of these models is the focus of this project.

Already, we have found that self-reference in a 1D ECA cannot lead to open-ended complexity, but state feedback provides self-reinforcing regions of behavior and, more importantly, how functional diversity can be embedded in a single automaton (Pavlic, 2014). Because biology is embedded in an environment, this model is probably not realistic in a physical sense, because no outer mechanisms are interacting with the system (Zenil, 2012).

Summer Model 1

For a tractable biological model, a type of “environment” that can act on the system must be introduced (Goldenfeld, 2010) and the interaction must be understood in simple terms. In the simplest terms possible, an environment acts on biology by means of selection criteria. In an attempt to understand how the environment influences biology, we interpreted the environment physically by an execution of some ECA rule with some initial condition, which created a fitness landscape at each time step that was applied to an “organism” CA of equal width, length, and with the same initial condition.

Each ECA rule lookup table is composed of 8 “sub-rules” (although this term is not conventional, we will use it in this description). Here is an example of the 8 sub-rules for rule 110:

111 -> 0, 110 -> 1, 101 -> 1, 100 -> 0, 011 -> 1, 010 -> 1, 001 -> 1, 000 -> 0″></p>
				<p>At each iteration in the environment, the frequency distribution of sub-rules expressed is computed. Take a look at the
					first few iterations of rule 110 below. </p>
				<p><img src=

At the first time step, the sub-rule 000->0 is used 6 times, 001->1 is used 1 time, 010->1 is used 1 time, and 100->0 is also used 1 time. Respectively, the frequency distribution for the first time step is 6/9, 1/9, 1/9, and 1/9.

As an abstract way of using the environment as a fitness landscape, these distributions are used as a threshold that the “biology” ECA must meet in order to make a change to its rule. If the organism ECA expresses sub-rules that meet or exceed the environment threshold for the same sub-rules at the same time step, then the sub-rule in the organism ECA’s rule space is changed at the bottom bit, and the next iteration is computed with the new rule.

Given the current parameters, it was easy to find a complexity at the phenotype description; however, the rule space remained static in many of these cases. It is more interesting to find combinations that yielded complex behavior at the level of the genotype as well as the phenotype. Amazingly, we have already seen interesting cases where the phenotype expresses complexity, while the genotype oscillated in a subset of rules in a complex way. Here are examples of complex behavior in both the phenotype and the genotype. The top plot is the organism’s rule space as a function of time step, and the three CA plots below the rule space are the environment execution, the organism without the interaction of the environment, and the organism as a result of the environment interaction (respectively). This particular combination of environment rule + initial organism rule has been shown to exhibit this behavior for 2^width time steps, which indicates that it will never converge. Note that the rightmost example has a phenotype that converges to a non-complex state, but the transient is visually appealing.

This table is a visualization of many different CA rules

Both the phenotype and genotype will be measured with 5 complexity measures. An example of these complexity measures for the phenotype is seen below:

This table is an analysis of several different CA rules

Because these results express complexity at both the phenotype and genotype, without converging in the exhaustive case, this is a simple model that strongly expresses the presence of open-ended complexity. A rigorous study of the dynamics between the environment and any interacting organisms has yet to be explored in full detail. We seek to gain knowledge about the different types of combinations and hope to generalize the effects of the initial conditions, width of the CAs, and combinations that lead to open-ended evolution.

Summer Model 2

A second attempt to understand environment-biology interaction was made with an abstract representation of the environment. The goal of this model is to understand how a system changes its genetic code according to a selection criteria of its phenotypic expression. This is not unlike a typical genetic algorithm experiment; however, our selection criteria is what makes this experiment unique. Instead of selecting for genetic programs that can perform a simple task reasonably well, we select for the rules which produce the “most different” phenotype. The genetic code is selected for innovation rather than task completion.

In a 1D ECA model, one genotype is selected from the 256 rule space, while the phenotype is the execution of the rule on some initial condition. A random subset of the rule space was applied to the same randomly generated initial condition for some amount of time steps. Then we selected the most different final step from each genotype, calculated by the maximal Euclidian distance from the mean state. In this context, the mean state is the average association from the rule to the final step of its execution. Its genotype was then randomly perturbed by dx bits, n number of times to simulate mutation of the ‘most fit’ gene. The population of mutants was then applied over another randomly generated initial condition, and contented the process. Here is the resulting phenotype-genotype evolution after 100 successive generations (generations run to the right instead of down for aesthetic preservation).

To gain a more comprehensive insight to these evolutionary dynamics, we mapped out the genotype attractor states by neighborhoods of rules. Neighborhoods can be composed by taking a rule and successively flipping one bit in the sequence. The result is eight rules with Hamming distance=1 away from the original rule, plus the original rule itself.

For each rule neighborhood, the most fit rule was found over an ensemble of random initial conditions. The result is a directed graph, which shows the most fit mutations of one rule into another. Surprisingly, not all the rules are connected. Instead, the graph of the rule space has many non-connected components, which include isolated, cyclic rule pairs. Here is an example of the rule space for width=100, steps=10, initial condition ensemble size=100 for 1D ECA. The vertex colors indicate vertex degree.

For the graph above, here are the vertex degrees for the 88 non-equivalent rules. Orange indicates class 3 rules, red indicates class 4 rules, and grey indicates class 1 and 2 rules.

The novelty about this experiment is the two-way feedback between the genotype and the environment. Because the environment is completely represented by the results of the phenotype (rules that produce the most different phenotype), the genome has influence over the environment’s selection. This is significantly different from traditional one-way models that have a fixed fitness selection. To illustrate, consider the bottom graph. This is the same experiment, but with a static fitness selection criteria (rules that produce the most black phenotype). Notice how there are less solutions to the problem, indicating less functional diversity.

This experiment was also completed for 1D outer totalistic CA, since the rule space is reasonably computationally inexpensive to explore. Similar results have been found.

References

Danchin, A. “Bacteria as Computers Making Computers.” FEMS Microbiology Reviews 33, no. 1 (2009): 3–26.

Goldenfeld, N. and C. Woese. “Life is Physics: Evolution as a Collective Phenomenon Far from Equilibrium.” Annual Review of Condensed Matter Physics

Kataoka, N. and K. Kaneko. “Functional Dynamics I: Articulation Process.” Physica D 138, no. 3–4 (2000): 225–250.

Pavlic, T., A. Adams, S. I. Walker, and P. C. W. Davies. “Self-Reference Cellular Automata: A Model of the Evolution of Information Control in Biological Systems.” In Artificial Life 14: Proceedings of the Fourteenth International Conference on the Synthesis and Simulation of Living Systems [Sayama, H., et al. (Eds.)], 2014.

Zenil, H., C. Gershenson, J. A. R. Marshall, et al. “Life as Thermodynamic Evidence of Algorithmic Structure in Natural Environments.” Entropy 14, no. 11 (2012): 2173–2191.

Zenil, H. and E. Villarreal-Zapata. “Aysmptotic Behavior and Ratios of Complexity in Cellular Automata Rule Spaces.” International Journal of Bifurcation and Chaos 23, no. 9 (2013): 135–159.

Favorite Outer Totalistic r=1, k=2 2D Cellular Automaton

Rule 182539