Evolution of Complexity
Tissue Differentiation in Network Tierra

Thomas S. Ray
Zoology, University of Oklahoma, Norman, Oklahoma, 73019
ATR Human Information Processing Research Laboratories
2-2-2 Hikaridai, Seika-cho Soraku-gun, Kyoto 619-0288 Japan
ray@santafe.edu, www.isd.atr.co.jp/~ray/


Software of vast complexity is needed to realize the full potential of today's exponentially growing computational power. We briefly present our experiments in utilizing evolution to generate complexity in self-replicating multi-threaded computer codes.


We live in an exciting time, on the threshold of the new millennium, when several decades of Moore's law have brought us to the explosive phase of the exponential growth of computing power. This has led to the ubiquitous presence of computing machines containing vast numbers of computing elements.

We envision a near future in which almost every object contains a computer chip. We envision robots and vehicles able to move with the agility of animals through complex and unpredictable environments. We envision machines able to truly understand and communicate in casual spoken human language, sensitive to the subtle nuances of emotional content, and able to translate between all languages. We envision the dawn of the era of true artificial intelligence.

Yet, no amount of raw computer power will be intelligent unless it is properly organized. The exponential increase of computing power is driven by higher densities and greater numbers of components on chips, not by exponentially more complex chip designs. The organization of exponentially increasing computing power into complex behavior is primarily a software problem, not a hardware problem. The organizational complexity of hardware and software does not march forward according to Moore's law.

Our most complex software (operating systems and telecommunications control systems) contain tens of millions of lines of code, and have become very difficult to maintain and develop. It is not certain that conventional methods will permit our most complex software to increase in complexity by an additional one, two, or more orders of magnitude, in pace with computing power.

The products of natural adaptive systems (such as the human mind and the biosphere) vastly exceed the complexity of anything created by humans. While tens of millions of lines of computer code are very difficult to manage, genetic codes exhibit magnificently robust and adaptive functionality with billions of base pairs. The traditional, and still ubiquitous Von Neumann computer is rigid and brittle. By its very design, it lacks the robust and adaptive quality of living organisms grown from genomes.

The luxury of the rich bounty of computing elements available today invites the creation of new paradigms in computation. Computer scientists are turning to biology for inspiration in the creation of new computer architectures. Cross-fertilization between biology and computer science has opened the era of evolvable software and hardware, while at the same time the development of reconfigurable chips is blurring the distinction between hardware and software. While the Von Neumann computer still dominates, an era of active exploration of fundamentally new, and often biologically inspired computer architectures has begun.

In order to realize the full potential of our vast computational power, we may need to adopt new methods in the design of software and hardware. If we can identify and harness the principles behind natural adaptive systems we may be able to create human artifacts of similar adaptive complexity. The central problem in this quest is to understand how evolution creates unbounded adaptive complexity. The first key research target is to create this kind of evolutionary explosion of complexity in artificial evolving systems. The network Tierra experiment is an effort to create such an evolutionary process.

The Tierra System

The original Tierra experiment demonstrated the ability of evolution by natural selection to operate in the medium of digital computation. It yielded a rich evolutionary process, driven by a co-evolutionary dynamic in which much of the adaptive evolution was a response to the presence of other evolving "digital organisms" sharing the environment. However, after a prolonged period of rich adaptive evolution, Tierra inevitably enters a period of permanent evolutionary stasis.

In the original Tierra experiment, it could be argued that the ecological community increases in complexity, before entering stasis. However, the individual replicators generally do not increase in complexity, although some examples of increased algorithmic complexity in the replicators have been found. The Tierra project at ATR has been aimed at finding a way to create an evolutionary process in the digital medium that generates a large increase in the complexity of replicators without quickly ending in stasis.

Network Tierra

The Tierra research program is built on biological inspiration in the design of new computational paradigms. The new initiative developed at ATR has come to be known as "network Tierra", and is inspired by the recognition that much of the complexity increase that occurred in organic evolution on Earth has been concentrated into a number of "major transitions". These include such events as the origin of chromosomes, the origin of eukaryotes, the origin of sex, and the origin of multi-cellularity.

It appears that the richest evolution in Earth's history was associated with the transition from single-celled to multi-celled life. This transition generated most of the complex forms and processes that we know today: morphology, physiology, ecology, behavior, nervous systems, etc. Network Tierra is built around a digital analog to this transition: the transition from single-threaded to multi-threaded software.

