Sipper M. Evolution of Parallel Cellular Machines. The Cellular Programming Approach

Springer, 1997, -204 p.Natural evolution has "created" a multitude of systems in which the actions of simple, locally-interacting components give rise to coordinated global information processing. Insect colonies, cellular assemblies, the retina, and the immune system, have all been cited as examples of systems in which emergent computation occurs. This term refers to the appearance of global information-processing capabilities that are not explicitly represented in the system's elementary components or in their interconnections.
The parallel cellular machines "designed" by nature exhibit striking problem solving capacities, while functioning within a dynamic environment. The central question posed in this volume is whether we can mimic nature's achievement, creating artificial machines that exhibit characteristics such as those manifest by their natural counterparts. Clearly, this ambitious goal is yet far off, however, our intent is to take a small step toward it.
The first issue that must be addressed concerns the basic design of our system, namely, we must choose a viable machine model. We shall present a number of systems in this work, which are essentially generalizations of the well-known cellular automata (CA) model. CAs are dynamical systems in which space and time are discrete. A cellular automaton consists of an array of cells, each of which can be in one of a finite number of possible states, updated synchronously in discrete time steps, according to a local, identical interaction rule. CAs exhibit three notable features, namely, massive parallelism, locality of cellular interactions, and simplicity of basic components (cells). Thus, they present an excellent point of departure for our forays into parallel cellular machines.
Having chosen the machine model, we immediately encounter a major problem common to such local, parallel systems, namely, the painstaking task one is faced with in designing them to exhibit a specific behavior or solve a particular problem. This results from the local dynamics of the system, which renders the design of local interaction rules to perform global computational tasks extremely arduous. Aiming to learn how to design such parallel cellular machines, we turn to nature, seeking inspiration in the process of evolution. The idea of applying the biological principle of natural evolution to artificial systems, introduced more than three decades ago, has seen impressive growth in the past decade. Usually grouped under the term evolutionary algorithms or evolutionary computation, we find the domains of genetic algorithms, evolution strategies, evolutionary programming, and genetic programming. In this volume we employ artificial evolution, based on the genetic-algorithms approach, to evolve ("design") parallel cellular machines.Universal Computation in Quasi-Uniform Cellular Automata
Studying Artificial Life Using a Simple, General Cellular Model
Cellular Programming: Coevolving Cellular Computation
Toward Applications of Cellular Programming
Online Autonomous Evolware: The Firefly Machine
Studying Fault Tolerance in Evolved Cellular Machines
Coevolving Architectures for Cellular Machines
Concluding Remarks and Future Research
A Growth and Replication: Specification of Rules
B A Two-state, r=1 CA that Classifies Density
C Specification of Evolved CAs
D Specification of an Evolved Architecture
E Computing acd and equivalent d'