The complexity of multi-celled organisms does not arise because many cells stick together, but rather because the many cells have differentiated into functionally different cell types which work together: blood cells, nerve cells, skin cells, liver cells, etc. Network Tierra is focused on the evolution of the differentiated condition. Network Tierra is seeded by a multi-threaded digital organisms which exhibits the most primitive possible level of differentiation: two cell types. The measure of success is the spontaneous evolution to greater levels of differentiation: three or more cell types.

The name "network Tierra" derives from the implementation of these experiments on a network of computers. The choice of a networked computational platform derives in part from the need to scale up the size of the environment for the digital organisms. Original Tierra generally operated in sixty thousand bytes of memory, and contained a few hundred digital organisms each with under a hundred bytes of code. If more complex individuals are to evolve, a single individual might fill such a small space. A networked platform provides a greater amount of memory space, and a greater amount of processing power.

However, a simple scaling up of the original Tierra experiment would certainly not cause an evolution of complexity or an escape from stasis. Another benefit of the networked environment is its inherent heterogeneity. Network Tierra runs as a low priority background process, and sleeps when the human user is active at the machine. This creates temporal an spatial patterns of the key resource, CPU time, to which evolution can potentially develop adaptations. Network Tierra includes new facilities which permit digital organisms to gather data about conditions on different machines on the net, and optionally to move between machines, based on their analysis of such data.

The seed organism in network Tierra contains a reproductive tissue of two cells and a sensory tissue of eight cells. The two reproductive cells work together in copying the genome from mother to daughter, each cell copies half of the genetic code. Each of the eight sensory cells collects data on a different machine on the net. The eight cells then cooperate in the comparison of the data to determine which of the eight machines offers the most favorable conditions. The result of the analysis is saved while another group of machines is analyzed. The result of the analysis is a recommendation as to where the daughter cell could be sent upon birth.

Interpretation of the results of evolution in network Tierra is a very difficult task. Tierran genomes are machine code. It is difficult to read and understand any machine code. Evolved machine codes are much more difficult to understand than those written by humans. Even more difficult still are multi-threaded evolved machine codes. A large part of the project has involved the development of tools to aid in the understanding of evolved digital genomes.

During the past year we have developed tools to analyze the degree of differentiation of different threads. Two threads are considered to be of the same cell type if they execute the same set of machine code instructions. Cells are differentiated into different cell types if they execute different sets of code. However, there can be both trivial and significant degrees of differentiation. Further, a meaningful analysis requires an understanding of the functional significance of differences in code execution by different threads. The analysis of thread differentiation can be only partially automated, and requires a great deal of effort.

Our analysis of thread differentiation has revealed that the relatively complex functions of the original sensory threads have been subdivided into at least two tasks, which are now accomplished by two sets of cells. Thus the single sensory tissue has evolved into two tissues, so that the total number of cell types in the digital organism has increased from two to three.

These results are our first indication that the evolutionary process in network Tierra can cause the kind of complexity increase that formed the basis of the Cambrian explosion of diversity: an increase in the level of differentiation into cell types. We are continuing to refine our analytical techniques, to apply them to more data, and to explore the conditions affecting evolution in the network environment.

The Future of Complex Computation

The emergence of artificial intelligence is not a certainty, like the inexorable march of Moore's law. Raw computing power is not intelligence. Our ability to ever create information processes of a complexity comparable to the human mind is completely unproven and absolutely uncertain.

I have suggested evolution as an alternate approach to producing intelligent information processes. Yet evolution in the digital medium remains a process with a very limited record of accomplishments. We have been able to establish active evolutionary processes, by both natural and artificial selection in the digital medium. But the evolving entities have always contained at most several thousand bits of genetic information.

We do not yet have a measure of the potential of evolution in this medium. If we were to realize a potential within several orders of magnitude of that of organic evolution, it would be a spectacular success. But if the potential of digital evolution falls ten orders of magnitude below organic evolution, then digital evolution will lose its luster. There is as yet no evidence to suggest which outcome is more likely.

The hope for evolution as a route to AI is not only that it would produce an intelligence rooted in and natural to the medium, but that evolution in the digital medium is capable of generating levels of complexity comparable to what it has produced in the organic medium. Evolution is the only process that is proven to be able to generate such levels of complexity. However, that proof is in the organic, not the digital medium. Like an artist that can express their creativity in oil paint but not stone sculpture, evolution may be capable of magnificent creations in the organic medium but not the digital.

Yet the vision of digital evolution of vast complexity is still out there, waiting for realization or disproof. We are only at the most rudimentary level of our experience with evolution in the digital medium. The possibilities are great enough to merit a serious and sustained effort.